Simple probabilistic analysis to generalize bottleneck graph multi-partitioning

DOI10.1016/j.aml.2012.04.015zbMath1251.05144OpenAlexW2062775464MaRDI QIDQ714518

Fang Tian, Zi-Long Liu

Publication date: 11 October 2012

Published in: Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aml.2012.04.015

zbMATH Keywords

probabilitybottleneckAzuma-Hoeffding inequalitymulti-partitioning

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• On several partitioning problems of Bollobás and Scott
• Partitioning 3-uniform hypergraphs
• Bounds for pairs in partitions of graphs
• Judicious \(k\)-partitions of graphs
• On a bottleneck bipartition conjecture of Erdős
• Judicious partitions of hypergraphs
• Improved approximations for max set splitting and max NAE SAT
• Exact bounds for judicious partitions of graphs
• Approximation algorithms for maximum cut with limited unbalance
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• Problems and results on judicious partitions
• Balanced judicious bipartitions of graphs
• Better Bounds for k-Partitions of Graphs
• Segmentation problems

This page was built for publication: Simple probabilistic analysis to generalize bottleneck graph multi-partitioning