Polynomial kernels for proper interval completion and related problems

DOI10.1016/J.IC.2013.08.006zbMATH Open1358.68117OpenAlexW1489471929MaRDI QIDQ393083FDOQ393083

Authors: 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

Recommendations

• Polynomial kernels for proper interval completion and related problems
• A Polynomial Kernel for Proper Interval Vertex Deletion
• A polynomial kernel for \textsc{Proper Interval Vertex Deletion}
• A Subexponential Parameterized Algorithm for Proper Interval Completion
• A subexponential parameterized algorithm for proper interval completion

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)

Cites Work

• On the complexity of DNA physical mapping
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On problems without polynomial kernels
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Optimal greedy algorithms for indifference graphs
• A \(4k^2\) kernel for feedback vertex set
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Title not available (Why is that?)
• Simple linear time recognition of unit interval graphs
• Title not available (Why is that?)
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Computing the Minimum Fill-In is NP-Complete
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• A survey of the algorithmic aspects of modular decomposition
• Cluster graph modification problems
• Kernelization: new upper and lower bound techniques
• A general method to speed up fixed-parameter-tractable algorithms
• 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
• A \(2k\) kernel for the cluster editing problem
• Interval Completion Is Fixed Parameter Tractable
• Two edge modification problems without polynomial kernels
• Parameterized and Exact Computation
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Polynomial kernels for 3-leaf power graph modification problems

Cited In (13)

• Title not available (Why is that?)
• Edge deletion problems: branching facilitated by modular decomposition
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• A subexponential parameterized algorithm for proper interval completion
• Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
• A survey of parameterized algorithms and the complexity of edge modification
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• On the proper interval completion problem within some chordal subclasses
• Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
• A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
• Polynomial kernels for proper interval completion and related problems
• A polynomial kernel for \textsc{Proper Interval Vertex Deletion}
• A Subexponential Parameterized Algorithm for Proper Interval Completion

This page was built for publication: Polynomial kernels for proper interval completion and related problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q393083)