Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a directed acyclic graph G and a path made up from its set of nodes N, what is the closest approximate match to N, equipped with an intuitive notion of distance?

A path in a directed acyclic graph is essentially a string (that uses the set of nodes as the alphabet), so when comparing paths one can make use of edit distances developed for approximate string matching:

There are many algorithms for approximate string matching:

http://en.wikipedia.org/wiki/Approximate_string_matching

This string matching answers the question when the G itself is also a path.. then we're merely asking to compare two strings.

Asking if an arbitrary graph A built from the same set of nodes is a sub-graph of G is the general case of the problem, but I'm only interested in the case where A is a path and G is directed & acyclic.

Any general pointers are also welcome.

--

Edit: I ended up using a dynamic programming algorithm, independently also suggested in the accepted answer. Good call! It is probably the most accurate option as well, and barely more "complex" than the string-to-string case when the average # of edges per node is low.

share|improve this question

closed as off-topic by Andres Caicedo, Ryan Budney, David White, Andrey Rekalo, Chris Godsil Jul 22 '13 at 11:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Andres Caicedo, Ryan Budney, David White, Andrey Rekalo, Chris Godsil
If this question can be reworded to fit the rules in the help center, please edit the question.

3  
for q1, I'm not seeing the problem. given the sequence of nodes in the path, why can't you just verify that directed edges exist between each adjacent pair of nodes ? –  Suresh Venkat May 27 '10 at 1:09
    
good point, I guess q2 is what I'd like know more about. –  Deniz May 27 '10 at 3:53
add comment

1 Answer 1

up vote 1 down vote accepted

If graph is acyclic you can use some sort of dynamic programming. Let $a_{u,k}$ be the best distance you can get if you start from vertex $u \in G$ and consider only $k$ last vertices of your given path.

It's quite straightforward how to calculate all $a_{u,k}$ based on all values of $a_{u',k'}$ with $u'$ "after" $u$ and $k' < k$: you just iterate over all edges going from vertex $u$.

This approach works in $O(|G| \times strlen)$ time.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.