Name
Abstract | ||
|---|---|---|
In the constraint programming framework, state-of-the-art static and dynamic decomposition techniques are hard to apply to prob- lems with complete initial constraint graphs. For such problems, we pro- pose a hybrid approach of these techniques in the presence of global constraints. In particular, we solve the subgraph isomorphism problem. Further we design specific heuristics for this hard problem, exploiting its special structure to achieve decomposition. The underlying idea is to pre- compute a static heuristic on a subset of its constraint network, to follow this static ordering until a first problem decomposition is available, and to switch afterwards to a fully propagated, dynamically decomposing search. Experimental results show that, for sparse graphs, our decom- position method solves more instances than dedicated, state-of-the-art matching algorithms or standard constraint programming approaches. |
Year | Venue | Keywords |
|---|---|---|
2008 | Clinical Orthopaedics and Related Research | constraint programming,computational complexity |
Field | DocType | Volume |
Constraint satisfaction,Discrete mathematics,Combinatorics,Constraint programming,Constraint graph,Decomposition method (constraint satisfaction),Constraint satisfaction dual problem,Constraint logic programming,Subgraph isomorphism problem,Mathematics,Hybrid algorithm (constraint satisfaction) | Journal | abs/0805.1 |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Zampelli | 1 | 44 | 3.37 |
| Martin Mann | 2 | 130 | 9.59 |
| Yves Deville | 3 | 987 | 110.84 |
| Rolf Backofen | 4 | 1213 | 104.30 |