The bisection width of cubic graphs

DOI10.1017/S0004972700003300MaRDI QIDQ4729817zbMATH OpenFDO

Authors R. C. Entringer, Lane Clark

Publication date 1989

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

Full work available at URL https://doi.org/10.1017/S0004972700003300

zbMATH Keywords

bisection algorithmsgraph partitioningminimal 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)

Recommendations

• scientific article; zbMATH DE number 125467
• On the minimum bisection of random 3-regular graphs
• Note on the bisection width of cubic graphs
• scientific article; zbMATH DE number 1834674
• Bounds on the bisection width for random \(d\)-regular graphs

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• A framework for solving VLSI graph layout problems
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• An Efficient Heuristic Procedure for Partitioning Graphs
• Eigenvalues and expanders
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• The asymptotic number of labeled graphs with given degree sequences

Cited in

(17)

• Bisection width of transposition graphs
• Note on the bisection width of cubic graphs
• Bounds on the bisection width for random \(d\)-regular graphs
• Minimal 2-connected graphs satisfying the even cut condition
• Full friendly index set. I
• scientific article; zbMATH DE number 125467 (Why is no real title available?)
• scientific article; zbMATH DE number 2019629 (Why is no real title available?)
• scientific article; zbMATH DE number 1834674 (Why is no real title available?)
• Communication throughput of interconnection networks
• LATIN 2004: Theoretical Informatics
• On the minimum bisection of random 3-regular graphs
• On minimum vertex bisection of random \(d\)-regular graphs
• Minimum bisections of graphs without even cycles
• Cuts, cats, and complete graphs
• Reconfigurable routing in data center networks
• Upper bounds on the bisection width of 3- and 4-regular graphs
• Satisfactory graph partition, variants, and generalizations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4729817)