Tree decompositions with small cost

DOI10.1016/j.dam.2004.01.008zbMath1084.05057OpenAlexW2047033531WikidataQ59567852 ScholiaQ59567852MaRDI QIDQ1764801

Fedor V. Fomin, Hans L. Bodlaender

Publication date: 22 February 2005

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

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

zbMATH Keywords

TriangulationTreewidthMinimal separatorProbabilistic networkTreecost

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (13)

Seeing Arboretum for the (partial k-) Trees ⋮ Approximately counting locally-optimal structures ⋮ Approximately Counting Locally-Optimal Structures ⋮ A revisit of the scheme for computing treewidth and minimum fill-in ⋮ Solving Graph Problems via Potential Maximal Cliques ⋮ Tree decompositions of graphs: saving memory in dynamic programming ⋮ A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ Unnamed Item ⋮ A faster tree-decomposition based algorithm for counting linear extensions ⋮ Uniform Constraint Satisfaction Problems and Database Theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• A partial k-arboretum of graphs with bounded treewidth
• Memory requirements for table computations in partial \(k\)-tree algorithms
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• On the hardness of approximate reasoning
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• A Linear Recognition Algorithm for Cographs
• Complexity of Finding Embeddings in a k-Tree
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• How to use the minimal separators of a graph for its chordal triangulation
• The Pathwidth and Treewidth of Cographs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Tree-decompositions of small pathwidth

This page was built for publication: Tree decompositions with small cost