The even-path problem for graphs and digraphs

DOI10.1002/NET.3230140403MaRDI QIDQ3345793zbMATH OpenOpenAlexFDO

Authors Andrea S. LaPaugh, Christos Papadimitriou

Publication date 1984

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230140403

zbMATH Keywords

NP-completelinear-time algorithmeven-length simple paths

Mathematics Subject Classification ID

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

Recommendations

• Finding an Even Simple Path in a Directed Planar Graph
• scientific article; zbMATH DE number 3974318
• scientific article; zbMATH DE number 3876619
• An extension to ‘an algorithm for rinding a circuit of even length in a directed graph’
• scientific article; zbMATH DE number 3876620

Cites work

• A Polynomial Solution to the Undirected Two Paths Problem
• Paths, Trees, and Flowers

Cited in

(35)

• scientific article; zbMATH DE number 867679 (Why is no real title available?)
• Simultaneous time-space upper bounds for red-blue path problem in planar DAGs
• Quick but odd growth of cacti
• Finding a shortest non-zero path in group-labeled graphs
• How many attackers can selfish defenders catch?
• Evaluation and enumeration problems for regular path queries
• A trichotomy for regular simple path queries on graphs
• scientific article; zbMATH DE number 3231691 (Why is no real title available?)
• A note on odd/even cycles
• The Even Cycle Problem for Planar Digraphs
• Odd paths, cycles, and T-joins: connections and algorithms
• Search-space reduction via essential vertices
• DFS tree construction: Algorithms and characterizations
• Graphs and complete intersection toric ideals
• A Trichotomy for Regular Trail Queries
• Shortest odd paths in undirected graphs with conservative weight functions
• 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
• An extension to ‘an algorithm for rinding a circuit of even length in a directed graph’
• Modern techniques for querying graph-structured databases
• Problems on group-labeled matroid bases
• Understanding the complexity of axiom pinpointing in lightweight description logics
• scientific article; zbMATH DE number 3922696 (Why is no real title available?)
• Odd Multiway Cut in Directed Acyclic Graphs
• Backdoors to tractable answer set programming
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• Finding an Even Simple Path in a Directed Planar Graph
• Handling controversial arguments
• LP extreme points and cuts for the fixed-charge network design problem
• An efficient Dijkstra-like labeling method for computing shortest odd/even paths
• Redundancy in logic. II: 2CNF and Horn propositional formulae
• Odd multiway cut in directed acyclic graphs
• Finding induced paths of given parity in claw-free graphs
• Finding a shortest non-zero path in group-labeled graphs via permanent computation

This page was built for publication: The even-path problem for graphs and digraphs

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