Finding disjoint paths in split graphs
From MaRDI portal
Publication:493652
DOI10.1007/s00224-014-9580-6zbMath1329.68142OpenAlexW2084983168MaRDI QIDQ493652
Erik Jan van Leeuwen, Pinar Heggernes, Pim van 't Hof, Reza Saei
Publication date: 4 September 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-014-9580-6
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (7)
On the kernelization of split graph problems ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Kernelization of Two Path Searching Problems on Split Graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Induced disjoint paths in AT-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The disjoint paths problem in quadratic time
- Kernel bounds for disjoint cycles and disjoint paths
- A simplified NP-complete satisfiability problem
- On problems without polynomial kernels
- The splittance of a graph
- Algorithmic graph theory and perfect graphs
- Graph minors. XIII: The disjoint paths problem
- NP-completeness of some edge-disjoint paths problems
- Vertex disjoint paths on clique-width bounded graphs
- Finding Disjoint Paths in Split Graphs
- On the Computational Complexity of Combinatorial Problems
- On the Complexity of Timetable and Multicommodity Flow Problems
- (Meta) Kernelization
- The k-Disjoint Paths Problem on Chordal Graphs
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
This page was built for publication: Finding disjoint paths in split graphs
