On the complexity of circulations

Esther M. Arkin; Christos H. Papadimitriou

doi:10.1016/0196-6774(86)90042-8

On the complexity of circulations

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 present a polynomial-time algorithm for producing a feasible real-valued circulation in undirected graphs with upper and lower bounds, based on Seymour's characterization. For directed graphs, an efficient algorithm follows from a classical result by Hoffman. We show that, for mixed graphs, i.e., graphs having both directed and undirected edges, the problem is NP-complete.

Original language	English
Pages (from-to)	134-145
Number of pages	12
Journal	Journal of Algorithms
Volume	7
Issue number	1
DOIs	https://doi.org/10.1016/0196-6774(86)90042-8
State	Published - Mar 1986

Access to Document

10.1016/0196-6774(86)90042-8

Cite this

@article{18d663fad64941ec9edf40f48152e873,

title = "On the complexity of circulations",

abstract = "We present a polynomial-time algorithm for producing a feasible real-valued circulation in undirected graphs with upper and lower bounds, based on Seymour's characterization. For directed graphs, an efficient algorithm follows from a classical result by Hoffman. We show that, for mixed graphs, i.e., graphs having both directed and undirected edges, the problem is NP-complete.",

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

year = "1986",

month = mar,

doi = "10.1016/0196-6774(86)90042-8",

language = "English",

volume = "7",

pages = "134--145",

journal = "Journal of Algorithms",

issn = "0196-6774",

number = "1",

}

TY - JOUR

T1 - On the complexity of circulations

AU - Arkin, Esther M.

AU - Papadimitriou, Christos H.

PY - 1986/3

Y1 - 1986/3

N2 - We present a polynomial-time algorithm for producing a feasible real-valued circulation in undirected graphs with upper and lower bounds, based on Seymour's characterization. For directed graphs, an efficient algorithm follows from a classical result by Hoffman. We show that, for mixed graphs, i.e., graphs having both directed and undirected edges, the problem is NP-complete.

AB - We present a polynomial-time algorithm for producing a feasible real-valued circulation in undirected graphs with upper and lower bounds, based on Seymour's characterization. For directed graphs, an efficient algorithm follows from a classical result by Hoffman. We show that, for mixed graphs, i.e., graphs having both directed and undirected edges, the problem is NP-complete.

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

U2 - 10.1016/0196-6774(86)90042-8

DO - 10.1016/0196-6774(86)90042-8

M3 - Article

AN - SCOPUS:0012821831

SN - 0196-6774

VL - 7

SP - 134

EP - 145

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -

On the complexity of circulations

Abstract

Access to Document

Other files and links

Fingerprint

Cite this