Premium
Maximum directed cuts in acyclic digraphs
Author(s) -
Alon Noga,
Bollobás Béla,
Gyárfás András,
Lehel Jenő,
Scott Alex
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20215
Subject(s) - digraph , directed acyclic graph , combinatorics , directed graph , mathematics , strongly connected component , feedback arc set , discrete mathematics , constant (computer programming) , graph , computer science , line graph , voltage graph , programming language
It is easily shown that every digraph with m edges has a directed cut of size at least m /4, and that 1/4 cannot be replaced by any larger constant. We investigate the size of the largest directed cut in acyclic digraphs, and prove a number of related results concerning cuts in digraphs and acyclic digraphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 1–13, 2007