The even‐path problem for graphs and digraphs

Andrea S. Lapaugh, Christos H. Papadimitriou

Research output: Contribution to journalArticlepeer-review

55 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)507-513
Number of pages7
Issue number4
StatePublished - 1984

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'The even‐path problem for graphs and digraphs'. Together they form a unique fingerprint.

Cite this