Published in

Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93

DOI: 10.1145/167088.167161

Society for Industrial and Applied Mathematics, SIAM Journal on Computing, 6(25), p. 1305-1317

DOI: 10.1137/s0097539793251219

Links

Tools

Export citation

Search in Google Scholar

A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

Journal article published in 1993 by Hans L. Bodlaender ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

In this paper, we give, for constant k, a linear time algorithm, that given a graph G = (V; E), determines whether the treewidth of G is at most k, and if so, finds a tree-decomposition of G with treewidth at most k. A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear time recognition algorithm. Another consequence is that a similar result holds when we look instead for path-decompositions with pathwidth at most some constant k.