ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS

DOI10.1142/S0129054107004656zbMath1112.68136MaRDI QIDQ3434272

Jesper Jansson, Mia Persson, Eva-Marta Lundell, Andrzej Lingas, Anders Dessmark

Publication date: 25 April 2007

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054107004656

zbMATH Keywords

clustering; approximation algorithm; clique partition; inapproximability; DNA clone classification

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

92D20: Protein sequences, DNA sequences

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W25: Approximation algorithms

Related Items

Unnamed Item, Polyhedral results and stronger Lagrangean bounds for stable spanning trees, The cluster deletion problem for cographs, The minimum spanning tree problem with conflict constraints and its variations, Finding the closest ultrametric, Complexity of the cluster deletion problem on subclasses of chordal graphs, A note on the complexity of the maximum edge clique partitioning problem with respect to the clique number, Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem, Cluster deletion on interval graphs and split related graphs, Indirect identification of horizontal gene transfer, Online clique clustering, Competitive Strategies for Online Clique Clustering

Cites Work

• Correlation clustering
• Optimization, approximation, and complexity classes
• The Complexity of Multiterminal Cuts
• Some optimal inapproximability results