• search hit 85 of 153
Back to Result List

Line Planning, Path Constrained Network Flow and Inapproximability

Please always quote using this URN:urn:nbn:de:0296-matheon-10272
  • We consider a basic subproblem which arises in line planning, and is of particular importance in the context of a high system load or robustness: How much can be routed maximally along all possible lines? The essence of this problem is the Path Constrained Network Flow (PCN) problem. We explore the complexity of this problem and its dual. In particular we show for the primal that it is as hard to approximate as MAX CLIQUE and for the dual that it is as hard to approximate as SET COVER. We also prove that the PCN problem is hard for special graph classes, interesting both from a complexity and from a practical perspective. Finally, we present a special graph class for which there is a polynomial-time algorithm.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Christina Büsing, Sebastian Stiller
URN:urn:nbn:de:0296-matheon-10272
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2012/01/25
Release Date:2012/01/25
Tag:Complexity; Line Planning; Network Flows; Robustness
Institute:Technische Universität Berlin
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05-06 Proceedings, conferences, collections, etc.
Preprint Number:877
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.