Finding k Disjoint Paths in a Directed Planar Graph
From MaRDI portal
Publication:4305357
DOI10.1137/S0097539792224061zbMath0810.05061OpenAlexW2050579693MaRDI QIDQ4305357
Publication date: 9 April 1995
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539792224061
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items
Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ Towards the Graph Minor Theorems for Directed Graphs ⋮ Towards Single Face Shortest Vertex-Disjoint Paths in Undirected Planar Graphs ⋮ Polynomial time algorithms for tracking path problems ⋮ FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ Irrelevant vertices for the planar disjoint paths problem ⋮ The disjoint shortest paths problem ⋮ Parameterizing path partitions ⋮ Combinatorial acyclicity models for potential‐based flows ⋮ The Induced Disjoint Paths Problem ⋮ Detours in directed graphs ⋮ A linear time algorithm for the induced disjoint paths problem in planar graphs ⋮ A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ On the complexity of the edge-disjoint min-min problem in planar digraphs ⋮ On shortest disjoint paths in planar graphs ⋮ A tight lower bound for edge-disjoint paths on planar DAGs ⋮ Multiflow Feasibility: An Annotated Tableau ⋮ Finding k Partially Disjoint Paths in a Directed Planar Graph ⋮ On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms ⋮ Hardness of Finding Two Edge-Disjoint Min-Min Paths in Digraphs ⋮ Network characterizations for excluding Braess's paradox ⋮ Tight Bounds for Linkages in Planar Graphs ⋮ Induced disjoint paths problem in a planar digraph ⋮ A trichotomy for regular simple path queries on graphs ⋮ Half-integral linkages in highly connected directed graphs ⋮ Improved Algorithms for the 2-Vertex Disjoint Paths Problem ⋮ Unnamed Item ⋮ Walking through waypoints ⋮ Complexity of a classical flow restoration problem ⋮ Theoretical and computational advances for network diversion ⋮ A relaxation of the directed disjoint paths problem: a global congestion metric helps ⋮ A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. ⋮ The Directed Disjoint Shortest Paths Problem ⋮ Planar Digraphs ⋮ On the complexity of the planar directed edge-disjoint paths problem ⋮ Steiner Problems with Limited Number of Branching Nodes
