On judicious bisections of graphs

DOI10.1016/j.jctb.2014.01.004zbMath1297.05194OpenAlexW2094939916MaRDI QIDQ402590

Xingxing Yu, Bao-Gang Xu

Publication date: 28 August 2014

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2014.01.004

zbMATH Keywords

judicious partitionbalanced partition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (28)

On judicious partitions of uniform hypergraphs ⋮ On judicious partitions of graphs ⋮ Judicious partitions of weighted hypergraphs ⋮ Biased partitions and judicious \(k\)-partitions of graphs ⋮ On judicious bipartitions of directed graphs ⋮ Bounds for pairs in judicious partitioning of graphs ⋮ Partitioning digraphs with outdegree at least 4 ⋮ On bisections of graphs without complete bipartite graphs ⋮ Graph partitioning: an updated survey ⋮ Bisections of Graphs Without Short Cycles ⋮ Partitioning dense uniform hypergraphs ⋮ Optimal bisections of directed graphs ⋮ The Bollobás--Scott Conjecture for 4-Uniform Hypergraphs ⋮ Judicious Partitioning of Hypergraphs with Edges of Size at Most 2 ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Maximum cuts in \(\mathscr{H} \)-free graphs ⋮ Bisections of graphs without \(K_{2, l}\) ⋮ Bounds for judicious balanced bipartitions of graphs ⋮ On bipartitions of directed graphs with small semidegree ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ Max-bisections of \(H\)-free graphs ⋮ Bipartitions of oriented graphs ⋮ Bipartition of graph under degree constraints ⋮ On partitions of \(K_{2, 3}\)-free graphs under degree constraints ⋮ On a Problem of Judiciousk-Partitions of Graphs ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Maximum bipartite subgraphs in graphs without short cycles ⋮ On bisections of directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bisections of graphs
• A note on balanced bipartitions
• Max \(k\)-cut and judicious \(k\)-partitions
• Judicious \(k\)-partitions of graphs
• On a bottleneck bipartition conjecture of Erdős
• Maximum cuts and judicious partitions in graphs without short cycles
• Exact bounds for judicious partitions of graphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Judicious partitions of bounded‐degree graphs
• Problems and results on judicious partitions
• Reducibility among Combinatorial Problems
• Balanced judicious bipartitions of graphs
• Better Bounds for k-Partitions of Graphs
• Node-and edge-deletion NP-complete problems
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• The RPR2 rounding technique for semidefinite programs
• Some Extremal Properties of Bipartite Subgraphs

This page was built for publication: On judicious bisections of graphs