Exploring subexponential parameterized complexity of completion problems

DOI10.4230/LIPICS.STACS.2014.288MaRDI QIDQ2965491zbMATH OpenFDO

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

zbMATH Keywords

edge completionmodificationsubexponential parameterized complexity

Mathematics Subject Classification ID

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

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

Cited in

(9)

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

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)