Exploring subexponential parameterized complexity of completion problems

DOI10.4230/LIPICS.STACS.2014.288zbMATH Open1359.68126arXiv1309.4022MaRDI QIDQ2965491FDOQ2965491

Authors: Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger 

Publication date: 3 March 2017

Full work available at URL: https://arxiv.org/abs/1309.4022

Recommendations

• Exploring the subexponential complexity of completion problems
• scientific article; zbMATH DE number 7053390
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs

zbMATH Keywords

modificationedge completionsubexponential parameterized complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cited In (8)

• Paths to trees and cacti
• Edge deletion problems: branching facilitated by modular decomposition
• Paths to trees and cacti
• On the existence of subexponential parameterized algorithms
• Exploring the subexponential complexity of completion problems
• Polynomial kernelization for removing induced claws and diamonds
• Parameterized lower bound and NP-completeness of some \(H\)-free edge deletion problems
• A Subexponential Parameterized Algorithm for Proper Interval Completion

This page was built for publication: Exploring subexponential parameterized complexity of completion problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2965491)