Cutwidth II: Algorithms for partial w-trees of bounded degree

Dimitrios M. Thilikos, Maria Serna, Hans L. Bodlaender

Research output: Contribution to journalArticlepeer-review

Abstract

The cutwidth of a graph G is defined to be the smallest integer k such that the vertices of G can be arranged in a vertex ordering [v1,⋯,vn] in a way that, for every i=1,⋯,n-1, there are at most k edges with one endpoint in {v1,⋯,vi} and the other in {vi+1,⋯,vn}. We examine the problem of computing in polynomial time the cutwidth of a partial w-tree with bounded degree. In particular, we show how to construct an algorithm that, in nO(w2d) steps, computes the cutwidth of any partial w-tree with vertices of degree bounded by a fixed constant d. Our algorithm is constructive in the sense that it can be adapted to output a corresponding optimal vertex ordering. Also, it is the main subroutine of an algorithm computing the pathwidth of a bounded degree partial w-tree with the same time complexity.

Original languageEnglish (US)
Pages (from-to)25-49
Number of pages25
JournalJournal of Algorithms
Volume56
Issue number1
DOIs
StatePublished - Jul 2005

Keywords

  • Cutwidth
  • Graph layout
  • Pathwidth
  • Treewidth

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Cutwidth II: Algorithms for partial w-trees of bounded degree'. Together they form a unique fingerprint.

Cite this