On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
type: Item
instance of: scholarly article
title: On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
zbMATH Open document ID: 1262.68048
author: Sylvain Guillemot
author: Christophe Paul
author: Anthony Perez
author: Frédéric Havet
published in: Algorithmica
publication date: 2013-05-16T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6163646
zbMATH Keywords: parameterized complexity
zbMATH Keywords: kernelization algorithms
zbMATH Keywords: cograph
zbMATH Keywords: modular decomposition
MaRDI profile type: Publication
full work available at URL: s00453-012-9619-5
OpenAlex ID: W1754878559
cites work: Kernels for feedback arc set in tournaments
cites work: Polynomial kernels for 3-leaf power graph modification problems
cites work: On problems without polynomial kernels
cites work: Q3113681
cites work: Kernel bounds for disjoint cycles and disjoint paths
cites work: Graph Classes: A Survey
cites work: On generating triangle-free graphs
cites work: Fixed-parameter tractability of graph modification problems for hereditary properties
cites work: A 2k Kernel for the Cluster Editing Problem
cites work: Handle-rewriting hypergraph grammars
cites work: A Combinatorial Decomposition Theory
cites work: The complexity of some edge deletion problems
cites work: Efficient Parameterized Preprocessing for Cluster Editing
cites work: Parametrized complexity theory.
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: Q4198056
cites work: Graph Sandwich Problems
cites work: A survey of the algorithmic aspects of modular decomposition
cites work: Q3549635
cites work: Q3549601
cites work: Two Edge Modification Problems without Polynomial Kernels
cites work: Cograph Editing: Complexity and Parameterized Algorithms
cites work: An O(n2) Algorithm for Undirected Split Decomposition
cites work: Complexity classification of some edge modification problems
cites work: Q5710169
cites work: A general method to speed up fixed-parameter-tractable algorithms
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Q5683627
cites work: Cluster graph modification problems
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: A 4 k 2 kernel for feedback vertex set
cites work: Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems
DOI: 10.1007/S00453-012-9619-5
description: scientific article; zbMATH DE number 6163646