Path Contraction Faster than $2^n$
From MaRDI portal
Publication:3300757
DOI10.1137/19M1259638zbMath1455.68132MaRDI QIDQ3300757
Fedor V. Fomin, Prafullkumar Tale, Saket Saurabh, Daniel Lokshtanov, Akanksha Agrawal
Publication date: 30 July 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
graph algorithmsexact exponential-time algorithmspath contraction3-disjoint connected subgraphsenumerating connected sets
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (6)
On the parameterized complexity of maximum degree contraction problem ⋮ Enumeration of minimal tropical connected sets ⋮ Contracting to a longest path in H-free graphs ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Disjoint paths and connected subgraphs for \(H\)-free graphs
Cites Work
- Unnamed Item
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- Edge-contraction problems
- Partitioning graphs into connected parts
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- Which problems have strongly exponential complexity?
- On the NP-hardness of edge-deletion and -contraction problems
- Treewidth computation and extremal combinatorics
- Connecting Terminals and 2-Disjoint Connected Subgraphs
- Contractibility and NP-completeness
- Finding a Maximum Independent Set
- Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
- On Problems as Hard as CNF-SAT
- Determinant Sums for Undirected Hamiltonicity
- Contracting bipartite graphs to paths and cycles
- Contracting chordal graphs and bipartite graphs to paths and trees
- On the complexity of \(k\)-SAT
This page was built for publication: Path Contraction Faster than $2^n$
