Maximum directed cuts in acyclic digraphs

DOI10.1002/JGT.20215MaRDI QIDQ3445498zbMATH OpenOpenAlexFDO

Authors Noga Alon, Béla Bollobás, András Gyárfás, Jeno Lehel, Alex 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

zbMATH Keywords

directed and acyclic graphsdirected cutextremal problemsmaximum cut

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35)

Recommendations

• Maximum directed cuts in graphs with degree constraints
• Maximum directed cuts in digraphs with degree restriction
• On maximum edge cuts of connected digraphs
• Intersection properties of maximal directed cuts in digraphs
• Covering the edges of digraphs in \(\mathcal D(3,3)\) and \(\mathcal D(4,4)\) with directed cuts

Cites work

• Monochromatic directed walks in arc-colored directed graphs
• Some Extremal Properties of Bipartite Subgraphs

Cited in

(30)

• A note on line digraphs and the directed max-cut problem
• Max Horn SAT and the minimum cut problem in directed hypergraphs
• Bounded degree acyclic decompositions of digraphs.
• Maximum directed cuts in graphs with degree constraints
• On judicious bipartitions of directed graphs
• A bound on judicious bipartitions of directed graphs
• Oblivious algorithms for the maximum directed cut problem
• On bisections of directed graphs
• Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization
• Acyclic digraphs
• Intersection properties of maximal directed cuts in digraphs
• Maximum directed cuts in digraphs with degree restriction
• Online Maximum Directed Cut
• scientific article; zbMATH DE number 4101224 (Why is no real title available?)
• Covering digraphs with small indegrees or outdegrees by directed cuts
• Covering the edges of digraphs in \(\mathcal D(3,3)\) and \(\mathcal D(4,4)\) with directed cuts
• 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
• Odd Multiway Cut in Directed Acyclic Graphs
• On mergings in acyclic directed graphs
• On maximum edge cuts of connected digraphs
• 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
• Optimal bisections of directed graphs
• Bounds on maximum weight directed cut
• Bisections of directed graphs without complete bipartite subgraphs
• On orientations with forbidden out-degrees
• A randomized rounding approach for DAG edge deletion
• A family of perfect graphs associated with directed graphs

This page was built for publication: Maximum directed cuts in acyclic digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3445498)