Polynomial kernels for proper interval completion and related problems

DOI10.1016/J.IC.2013.08.006MaRDI QIDQ393083zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• Title not available (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A \(2k\) kernel for the cluster editing problem
• A general method to speed up fixed-parameter-tractable algorithms
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• A survey of the algorithmic aspects of modular decomposition
• Cluster graph modification problems
• Computing the Minimum Fill-In is NP-Complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Interval Completion Is Fixed Parameter Tractable
• Kernelization: new upper and lower bound techniques
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• On problems without polynomial kernels
• On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
• On the complexity of DNA physical mapping
• Optimal greedy algorithms for indifference graphs
• Parameterized and Exact Computation
• Polynomial kernels for 3-leaf power graph modification problems
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Proper Interval Vertex Deletion
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Simple linear time recognition of unit interval graphs
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Two edge modification problems without polynomial kernels

Cited in

(13)

• A Subexponential Parameterized Algorithm for Proper Interval Completion
• scientific article; zbMATH DE number 7651188 (Why is no real title available?)
• 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
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• A survey of parameterized algorithms and the complexity of edge modification
• 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}

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)