A survey of parameterized algorithms and the complexity of edge modification

The survey is a comprehensive overview of the developing area of parameterized algorithms for graph modification problems. It describes state of the art in kernelization, subexponential algorithms, and parameterized complexity of graph modification. The main focus is on edge modification problems, w...

Full description

Saved in:
Bibliographic Details
Published in:Computer science review 2023-05, Vol.48, p.100556, Article 100556
Main Authors: Crespelle, Christophe, Drange, Pål Grønås, Fomin, Fedor V., Golovach, Petr
Format: Article
Language:English
Subjects:
Algorithms
Edge modification
Graph modification
Parameterized graph algorithms
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The survey is a comprehensive overview of the developing area of parameterized algorithms for graph modification problems. It describes state of the art in kernelization, subexponential algorithms, and parameterized complexity of graph modification. The main focus is on edge modification problems, where the task is to change some adjacencies in a graph to satisfy some required properties. To facilitate further research, we list many open problems in the area.
ISSN:1574-0137
1876-7745
DOI:10.1016/j.cosrev.2023.100556