Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
From MaRDI portal
Publication:3084217
DOI10.1137/070697781zbMath1207.68169OpenAlexW2061597613MaRDI QIDQ3084217
Publication date: 15 March 2011
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/8cd9156af81041c5786794d6564ccad977c6a2d4
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)
Related Items
Edge-Disjoint Branchings in Temporal Graphs, Congestion-Free Rerouting of Flows on DAGs, Packing arc-disjoint cycles in tournaments, Evaluation and Enumeration Problems for Regular Path Queries, Adapting the Directed Grid Theorem into an FPT Algorithm, Parameterizing path partitions, Packing arc-disjoint cycles in oriented graphs, A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs, A tight lower bound for edge-disjoint paths on planar DAGs, Digraph width measures in parameterized algorithmics, Chordless Cycle Packing Is Fixed-Parameter Tractable, Edge-disjoint branchings in temporal digraphs, Half-integral linkages in highly connected directed graphs, Routing with congestion in acyclic digraphs, On the complexity of finding internally vertex-disjoint long directed paths, The directed 2-linkage problem with length constraints, 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., Packing Arc-Disjoint Cycles in Tournaments, On width measures and topological problems on semi-complete digraphs, Packing Cycles Faster Than Erdos--Posa, Acyclic Digraphs, Digraphs of Bounded Width
