A survey of parameterized algorithms and the complexity of edge modification

2020/01/19 by Crespelle, Christophe, Drange, Pål Grønås, Fomin, Fedor V. +1 · 4 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2001.06867

Abstract

The survey provides an overview of the developing area of parameterized algorithms for graph modification problems. We concentrate on edge modification problems, where the task is to change a small number of adjacencies in a graph in order to satisfy some required property.

Cited by

• An efficient algorithm for F-subgraph-free Edge Deletion on graphs having a product structure
• A Finer View of the Parameterized Landscape of Labeled Graph Contractions
• Improved upper bounds on color reversal by local inversions
• Triangle-Covered Graphs: Algorithms, Complexity, and Structure

Related

• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• Parameterized Geometric Graph Modification with Disk Scaling
• Graph Editing to a Given Degree Sequence
• Chordal Editing is Fixed-Parameter Tractable
• Parameterized Algorithms for Balanced Cluster Edge Modification Problems