Judicious partitions of directed graphs

DOI10.1002/rsa.20579zbMath1330.05078arXiv1305.2986OpenAlexW2071932326WikidataQ115150369 ScholiaQ115150369MaRDI QIDQ3467583

Choongbum Lee, Po-Shen Loh, Benjamin Sudakov

Publication date: 3 February 2016

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.2986

zbMATH Keywords

directed graphsjudicious partitioning

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20)

Related Items (11)

On judicious bipartitions of directed graphs ⋮ Partitioning digraphs with outdegree at least 4 ⋮ On bisections of graphs without complete bipartite graphs ⋮ Graph partitioning: an updated survey ⋮ Optimal bisections of directed graphs ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ On splitting digraphs ⋮ On bipartitions of directed graphs with small semidegree ⋮ Bipartitions of oriented graphs ⋮ A bound on judicious bipartitions of directed graphs ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable

Cites Work

• Unnamed Item
• Bisections of graphs
• On several partitioning problems of Bollobás and Scott
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Partitioning 3-uniform hypergraphs
• Max \(k\)-cut and judicious \(k\)-partitions
• The size of the largest bipartite subgraphs
• Maximum cuts and judicious partitions in graphs without short cycles
• Judicious partitions of 3-uniform hypergraphs
• Exact bounds for judicious partitions of graphs
• The Bollobás-Thomason conjecture for \(3\)-uniform hypergraphs
• Bipartite Subgraphs of Triangle-Free Graphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Gadgets, Approximation, and Linear Programming
• Problems and results on judicious partitions
• Maximizing Several Cuts Simultaneously
• Some optimal inapproximability results
• Some Extremal Properties of Bipartite Subgraphs
• MaxCut in ${\bm H)$-Free Graphs

This page was built for publication: Judicious partitions of directed graphs