Finding an even simple path in a directed planar graph

Finding an even simple path in a directed planar graph

0.00 Avg rating—0 Votes
Article ID: iaor2001495
Country: United States
Volume: 29
Issue: 2
Start Page Number: 685
End Page Number: 695
Publication Date: Oct 1999
Journal: SIAM Journal On Computing
Authors:
Abstract:

In this paper we show that the following problem, the even simple path (ESP) problem for directed planar graphs, is solvable in polynomial time: Given: a directed planar graph G = (V,E) and two nodes s (startingnode), t (targetnode) ∈ V; Find: a simple path (i.e., without repeated nodes) from s to t of even length. (The length of the path is the number of edges it contains.)

Reviews

Required fields are marked *. Your email address will not be published.