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

(15)

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

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)