Lower Bounds for the Parameterized Complexity of Minimum Fill-in and Other Completion Problems

Ivan Bliznets,Marek Cygan,Paweł Komosa,Michał Pilipczuk,Lukas Mach

Lower Bounds for the Parameterized Complexity of Minimum Fill-in and Other Completion Problems

2020

Ivan Bliznets
Marek Cygan
Paweł Komosa
Michał Pilipczuk
Lukas Mach

In this work, we focus on several completion problems for subclasses of chordal graphs: MINIMUM FILL-IN, INTERVAL COMPLETION, PROPER INTERVAL COMPLETION, TRIVIALLY PERFECT COMPLETION, and THRESHOLD...

Keywords:

Mathematics
Discrete mathematics
Parameterized complexity

Correction
Source
Cite
Save
Machine Reading By IdeaReader

References

Citations