Abstract | ||
---|---|---|
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 |
Year | DOI | Venue |
---|---|---|
2007 | 10.1002/jgt.v55:1 | Journal of Graph Theory |
Keywords | Field | DocType |
maximum cut | Graph theory,Discrete mathematics,Combinatorics,Minimum cut,Directed acyclic graph,Mathematics,Maximum cut,Digraph | Journal |
Volume | Issue | ISSN |
55 | 1 | 0364-9024 |
Citations | PageRank | References |
16 | 1.14 | 9 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Noga Alon | 1 | 10468 | 1688.16 |
Béla Bollobás | 2 | 2696 | 474.16 |
András Gyárfás | 3 | 582 | 102.26 |
Jenö Lehel | 4 | 141 | 24.61 |
Alex Scott | 5 | 251 | 40.93 |