A PTAS for the Cluster Editing Problem on Planar Graphs

DOI10.1007/978-3-319-51741-4_3MaRDI QIDQ2971154zbMATH OpenOpenAlexFDO

Authors André Berger, Alexander Grigoriev, Andrej Winokurow

Publication date 4 April 2017

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-51741-4_3

zbMATH Keywords

PTAScorrelation clusteringcluster editinggraph approximation\(k\)-planaritymicroscopy cell segmentation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• A faster algorithm for the cluster editing problem on proper interval graphs
• The Cluster Editing Problem: Implementations and Experiments
• The Multi-parameterized Cluster Editing Problem
• On the complexity of multi-parameterized cluster editing
• Tight bounds for parameterized complexity of Cluster Editing
• Branch-and-cut approaches for p-cluster editing
• Editing graphs into few cliques: complexity, approximation, and kernelization schemes
• scientific article; zbMATH DE number 26490
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• On the clique editing problem

Cites work

• scientific article; zbMATH DE number 3405712 (Why is no real title available?)
• A c^k n 5-approximation algorithm for treewidth
• Approximating Symmetric Relations by Equivalence Relations
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation algorithms for approximating graphs with bounded number of connected components
• Clustering with qualitative information
• Correlation clustering
• Correlation clustering and two-edge-connected augmentation for planar graphs
• Diameter and treewidth in minor-closed graph families
• Easy problems for tree-decomposable graphs
• Genus, treewidth, and local crossing number
• Going weighted: parameterized algorithms for cluster editing
• Graphs drawn with few crossings per edge
• On simple characterizations of k-trees
• Parameterized algorithms
• Treewidth. Computations and approximations

Cited in

(2)

• On the clique editing problem
• Correlation clustering and two-edge-connected augmentation for planar graphs

This page was built for publication: A PTAS for the Cluster Editing Problem on Planar Graphs

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