Saturating flows in networks
- ,
- M. Chrobak,
- K. Diks
- University of Warsaw
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Related Event
Title
International Conference on Fundamentals of Computation Theory, FCT 1987
Event type
ConferenceDate
06/22/1987 - 06/26/1987Location
KazanRussian Federation
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.
Publication Information
Output type
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Original language
English (US)Pages from-to (Number of pages)
Pages 82-91 (10 pages)Publication milestones
- Published - 1987
Publication status
Published - 1987
Publisher
Springer VerlagPublication series
- Publication series name: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print): 0302-9743
ISSN (Electronic): 1611-3349
Volume: 278 LNCS
ISBN (Print)
9783540187400Publication IDs
- Scopus: 84959865861
Host publication title
Fundamentals of Computation Theory - International Conference, FCT 1987Host publication editors
- Lothar Budach
- Rais Gatic Bukharajev
- Oleg Borisovic Lupanov
Publication metrics
Metrics
Fractional count
1
Fractional count
0.33
Fractional count
2
Fractional count
0.67
Fractional count
1
Fractional count
1
PlumX, opens in new tab
Citation count
1