Advertisement
Published in:
2015 | OriginalPaper | Chapter
Simultaneous Time-Space Upper Bounds for Red-Blue Path Problem in Planar DAGs
Authors : Diptarka Chakraborty, Raghunath Tewari
Published in: WALCOM: Algorithms and Computation
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper, we consider the
RedBluePath
problem, which states that given a graph
G
whose edges are colored either red or blue and two fixed vertices
s
and
t
in
G
, is there a path from
s
to
t
in
G
that alternates between red and blue edges. The
RedBluePath
problem in planar DAGs is
NL
-complete. We exhibit a polynomial time and
$O(n^{\frac{1}{2}+\epsilon})$
space algorithm (for any
ε
> 0) for the
RedBluePath
problem in planar DAG. We also consider a natural relaxation of
RedBluePath
problem, denoted as
EvenPath
problem. The
EvenPath
problem in DAGs is known to be
NL
-complete. We provide a polynomial time and
$O(n^{\frac{1}{2}+\epsilon})$
space (for any
ε
> 0) bound for
EvenPath
problem in planar DAGs.