Line planning, path constrained network flow and inapproximability

DOI10.1002/NET.20386MaRDI QIDQ3076020zbMATH OpenOpenAlexFDO

Authors Christina Büsing, Sebastian Stiller

Publication date 17 February 2011

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20386

zbMATH Keywords

bounded treewidthcomplexityline planningnetwork flowsplanar graphsrobustness

Mathematics Subject Classification ID

Flows in graphs (05C21) Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10) Deterministic scheduling theory in operations research (90B35)

Recommendations

• scientific article; zbMATH DE number 5117501
• Models for line planning in public transport
• scientific article; zbMATH DE number 3848940
• The line connectivity problem
• Metric inequalities for routings on direct connections with application to line planning

Cites work

• A threshold of ln n for approximating set cover
• Approximation algorithms for NP-hard problems.
• Combinatorial optimization. Theory and algorithms
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Optimal lines for railway systems
• Primal-dual approximation algorithms for integral flow and multicut in trees

Cited in

(5)

• Metric inequalities for routings on direct connections with application to line planning
• Balanced-flow algorithm for path network planning in hierarchical spaces
• Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks
• Construction Line Algorithms for the Connection Location-Allocation Problem
• Algorithms and hardness for non-pool-based line planning

This page was built for publication: Line planning, path constrained network flow and inapproximability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3076020)