Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs

DOI10.1006/jagm.1996.0049zbMath0861.68036WikidataQ29396868 ScholiaQ29396868MaRDI QIDQ4895809

Ton Kloks, Hans L. Bodlaender

Publication date: 11 May 1997

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://dspace.library.uu.nl/handle/1874/21989

zbMATH Keywords

pathwidth

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68W10: Parallel algorithms in computer science

Related Items

On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Computing the vertex separation of unicyclic graphs, The complexity of subgraph isomorphism for classes of partial k-trees, Treewidth for graphs with small chordality, Algorithms for generalized vertex-rankings of partial k-trees, Edge and node searching problems on trees, The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs, Algorithms and obstructions for linear-width and related search parameters, Counting \(H-\)colorings of partial \(k-\)trees, Embeddings of \(k\)-connected graphs of pathwidth \(k\), The parametrized complexity of knot polynomials, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors