Simultaneous time-space upper bounds for red-blue path problem in planar DAGs

DOI10.1007/978-3-319-15612-5_23MaRDI QIDQ5176589zbMATH OpenOpenAlexFDO

Authors Diptarka Chakraborty, Raghunath Tewari

Publication date 27 February 2015

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-15612-5_23

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On finding rainbow and colorful paths
• \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability
• Finding an Even Simple Path in a Directed Planar Graph
• An $$O(n^{\epsilon })$$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
• The even-path problem for graphs and digraphs

Cited in

(2)

• EvenPath in directed single-crossing graphs
• The Even-Path problem in directed single-crossing-minor-free graphs

This page was built for publication: Simultaneous time-space upper bounds for red-blue path problem in planar DAGs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5176589)