Polynomial Kernels for Proper Interval Completion and Related Problems

DOI10.1007/978-3-642-22953-4_20zbMath1342.68152arXiv1103.5599OpenAlexW2570709797MaRDI QIDQ3088286

Stéphane Bessy, Anthony Perez

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (1)

An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs

Cites Work

• Unnamed Item
• 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
• 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

This page was built for publication: Polynomial Kernels for Proper Interval Completion and Related Problems