Published in

Elsevier, Journal of Algorithms in Cognition, Informatics and Logic, 2(21), p. 358-402

DOI: 10.1006/jagm.1996.0049

Links

Tools

Export citation

Search in Google Scholar

Efficient and constructive algorithms for the pathwidth and treewidth of graphs

Journal article published in 1993 by Hl Hans Bodlaender, Hans L. Bodlaender ORCID, Ajj Ton Kloks
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

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

Abstract

In this paper we give, for all constants k, l , explicit algorithms, that given a graph G = (V, E) with a tree-decomposition of G with treewidth at most l, decide whether the treewidth (or pathwidth) of G is at most k, and if so, find a tree-decomposition or (path-decomposition) of G of width at most k, and that use O(|V|) time. In contrast with previous solutions, our algorithms do not rely on non-constructive reasoning, and are single exponential in k and l. This result can be combined with a result of Reed [37], yielding explicit O(n log n) algorithms for the problem, given a graph G, to determine whether the treewidth (or pathwidth) of G is at most k, and if so, to find a tree- (or path-)decomposition of width at most k (k constant). Also, Bodlaender [13] has used the result of this paper to obtain linear time algorithms for these problems. We also show that for all constants k, there exists a polynomial time algorithm, that, when given a graph G = (V, E) with treewidth ≤ k, computes the pathwidth of G and a path-decomposition of G of minimum width.