Min-sum 2-paths problems

DOI10.1007/S00224-014-9569-1MaRDI QIDQ260263zbMATH OpenOpenAlexFDO

Authors Oded Lachish, Alexandru Popa, T. 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

algorithmspathsMIN-sumorientation

Mathematics Subject Classification ID

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

Recommendations

• Min-sum 2-paths problems
• Route-enabling graph orientation problems
• Route-enabling graph orientation problems
• Complexity and approximation results for the min-sum and min-max disjoint paths problems
• The complexity of two graph orientation problems

Cites work

• Graph minors. XIII: The disjoint paths problem
• On orientations and shortest paths
• On shortest disjoint paths in planar graphs
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
• Route-enabling graph orientation problems
• The \(k\)-disjoint paths problem on chordal graphs
• The complexity of finding two disjoint paths with min-max objective function
• Theory and Applications of Models of Computation

Cited in

(9)

• The 2-path network problem
• Route-enabling graph orientation problems
• Min-sum 2-paths problems
• On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems
• Route-enabling graph orientation problems
• Shortest two disjoint paths in polynomial time
• The Minimum Reload s-t Path/Trail/Walk Problems
• The minimum reload \(s-t\) path, trail and walk problems
• Walking through waypoints

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

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