Disjoint paths and connected subgraphs for \(H\)-free graphs
From MaRDI portal
Publication:5918405
DOI10.1016/j.tcs.2021.10.019OpenAlexW3168725788MaRDI QIDQ5918405
Erik Jan van Leeuwen, Daniël Paulusma, Walter Kern, Barnaby Martin, Siani Smith
Publication date: 1 December 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2105.06349
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (4)
Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Few induced disjoint paths for \(H\)-free graphs ⋮ Few induced disjoint paths for \(H\)-free graphs
Cites Work
- Unnamed Item
- The disjoint paths problem in quadratic time
- Removing local extrema from imprecise terrains
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- Finding disjoint paths in split graphs
- On partitioning a graph into two connected subgraphs
- Partitioning graphs into connected parts
- Paw-free graphs
- Complement reducible graphs
- Graph minors. XIII: The disjoint paths problem
- Vertex disjoint paths on clique-width bounded graphs
- Connecting Terminals and 2-Disjoint Connected Subgraphs
- Dynamic Programming Treatment of the Travelling Salesman Problem
- A Dynamic Programming Approach to Sequencing Problems
- Path Contraction Faster than $2^n$
- A Polynomial Solution to the Undirected Two Paths Problem
- On the Computational Complexity of Combinatorial Problems
- On the Complexity of Timetable and Multicommodity Flow Problems
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Disjoint paths and connected subgraphs for \(H\)-free graphs
- Contracting to a longest path in H-free graphs
This page was built for publication: Disjoint paths and connected subgraphs for \(H\)-free graphs
