A polynomial kernel for trivially perfect editing
type: Item
instance of: scholarly article
title: A polynomial kernel for trivially perfect editing
title: A Polynomial Kernel for Trivially Perfect Editing
zbMATH Open document ID: 1397.05070
zbMATH Open document ID: 1466.68045
DOI: 10.1007/978-3-662-48350-3_36
DOI: 10.1007/S00453-017-0401-6
author: Pål Grønås Drange
author: Michał Pilipczuk
published in: Algorithmica
published in: Algorithms - ESA 2015
publication date: 2018-10-18T00:00:00Z
publication date: 2015-11-19T00:00:00Z
full work available at URL: https://arxiv.org/abs/1412.7558
Mathematics Subject Classification ID: 05C17
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q27
zbMATH DE Number: 6958239
zbMATH DE Number: 6511788
zbMATH Keywords: trivially perfect graph
zbMATH Keywords: graph modification
zbMATH Keywords: polynomial kernel
MaRDI profile type: Publication
OpenAlex ID: W1589219240
OpenAlex ID: W2908014032
Wikidata QID: Q59607877
arXiv ID: 1412.7558
cites work: A kernelization algorithm for \(d\)-hitting set
cites work: NP-completeness results for edge modification problems
cites work: Fixed-parameter tractability of graph modification problems for hereditary properties
cites work: Incompressibility of \(H\)-free edge modification problems
cites work: Polynomial Kernelization for Removing Induced Claws and Diamonds
cites work: On the threshold of intractability
cites work: Q2965491
cites work: On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
cites work: Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
cites work: Which problems have strongly exponential complexity?
cites work: Cluster editing with locally bounded modifications
cites work: Two Edge Modification Problems without Polynomial Kernels
cites work: Fast FAST
cites work: A Subexponential Parameterized Algorithm for Proper Interval Completion
cites work: Subexponential parameterized algorithm for Interval Completion
cites work: Polynomial kernelization for removing induced claws and diamonds
cites work: Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
cites work: Exploring the subexponential complexity of completion problems
cites work: Paths, Trees, and Flowers
cites work: The complexity of some edge deletion problems
cites work: Parametrized complexity theory.
cites work: Tight bounds for parameterized complexity of cluster editing with a small number of clusters
cites work: A Polynomial Kernel for Proper Interval Vertex Deletion
cites work: Subexponential Parameterized Algorithm for Minimum Fill-In
cites work: Transitiv orientierbare Graphen
cites work: Faster parameterized algorithms for deletion to split graphs
cites work: Quasi-threshold graphs
cites work: Two edge modification problems without polynomial kernels
cites work: Complexity and parameterized algorithms for cograph editing
cites work: Modular decomposition and transitive orientation
cites work: Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion
cites work: On the density of families of sets
cites work: A combinatorial problem; stability and order for models and theories in infinitary languages
cites work: Edge-Deletion Problems
description: scientific article; zbMATH DE number 6511788
alternative label: A Polynomial Kernel for Trivially Perfect Editing