Finding an Even Simple Path in a Directed Planar Graph

DOI10.1137/S0097539797330343MaRDI QIDQ4943840zbMATH OpenOpenAlexFDO

Authors Zhivko Nedev

Publication date 19 March 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539797330343

zbMATH Keywords

NP-completenessplanar graphspolynomial-time algorithmsregular expressionssimple pathslabeled directed graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The even-path problem for graphs and digraphs
• Finding an induced path of given parity in planar graphs in polynomial time
• A simple solution to the two paths problem in planar graphs
• A linear-time algorithm for edge-disjoint paths in planar graphs
• Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^{2} n)\)-time algorithm

Cited in

(7)

• Simultaneous time-space upper bounds for red-blue path problem in planar DAGs
• A trichotomy for regular simple path queries on graphs
• EvenPath in directed single-crossing graphs
• Finding an induced path of given parity in planar graphs in polynomial time
• The Even-Path problem in directed single-crossing-minor-free graphs
• The even-path problem for graphs and digraphs
• A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs

This page was built for publication: Finding an Even Simple Path in a Directed Planar Graph

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