View Related Documents

Abstract

We derive new upper bounds on the bisection width of graphs which have a regular vertex degree. We show that the bisection width of large 3-regular graphs with ∣V∣ vertices is at most 1/6∣V∣. For the bisection width of large 4-regular graphs we show an upper bound of 2/5 ∣V∣.

Keywords  graph partitioning - bisection width - regular graphs - local improvement

Fulltext Preview

Image of the first page of the fulltext document