Solving partial constraint satisfaction problems with tree decomposition

DOI10.1002/NET.10046MaRDI QIDQ4785233zbMATH OpenOpenAlexFDO

Authors Arie M. C. A. Koster, Stan Van Hoesel, Antoon W. J. Kolen

Publication date 17 December 2002

Published in Networks (Search for Journal in Brave)

Full work available at URL https://cris.maastrichtuniversity.nl/en/publications/b7af3f17-3aec-4858-a7fc-592a49b9343e

zbMATH Keywords

dynamic programmingfrequency assignmentMAX-SATpartial constraintsatisfactiontree decomposition

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Recommendations

• scientific article; zbMATH DE number 4162300
• Solving frequency assignment problems via tree-decomposition
• Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
• Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
• A comparison of structural CSP decomposition methods

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Solving frequency assignment problems via tree-decomposition

Cited in

(21)

• The partial constraint satisfaction problem: Facets and lifting theorems
• Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
• A branch-and-price-and-cut method for computing an optimal bramble
• Tree decompositions of graphs: saving memory in dynamic programming
• Tree decomposition and discrete optimization problems: a survey
• The \(k\)-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing
• A c^k n 5-approximation algorithm for treewidth
• Fixed-parameter tractability of treewidth and pathwidth
• Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
• scientific article; zbMATH DE number 4162300 (Why is no real title available?)
• D-FLAT: declarative problem solving using tree decompositions and answer-set programming
• Tree decompositions and social graphs
• Generalized partial computation using disunification to solve constraints
• Models and solution techniques for frequency assignment problems
• Tangle bases: Revisited
• Multi-neighborhood simulated annealing for the minimum interference frequency assignment problem
• On the complexity of winner determination and strategic control in conditional approval voting
• Safe separators for treewidth
• Treewidth computations. I: Upper bounds
• A comparison of problem decomposition techniques for the FAP
• On the maximum cardinality search lower bound for treewidth

Describes a project that uses

Uses Software

• CALMA
• DIMACS

This page was built for publication: Solving partial constraint satisfaction problems with tree decomposition

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