Min-sum 2-paths problems

DOI10.1007/S00224-014-9569-1zbMath1332.05061OpenAlexW2036183099MaRDI QIDQ260263

Oded Lachish, Alexandru Popa, Trevor I. Fenner

Publication date: 21 March 2016

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://eprints.bbk.ac.uk/id/eprint/15295/1/15295.pdf

zbMATH Keywords

pathsalgorithmsorientationMIN-sum

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ Walking through waypoints ⋮ Shortest Two Disjoint Paths in Polynomial Time

Cites Work

• The complexity of finding two disjoint paths with min-max objective function
• On orientations and shortest paths
• Graph minors. XIII: The disjoint paths problem
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
• On Shortest Disjoint Paths in Planar Graphs
• Route-Enabling Graph Orientation Problems
• The k-Disjoint Paths Problem on Chordal Graphs
• Theory and Applications of Models of Computation

This page was built for publication: Min-sum 2-paths problems