Upper bounds on the bisection width of 3- and 4-regular graphs
type: Item
instance of: scholarly article
title: Upper bounds on the bisection width of 3- and 4-regular graphs
zbMATH Open document ID: 1103.05042
author: Robert Preis
author: Burkhard Monien
published in: Journal of Discrete Algorithms
publication date: 2006-10-31T00:00:00Z
review text: New upper bounds are obtained for the bisection width of graphs that have a regular vertex degree. It is shown that the bisection width of sufficiently large 3-regular graphs with \(| V| \) vertices is at most \(( \frac{1}{6}+\varepsilon) | V| \), with \(\varepsilon >0\). For the bisection width of sufficiently large 4-regular graphs it is shown that \((\frac{2}{5}+\varepsilon) | V| \) is an upper bound, with \(\varepsilon >0\).
reviewed by: Giacomo Bonanno
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5069051
zbMATH Keywords: graph partitioning
describes a project that uses: METIS
describes a project that uses: PARTY
describes a project that uses: Scotch
describes a project that uses: JOSTLE
describes a project that uses: Chaco
MaRDI profile type: Publication
full work available at URL: j.jda.2005.12.009
OpenAlex ID: W2055190409
cites work: On the Edge-Expansion of Graphs
cites work: Q2766666
cites work: On the bisection width and expansion of butterfly networks
cites work: The isoperimetric number of random regular graphs
cites work: The bisection width of cubic graphs
cites work: Cubic Ramanujan graphs
cites work: Q4859012
cites work: Q3877805
cites work: A polylogarithmic approximation of the minimum bisection
cites work: Some simplified NP-complete graph problems
cites work: Q5286666
cites work: Q4027167
cites work: Q4321509
cites work: Ramanujan graphs
cites work: Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
cites work: Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
cites work: Q4779170
cites work: Quality matching and local improvement for multilevel graph-partitioning
cites work: Q4409104
DOI: 10.1016/J.JDA.2005.12.009
description: scientific article; zbMATH DE number 5069051