Tree decompositions with small cost

DOI10.1016/J.DAM.2004.01.008MaRDI QIDQ1764801zbMATH OpenOpenAlexWikidataFDO

Authors Hans L. Bodlaender, Fedor V. Fomin

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)

Recommendations

• Tree Decompositions with Small Cost
• Minimum size tree-decompositions
• Minimum size tree-decompositions
• Algorithms finding tree-decompositions of graphs
• Publication:4944975

Cites work

• scientific article; zbMATH DE number 1634667 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 19874 (Why is no real title available?)
• scientific article; zbMATH DE number 1500539 (Why is no real title available?)
• scientific article; zbMATH DE number 4121482 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth
• Algorithmic Aspects of Vertex Elimination on Graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Complexity of Finding Embeddings in a k-Tree
• Graph Classes: A Survey
• How to use the minimal separators of a graph for its chordal triangulation
• Memory requirements for table computations in partial k-tree algorithms
• On rigid circuit graphs
• On the hardness of approximate reasoning
• The Pathwidth and Treewidth of Cographs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Tree-decompositions of small pathwidth
• Treewidth and minimum fill-in: Grouping the minimal separators

Cited in

(16)

• scientific article; zbMATH DE number 7310159 (Why is no real title available?)
• On tradeoffs between width- and fill-like graph parameters
• Uniform Constraint Satisfaction Problems and Database Theory
• Approximately counting locally-optimal structures
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• Minimum size tree-decompositions
• Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm
• Tree decompositions of graphs: saving memory in dynamic programming
• scientific article; zbMATH DE number 1420905 (Why is no real title available?)
• Seeing Arboretum for the (partial k-) Trees
• Tree Decompositions with Small Cost
• A faster tree-decomposition based algorithm for counting linear extensions
• A faster tree-decomposition based algorithm for counting linear extensions
• A revisit of the scheme for computing treewidth and minimum fill-in
• Approximately Counting Locally-Optimal Structures
• Minimum size tree-decompositions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1764801)