A polynomial-time algorithm for finding regular simple paths in outerplanar graphs

摘要

Let G be a labeled directed graph with are labels drawn from alphabet Sigma, R be a regular expression over Sigma, and x and y be a pair of nodes from G. The regular simple path (RSP) problem is to determine whether there is a simple path p in G from x to y, such that the concatenation of are labels along p satisfies R. Although RSP is known to be NP-hard in general, we show that it is solvable in polynomial time when G is outerplanar. The proof proceeds by presenting an algorithm which gives a polynomial-time reduction of RSP for outerplanar graphs to RSP for directed acyclic graphs, a problem which has been shown to be solvable in polynomial time. (C) 2000 Academic Press. [References: 6]