(Sub)linear kernels for edge modification problems toward structured graph classes
type: Item
instance of: scholarly article
title: (Sub)linear kernels for edge modification problems toward structured graph classes
author: Gabriel Bathie
author: Nicolas Bousquet
author: Yixin Cao
author: Yuping Ke
author: Théo Pierron
published in: Algorithmica
publication date: 2022-10-27T00:00:00Z
full work available at URL: https://arxiv.org/abs/2105.09566
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7608293
zbMATH Keywords: kernelization
zbMATH Keywords: graph editing
zbMATH Keywords: split graphs
zbMATH Keywords: (Sub)linear kernels
MaRDI profile type: Publication
OpenAlex ID: W4225406559
cites work: Correlation clustering
cites work: Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems
cites work: A golden ratio parameterized algorithm for cluster editing
cites work: NP-completeness results for edge modification problems
cites work: Fixed-parameter tractability of graph modification problems for hereditary properties
cites work: Cluster editing: kernelization based on edge cuts
cites work: A \(2k\) kernel for the cluster editing problem
cites work: Parameterized Algorithms
cites work: Editing Simple Graphs
cites work: Exploring the subexponential complexity of completion problems
cites work: A polynomial kernel for trivially perfect editing
cites work: Q6168461
cites work: Tight bounds for parameterized complexity of cluster editing with a small number of clusters
cites work: Kernelization
cites work: Faster parameterized algorithms for deletion to split graphs
cites work: On the relation of strong triadic closure and cluster deletion
cites work: Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
cites work: The splittance of a graph
cites work: On the complexity of \(k\)-SAT
cites work: Cluster editing with locally bounded modifications
cites work: Strong triadic closure in cographs and graphs of low maximum degree
cites work: Edge deletion problems: branching facilitated by modular decomposition
cites work: Complexity classification of some edge modification problems
cites work: Parameterizing edge modification problems above lower bounds
cites work: The Comparability Graph of a Tree
cites work: Quasi-threshold graphs
cites work: Node-and edge-deletion NP-complete problems
DOI: 10.1007/S00453-022-00969-1
description: scientific article; zbMATH DE number 7608293