Decomposition Techniques for Subgraph Matching

Details Decomposition Techniques for Subgraph Matching Decomposition Techniques for Subgraph Matching

2008-05-07

arxiv.org/abs/0805.1030v1

Computer Science

Computational Complexity

15 pages

Scientific paper

In the constraint programming framework, state-of-the-art static and dynamic decomposition techniques are hard to apply to problems with complete initial constraint graphs. For such problems, we propose 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 precompute 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 decomposition method solves more instances than dedicated, state-of-the-art matching algorithms or standard constraint programming approaches.

Affiliated with

Also associated with

No associations

Rating

Decomposition Techniques for Subgraph Matching does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Decomposition Techniques for Subgraph Matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decomposition Techniques for Subgraph Matching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-491771