Publication | Closed Access
The even‐path problem for graphs and digraphs
73
Citations
6
References
1984
Year
Directed GraphEngineeringPathfindingNetwork AnalysisEducationComputational ComplexityGraph ProcessingStructural Graph TheoryPath ProblemsEven‐path ProblemDiscrete MathematicsCombinatorial OptimizationGraph AlgorithmsDirected GraphsSimple Linear‐time AlgorithmGraph AlgorithmNetwork ScienceGraph TheoryNetwork AlgorithmEven‐length Simple Paths
Abstract We give a simple linear‐time algorithm for finding even‐length simple paths between two specified nodes of a given graph. We show that the same problem for directed graphs is NP‐complete.
| Year | Citations | |
|---|---|---|
Page 1
Page 1