Polynomial kernels for proper interval completion and related problems
From MaRDI portal
Publication:393083
DOI10.1016/j.ic.2013.08.006zbMath1358.68117OpenAlexW1489471929MaRDI QIDQ393083
Publication date: 16 January 2014
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2013.08.006
Analysis of algorithms and problem complexity (68Q25) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (9)
Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes ⋮ Unit interval editing is fixed-parameter tractable ⋮ Edge deletion problems: branching facilitated by modular decomposition ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ A Subexponential Parameterized Algorithm for Proper Interval Completion
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A survey of the algorithmic aspects of modular decomposition
- Polynomial kernels for 3-leaf power graph modification problems
- Simple linear time recognition of unit interval graphs
- 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 Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
- 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
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Parameterized and Exact Computation
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
This page was built for publication: Polynomial kernels for proper interval completion and related problems
