Polynomial Kernels for Proper Interval Completion and Related Problems
From MaRDI portal
Publication:3088286
DOI10.1007/978-3-642-22953-4_20zbMath1342.68152arXiv1103.5599MaRDI QIDQ3088286
Publication date: 19 August 2011
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1103.5599
68Q25: Analysis of algorithms and problem complexity
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- A kernel of order \(2k - c\) for Vertex Cover
- Polynomial kernels for 3-leaf power graph modification problems
- On problems without polynomial kernels
- On the complexity of DNA physical mapping
- Fixed-parameter tractability of graph modification problems for hereditary properties
- A general method to speed up fixed-parameter-tractable algorithms
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- Cluster graph modification problems
- Optimal greedy algorithms for indifference graphs
- A 4 k 2 kernel for feedback vertex set
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Proper Interval Vertex Deletion
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A 2k Kernel for the Cluster Editing Problem
- Interval Completion Is Fixed Parameter Tractable
- Kernelization: New Upper and Lower Bound Techniques
- Two Edge Modification Problems without Polynomial Kernels
- Computing the Minimum Fill-In is NP-Complete
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
