Path Contraction Faster Than 2^n
From MaRDI portal
Publication:5091159
DOI10.4230/LIPIcs.ICALP.2019.11OpenAlexW2966455354MaRDI QIDQ5091159
Daniel Lokshtanov, Saket Saurabh, Prafullkumar Tale, Fedor V. Fomin, Akanksha Agrawal
Publication date: 21 July 2022
Full work available at URL: https://bora.uib.no/bora-xmlui/bitstream/1956/23578/2/1-s2.0-S030439750500633X-main.pdf
graph algorithmsexact exponential time algorithmspath contraction3-disjoint connected subgraphsenumerating connected sets
Related Items (1)
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
