On the complexity of finding internally vertex-disjoint long directed paths
DOI10.1007/s00453-019-00659-5zbMath1433.68164arXiv1706.09066OpenAlexW2962799203WikidataQ126579741 ScholiaQ126579741MaRDI QIDQ5918120
No author found.
Publication date: 14 April 2020
Published in: Algorithmica, LATIN 2018: Theoretical Informatics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1706.09066
parameterized complexitycomplexity dichotomyFPT algorithmrepresentative familyspindledigraph subdivision
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A randomized algorithm for long directed cycle
- Fundamentals of parameterized complexity
- Finding a subdivision of a digraph
- Approximate triclique coloring for register allocation
- Representative families: a unified tradeoff-based approach
- Disjoint paths in acyclic digraphs
- Which problems have strongly exponential complexity?
- A short proof of Mader's \(\mathcal S\)-paths theorem
- Parametrized complexity theory.
- Disjoint \(A\)-paths in digraphs
- Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Finding Two Edge-Disjoint Paths with Length Constraints
- Divide-and-Color
- On the existence of specified cycles in a tournament
- Color-coding
- Packing paths in digraphs
- Cycles with two blocks in k‐chromatic digraphs
- Finding a subdivision of a prescribed digraph of order 4
- Subdivisions of oriented cycles in digraphs with large chromatic number
- The complexity of finding maximum disjoint paths with length constraints
- Kernelization Lower Bounds by Cross-Composition
- Finding topological subgraphs is fixed-parameter tractable
- Automata, Languages and Programming
- Parameterized Algorithms
This page was built for publication: On the complexity of finding internally vertex-disjoint long directed paths
