The even‐path problem for graphs and digraphs

Andrea S. Lapaugh, Christos H. Papadimitriou

Research output: Contribution to journalArticle

45 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)507-513
Number of pages7
JournalNetworks
Volume14
Issue number4
DOIs
StatePublished - Jan 1 1984

All Science Journal Classification (ASJC) codes

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

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

  • Cite this

    Lapaugh, A. S., & Papadimitriou, C. H. (1984). The even‐path problem for graphs and digraphs. Networks, 14(4), 507-513. https://doi.org/10.1002/net.3230140403