Safe reduction rules for weighted treewidth

DOI10.1007/s00453-006-1226-xzbMath1108.68091OpenAlexW2122238039WikidataQ59567787 ScholiaQ59567787MaRDI QIDQ870458

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

Publication date: 12 March 2007

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

probabilistic networks

Mathematics Subject Classification ID

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

Related Items (13)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs ⋮ 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 ⋮ The tree-width of C ⋮ Weighted Treewidth Algorithmic Techniques and Results ⋮ Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization ⋮ Tractable answer-set programming with weight constraints: bounded treewidth is not enough ⋮ Towards fixed-parameter tractable algorithms for abstract argumentation ⋮ Bounded treewidth as a key to tractability of knowledge representation and reasoning ⋮ On the maximum cardinality search lower bound for treewidth ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ On sparsification for computing treewidth

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