Weighted hierarchical alignment of directed acyclic graph

Details Weighted hierarchical alignment of directed acyclic graph Weighted hierarchical alignment of directed acyclic graph

2006-06-29

arxiv.org/abs/cs/0606124v2

Computer Science

Data Structures and Algorithms

Scientific paper

In some applications of matching, the structural or hierarchical properties of the two graphs being aligned must be maintained. The hierarchical properties are induced by the direction of the edges in the two directed graphs. These structural relationships defined by the hierarchy in the graphs act as a constraint on the alignment. In this paper, we formalize the above problem as the weighted alignment between two directed acyclic graphs. We prove that this problem is NP-complete, show several upper bounds for approximating the solution, and finally introduce polynomial time algorithms for sub-classes of directed acyclic graphs.

Affiliated with

Also associated with

No associations

Rating

Weighted hierarchical alignment of directed acyclic graph 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 Weighted hierarchical alignment of directed acyclic graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Weighted hierarchical alignment of directed acyclic graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-597808