Polynomial kernels for 3-leaf power graph modification problems
From MaRDI portal
Publication:602747
DOI10.1016/j.dam.2010.07.002zbMath1231.05131OpenAlexW1939541543MaRDI QIDQ602747
Anthony Perez, Stéphane Bessy, Christophe Paul
Publication date: 5 November 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2010.07.002
Graph polynomials (05C31) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Related Items
Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ Polynomial kernels for proper interval completion and related problems ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ A cubic-vertex kernel for flip consensus tree ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph-modeled data clustering: Exact algorithms for clique generation
- Structure and linear time recognition of 3-leaf powers
- Closest 4-leaf power is fixed-parameter tractable
- Cluster analysis and mathematical programming
- Cluster graph modification problems
- Error compensation in leaf power problems
- On Graph Powers for Leaf-Labeled Trees
- The Cluster Editing Problem: Implementations and Experiments
- Exact Algorithms for Cluster Editing: Evaluation and Experiments
- The 3-Steiner Root Problem
- On Problems without Polynomial Kernels (Extended Abstract)
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- A More Effective Linear Kernelization for Cluster Editing
- Tree Powers
- Structure and linear-time recognition of 4-leaf powers
- Parameterized and Exact Computation
- Efficient Parameterized Preprocessing for Cluster Editing
- Algorithms and Computation
- Graph-Theoretic Concepts in Computer Science
- Complexity classification of some edge modification problems
