The bisection width of cubic graphs

DOI10.1017/S0004972700003300zbMath0681.05040MaRDI QIDQ4729817

Roger Entringer, Lane H. Clark

Publication date: 1989

Published in: Bulletin of the Australian Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

graph partitioningbisection algorithmsminimal cut

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Related Items (7)

Upper bounds on the bisection width of 3- and 4-regular graphs ⋮ Minimal 2-connected graphs satisfying the even cut condition ⋮ Full friendly index set. I ⋮ Communication throughput of interconnection networks ⋮ On the minimum bisection of random 3-regular graphs ⋮ Note on the bisection width of cubic graphs ⋮ Satisfactory graph partition, variants, and generalizations

Cites Work

• Unnamed Item
• A framework for solving VLSI graph layout problems
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Eigenvalues and expanders
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• An Efficient Heuristic Procedure for Partitioning Graphs

This page was built for publication: The bisection width of cubic graphs