Polynomial kernels for proper interval completion and related problems
type: Item
instance of: scholarly article
title: Polynomial kernels for proper interval completion and related problems
zbMATH Open document ID: 1358.68117
author: Stéphane Bessy
author: Anthony Perez
published in: Information and Computation
publication date: 2014-01-16T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C62
zbMATH DE Number: 6246020
zbMATH Keywords: parameterized complexity
zbMATH Keywords: kernelization algorithms
zbMATH Keywords: graph modification problems
zbMATH Keywords: proper interval graphs
MaRDI profile type: Publication
full work available at URL: j.ic.2013.08.006
OpenAlex ID: W1489471929
cites work: Polynomial kernels for 3-leaf power graph modification problems
cites work: Kernelization: New Upper and Lower Bound Techniques
cites work: On problems without polynomial kernels
cites work: Fixed-parameter tractability of graph modification problems for hereditary properties
cites work: A 2k Kernel for the Cluster Editing Problem
cites work: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
cites work: Simple linear time recognition of unit interval graphs
cites work: Parameterized and Exact Computation
cites work: Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
cites work: Q4393480
cites work: On the complexity of DNA physical mapping
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: A survey of the algorithmic aspects of modular decomposition
cites work: A Fully dynamic algorithm for recognizing and representing proper interval graphs
cites work: Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
cites work: Two Edge Modification Problems without Polynomial Kernels
cites work: Optimal greedy algorithms for indifference graphs
cites work: Q5710169
cites work: A general method to speed up fixed-parameter-tractable algorithms
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: Proper Interval Vertex Deletion
cites work: Interval Completion Is Fixed Parameter Tractable
cites work: Computing the Minimum Fill-In is NP-Complete
DOI: 10.1016/J.IC.2013.08.006
description: scientific article; zbMATH DE number 6246020