Polynomial kernels for proper interval completion and related problems

DOI10.1016/j.ic.2013.08.006zbMath1358.68117OpenAlexW1489471929MaRDI QIDQ393083

Stéphane Bessy, Anthony Perez

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

zbMATH Keywords

parameterized complexityproper interval graphsgraph modification problemskernelization algorithms

Mathematics Subject Classification ID

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