Bounds for pairs in judicious partitioning of graphs

DOI10.1002/rsa.20642zbMath1352.05150OpenAlexW2290912581MaRDI QIDQ2951883

Jian-Feng Hou, Geng-Hua Fan

Publication date: 10 January 2017

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

Full work available at URL: https://doi.org/10.1002/rsa.20642

zbMATH Keywords

Azuma-Hoeffding inequalityChernoff inequalityjudicious partitioning

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

Biased partitions and judicious \(k\)-partitions of graphs ⋮ On judicious bipartitions of directed graphs ⋮ 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 ⋮ Bisections of graphs without \(K_{2, l}\) ⋮ On bipartitions of directed graphs with small semidegree ⋮ Bipartitions of oriented graphs ⋮ On partitions of \(K_{2, 3}\)-free graphs under degree constraints ⋮ A bound on judicious bipartitions of directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On judicious bisections of graphs
• Bisections of graphs
• A bound for judicious \(k\)-partitions of graphs
• On several partitioning problems of Bollobás and Scott
• Bounds for pairs in partitions of graphs
• Judicious \(k\)-partitions of graphs
• Bipartite density of triangle-free subcubic graphs
• Judicious partitions of hypergraphs
• Maximum cuts and judicious partitions in graphs without short cycles
• Connected components in random graphs with given expected degree sequences
• Exact bounds for judicious partitions of graphs
• Triangle-free subcubic graphs with minimum bipartite density
• Weighted sums of certain dependent random variables
• Bipartite subgraphs
• Problems and results on judicious partitions
• Better Bounds for k-Partitions of Graphs
• Probability Inequalities for Sums of Bounded Random Variables
• Some Extremal Properties of Bipartite Subgraphs

This page was built for publication: Bounds for pairs in judicious partitioning of graphs