Saturating flows in networks

B. S. Chlebus, M. Chrobak, K. Diks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

A saturating flow through a network satisfies the condition that if it uses an edge then it uses its whole capacity. We show that the problem to verify whether there is a non-zero saturating flow in a given network is strongly NP-complete. This problem restricted to edge series-parallel networks remains NP-complete, but there is a pseudopolynomial time algorithm solving it. Restricted still farther to s-t outerplanar networks the problem is polynomially solvable.

Original languageEnglish (US)
Title of host publicationFundamentals of Computation Theory - International Conference, FCT 1987
EditorsLothar Budach, Rais Gatic Bukharajev, Oleg Borisovic Lupanov
PublisherSpringer Verlag
Pages82-91
Number of pages10
ISBN (Print)9783540187400
DOIs
StatePublished - 1987
Externally publishedYes
EventInternational Conference on Fundamentals of Computation Theory, FCT 1987 - Kazan, Russian Federation
Duration: Jun 22 1987Jun 26 1987

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume278 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Fundamentals of Computation Theory, FCT 1987
Country/TerritoryRussian Federation
CityKazan
Period6/22/876/26/87

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Saturating flows in networks'. Together they form a unique fingerprint.

Cite this