Upper bounds on the bisection width of 3- and 4-regular graphs

DOI10.1016/j.jda.2005.12.009zbMath1103.05042OpenAlexW2055190409MaRDI QIDQ849636

Robert Preis, Burkhard Monien

Publication date: 31 October 2006

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2005.12.009

zbMATH Keywords

graph partitioning

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (9)

Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ Organisational hierarchy constructions with easy Kuramoto synchronisation ⋮ Properties of regular graphs with large girth via local algorithms ⋮ A faster polynomial-space algorithm for Max 2-CSP ⋮ Linear-programming design and analysis of fast algorithms for Max 2-CSP ⋮ Note on the bisection width of cubic graphs ⋮ Satisfactory graph partition, variants, and generalizations ⋮ Minimal selectors and fault tolerant networks ⋮ Minimum Power Dominating Sets of Random Cubic Graphs

Uses Software

• METIS
• JOSTLE
• Scotch
• Chaco
• PARTY

Cites Work

• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Ramanujan graphs
• The isoperimetric number of random regular graphs
• Cubic Ramanujan graphs
• Some simplified NP-complete graph problems
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• On the bisection width and expansion of butterfly networks
• Quality matching and local improvement for multilevel graph-partitioning
• A Polylogarithmic Approximation of the Minimum Bisection
• On the Edge-Expansion of Graphs
• The bisection width of cubic graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Upper bounds on the bisection width of 3- and 4-regular graphs