A PTAS for the Cluster Editing Problem on Planar Graphs

DOI10.1007/978-3-319-51741-4_3zbMath1484.68328OpenAlexW2568488014MaRDI QIDQ2971154

Andrej Winokurow, André Berger, Alexander Grigoriev

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

PTAScluster editingcorrelation clusteringgraph approximation\(k\)-planaritymicroscopy cell segmentation

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Correlation clustering
• Going weighted: parameterized algorithms for cluster editing
• Graphs drawn with few crossings per edge
• Treewidth. Computations and approximations
• Diameter and treewidth in minor-closed graph families
• On simple characterizations of k-trees
• Clustering with qualitative information
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Genus, Treewidth, and Local Crossing Number
• Easy problems for tree-decomposable graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation algorithms for graph approximation problems
• Approximating Symmetric Relations by Equivalence Relations
• Parameterized Algorithms

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