Maximum directed cuts in acyclic digraphs
From MaRDI portal
Publication:3445498
DOI10.1002/jgt.20215zbMath1117.05056OpenAlexW4255598955MaRDI QIDQ3445498
Noga Alon, Béla Bollobás, András Gyárfás, Jenő Lehel, Alexander D. Scott
Publication date: 11 June 2007
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.20215
Related Items (18)
On judicious bipartitions of directed graphs ⋮ Intersection properties of maximal directed cuts in digraphs ⋮ Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization ⋮ Maximum directed cuts in graphs with degree constraints ⋮ Covering digraphs with small indegrees or outdegrees by directed cuts ⋮ Impact of soft ride time constraints on the complexity of scheduling in dial-a-ride problems ⋮ Partitioning digraphs with outdegree at least 4 ⋮ Graph partitioning: an updated survey ⋮ Covering the edges of digraphs in \(\mathcal D(3,3)\) and \(\mathcal D(4,4)\) with directed cuts ⋮ Optimal bisections of directed graphs ⋮ An LP-rounding \(2\sqrt{2}\)-approximation for restricted maximum acyclic subgraph ⋮ On the maximum arc-chromatic number of digraphs with bounded outdegrees or indegrees ⋮ On Maximum Edge Cuts of Connected Digraphs ⋮ A bound on judicious bipartitions of directed graphs ⋮ Maximum directed cuts in digraphs with degree restriction ⋮ Acyclic Digraphs ⋮ Oblivious algorithms for the maximum directed cut problem ⋮ On bisections of directed graphs
Cites Work
This page was built for publication: Maximum directed cuts in acyclic digraphs
