Editing graphs into few cliques: complexity, approximation, and kernelization schemes

DOI10.1007/978-3-319-21840-3_34MaRDI QIDQ3449838zbMATH OpenOpenAlexFDO

Authors Falk Hüffner, Christian Komusiewicz, André Nichterlein

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• A More Effective Linear Kernelization for Cluster Editing
• A more effective linear kernelization for cluster editing
• A 2k kernel for the cluster editing problem
• A \(2k\) kernel for the cluster editing problem
• On the clique editing problem

Cites work

• A more effective linear kernelization for cluster editing
• Cluster graph modification problems
• Complexity classification of some edge modification problems
• Correlation clustering with a fixed number of clusters
• Editing simple graphs
• Editing the simplest graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Fundamentals of parameterized complexity
• Graph partitions with prescribed patterns
• Kernels for feedback arc set in tournaments
• Kernels: Annotated, Proper and Induced
• Nonlinear oscillations under multifrequency parametric excitation
• On realizations of point determining graphs, and obstructions to full homomorphisms
• On the clique editing problem
• Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions
• Some simplified NP-complete graph problems
• The node-deletion problem for hereditary properties is NP-complete
• The splittance of a graph
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters

Cited in

(3)

• scientific article; zbMATH DE number 7525474 (Why is no real title available?)
• On Editing Graphs into 2-Club Clusters
• A PTAS for the Cluster Editing Problem on Planar Graphs

This page was built for publication: Editing graphs into few cliques: complexity, approximation, and kernelization schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449838)