On negative cycles in mixed graphs

Esther M. Arkin; Christos H. Papadimitriou

doi:10.1016/0167-6377(85)90013-6

On negative cycles in mixed graphs

Esther M. Arkin
, Christos H. Papadimitriou

Applied Mathematics and Statistics

Stanford University

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

5 Scopus citations

Abstract

We show that, for mixed graphs, i.e., graphs having both directed and undirected edges, with a length function defined on the edges, the problems of detecting negative cycles and of finding the shortest path in the absence of negative cycles are NP-complete.

Original language	English
Pages (from-to)	113-116
Number of pages	4
Journal	Operations Research Letters
Volume	4
Issue number	3
DOIs	https://doi.org/10.1016/0167-6377(85)90013-6
State	Published - Oct 1985

Keywords

mixed graph
negative cycles
NP-completeness
shortest paths

Access to Document

10.1016/0167-6377(85)90013-6

Cite this

@article{3fe2c63bca554ac2ba61bb92cbafa7a0,

title = "On negative cycles in mixed graphs",

abstract = "We show that, for mixed graphs, i.e., graphs having both directed and undirected edges, with a length function defined on the edges, the problems of detecting negative cycles and of finding the shortest path in the absence of negative cycles are NP-complete.",

keywords = "mixed graph, negative cycles, NP-completeness, shortest paths",

author = "Arkin, \{Esther M.\} and Papadimitriou, \{Christos H.\}",

year = "1985",

month = oct,

doi = "10.1016/0167-6377(85)90013-6",

language = "English",

volume = "4",

pages = "113--116",

journal = "Operations Research Letters",

issn = "0167-6377",

number = "3",

}

TY - JOUR

T1 - On negative cycles in mixed graphs

AU - Arkin, Esther M.

AU - Papadimitriou, Christos H.

PY - 1985/10

Y1 - 1985/10

N2 - We show that, for mixed graphs, i.e., graphs having both directed and undirected edges, with a length function defined on the edges, the problems of detecting negative cycles and of finding the shortest path in the absence of negative cycles are NP-complete.

AB - We show that, for mixed graphs, i.e., graphs having both directed and undirected edges, with a length function defined on the edges, the problems of detecting negative cycles and of finding the shortest path in the absence of negative cycles are NP-complete.

KW - mixed graph

KW - negative cycles

KW - NP-completeness

KW - shortest paths

UR - https://www.scopus.com/pages/publications/0022136660

U2 - 10.1016/0167-6377(85)90013-6

DO - 10.1016/0167-6377(85)90013-6

M3 - Article

AN - SCOPUS:0022136660

SN - 0167-6377

VL - 4

SP - 113

EP - 116

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

On negative cycles in mixed graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this