2015/02/07 by Diptarka Chakraborty, Chakraborty, Diptarka, Raghunath Tewari +1
Computer Science · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1502.02135
openalex publication_date 2015/02/07 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
In this paper, we show that given a weighted, directed planar graph G, and any ε>0, there exists a polynomial time and O(n(1)/(2)+ε) space algorithm that computes the shortest path between two fixed vertices in G. We also consider the \RB 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 \RB problem in planar DAGs is \NL-complete. We exhibit a polynomial time and O(n(1)/(2)+ε) space algorithm (for any ε>0) for the \RB problem in planar DAG. In the last part of this paper, we consider the problem of deciding and constructing the perfect matching present in a planar bipartite graph and also a similar problem which is to find a Hall-obstacle in a planar bipartite graph. We show the time-space bound of these two problems are same as the bound of shortest path problem in a directed planar graph.