Digital Signal Processing Reference
In-Depth Information
THE DAG-COMPARE ALGORITHM
This section presents a polynomial-time algorithm for path matching
between two DAG
o
s called DAG-Compare where we find the two paths
for each DAG
o
s that maximize the function PathScore from Eq. 5.2.
The matching score between two paths can be solved in quadratic time
[Cormen et al., 1990]. All pairs of paths between two DAG may be
compared via dynamic programming (DP) in quadratic time.
For DP, we identify subproblems associated with this problem: the
function score(
u
1
,
u
2
) returns the set of all path scores for one path that
goes from source and to a node
u
1
in one DAG
o
and another that goes
from source to a node
u
2
in the another DAG
o
. We can describe this
set of scores in terms of the recurrence relation with MatchEdge.
(
)
V
(
e
1
),
∪
{
MatchEdge
}
score
(
v
1
,
v
2
)
e
1
(5.4)
V
(
e
2
),
c
InEdges
(
v
1
),
e
2
InEdges
(
v
2
),
score
(Prev(
e
1
), Prev(
e
2
))
where
InEdges
(
v
) are the set of edges going into node
v
, the func-
tion V returns the edge value of a given edge, and the function Prev
returns node that an edge leaves. The DAG-Compare algorithm finds
max(
score
(
s
1
,
s
2
)) where
s
1
and
s
2
are the sinks of two DAGs. The so-
lution to the current subproblem can be reached by traversing at most
one edge in each graph from a previous subproblem. To find maximum
of this set, this formulation still leads to a possibly exponential time
computation. By using MatchEdge's monotonicity, we can simplify the
equation for the maximum of a given score set:
c
max(
score
(
v
1
,
v
2
)) = max
(5.5)
where
c
(
e
1
,
e
2
) = max(
score
(Prev(
e
1
), Prev(
e
2
)))
By the dynamic programming principle, we recognize that only the max-
imum score needs to be remembered at any previous step.
There exists an order of solving the maximum of the score sets that
preserves these edge dependencies, i.e., all computation of previous scores
Search WWH ::
Custom Search