The even‐path problem for graphs and digraphs

Andrea S. Lapaugh; Christos H. Papadimitriou

doi:10.1002/net.3230140403

The even‐path problem for graphs and digraphs

Andrea S. Lapaugh, Christos H. Papadimitriou

Computer Science

Research output: Contribution to journal › Article › peer-review

61 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 language	English (US)
Pages (from-to)	507-513
Number of pages	7
Journal	Networks
Volume	14
Issue number	4
DOIs	https://doi.org/10.1002/net.3230140403
State	Published - 1984

All Science Journal Classification (ASJC) codes

Information Systems
Computer Networks and Communications

Access to Document

10.1002/net.3230140403

Cite this

@article{1eb165da32814c97b934f24c774b49e2,

title = "The even‐path problem for graphs and digraphs",

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.",

author = "Lapaugh, {Andrea S.} and Papadimitriou, {Christos H.}",

year = "1984",

doi = "10.1002/net.3230140403",

language = "English (US)",

volume = "14",

pages = "507--513",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

T1 - The even‐path problem for graphs and digraphs

AU - Lapaugh, Andrea S.

AU - Papadimitriou, Christos H.

PY - 1984

Y1 - 1984

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0021691734&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021691734&partnerID=8YFLogxK

U2 - 10.1002/net.3230140403

DO - 10.1002/net.3230140403

M3 - Article

AN - SCOPUS:0021691734

SN - 0028-3045

VL - 14

SP - 507

EP - 513

JO - Networks

JF - Networks

IS - 4

ER -

The even‐path problem for graphs and digraphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this