Polynomial kernels for proper interval completion and related problems
From MaRDI portal
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
- 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 4k^2 kernel for feedback vertex set
- 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
(16)- A Subexponential Parameterized Algorithm for Proper Interval Completion
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- Polynomial kernels for edge modification problems towards block and strictly chordal graphs
- 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
- Kernel for proper Helly circular-arc vertex deletion: smaller and simpler via graph isomorphism
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
- Polynomial kernels for proper interval completion and related problems
- An improved kernelization algorithm for trivially perfect editing
- 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)
