Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes
DOI10.1007/978-3-319-21840-3_34zbMath1451.68203OpenAlexW2402537399MaRDI QIDQ3449838
André Nichterlein, Christian Komusiewicz, Falk Hüffner
Publication date: 30 October 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-21840-3_34
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Cites Work
- Unnamed Item
- Fundamentals of parameterized complexity
- Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions
- Kernels for feedback arc set in tournaments
- Nonlinear oscillations under multifrequency parametric excitation
- A more effective linear kernelization for cluster editing
- The node-deletion problem for hereditary properties is NP-complete
- The splittance of a graph
- Some simplified NP-complete graph problems
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Cluster graph modification problems
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- On realizations of point determining graphs, and obstructions to full homomorphisms
- Graph partitions with prescribed patterns
- On the Clique Editing Problem
- Editing Simple Graphs
- Kernels: Annotated, Proper and Induced
- Editing the Simplest Graphs
- Complexity classification of some edge modification problems
This page was built for publication: Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes
