Balanced judicious bipartitions of graphs

DOI10.1002/JGT.20421zbMath1215.05093OpenAlexW4251622426MaRDI QIDQ5190331

Juan Yan, Xingxing Yu, Bao-Gang Xu

Publication date: 15 March 2010

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20421

zbMATH Keywords

minimum degreemaximum degreejudicious partitionbalanced partition

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

Related Items (19)

Judicious bisection of hypergraphs ⋮ Judicious partitions of weighted hypergraphs ⋮ Biased partitions and judicious \(k\)-partitions of graphs ⋮ On judicious bipartitions of directed graphs ⋮ On bisections of graphs without complete bipartite graphs ⋮ On judicious bisections of graphs ⋮ Upper bounds on minimum balanced bipartitions ⋮ Graph partitioning: an updated survey ⋮ Bisections of Graphs Without Short Cycles ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Bisections of graphs without \(K_{2, l}\) ⋮ Bounds for judicious balanced bipartitions of graphs ⋮ A note on balanced bipartitions ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ Simple probabilistic analysis to generalize bottleneck graph multi-partitioning ⋮ Bipartitions of oriented graphs ⋮ Bipartition of graph under degree constraints ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ On bisections of directed graphs

Cites Work

• Judicious \(k\)-partitions of graphs
• On a bottleneck bipartition conjecture of Erdős
• Exact bounds for judicious partitions of graphs
• Some Extremal Properties of Bipartite Subgraphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Balanced judicious bipartitions of graphs