Safe reduction rules for weighted treewidth

DOI10.1007/S00453-006-1226-XMaRDI QIDQ870458zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Frank van den Eijkhof, Hans L. Bodlaender, M. C. A. Koster

Publication date 12 March 2007

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-006-1226-x

zbMATH Keywords

probabilistic networks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 1953092
• Safe separators for treewidth
• Weighted Treewidth Algorithmic Techniques and Results
• Reduction algorithms for graphs of small treewidth
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization

Cited in

(14)

• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
• Towards fixed-parameter tractable algorithms for abstract argumentation
• Safe separators for treewidth
• On the maximum cardinality search lower bound for treewidth
• Weighted Treewidth Algorithmic Techniques and Results
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• An extended depth-first search algorithm for optimal triangulation of Bayesian networks
• scientific article; zbMATH DE number 1953092 (Why is no real title available?)
• The tree-width of C
• Tractable answer-set programming with weight constraints: bounded treewidth is not enough
• Updating credal networks is approximable in polynomial time
• Fixed-parameter tractability of treewidth and pathwidth

This page was built for publication: Safe reduction rules for weighted treewidth

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