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 programmingsatisfactiontree decompositionfrequency assignmentMAX-SATpartial constraint

Mathematics Subject Classification ID

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

Recommendations

• Publication:3489491
• 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

(19)

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

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)