Tree-decompositions of small pathwidth

DOI10.1016/j.dam.2004.01.012zbMath1067.68108OpenAlexW2036618810MaRDI QIDQ5916128

Jan Arne Telle

Publication date: 22 February 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.01.012

zbMATH Keywords

graph algorithmtreewidthpathwidthmemory usage

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Induced Separation Dimension ⋮ A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth ⋮ The induced separation dimension of a graph ⋮ Minimum reload cost graph factors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. I. Excluding a forest
• All structured programs have small tree width and good register allocation
• The vertex separation and search number of a graph
• Obstruction set isolation for the gate matrix layout problem
• Triangulating multitolerance graphs
• Memory requirements for table computations in partial \(k\)-tree algorithms
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Triangulating graphs without asteroidal triples
• Representation of a finite graph by a set of intervals on the real line
• Complexity of Finding Embeddings in a k-Tree
• Asteroidal Triple-Free Graphs
• The Pathwidth and Treewidth of Cographs

This page was built for publication: Tree-decompositions of small pathwidth