ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS

DOI10.1142/S0129054107004656zbMath1112.68136OpenAlexW2013850148MaRDI 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

clusteringapproximation algorithmclique partitioninapproximabilityDNA clone classification

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Protein sequences, DNA sequences (92D20) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (12)

Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem ⋮ Competitive Strategies for Online Clique Clustering ⋮ The cluster deletion problem for cographs ⋮ Polyhedral results and stronger Lagrangean bounds for stable spanning trees ⋮ 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 ⋮ Unnamed Item ⋮ Cluster deletion on interval graphs and split related graphs ⋮ Indirect identification of horizontal gene transfer ⋮ A note on the complexity of the maximum edge clique partitioning problem with respect to the clique number ⋮ Online clique clustering

Cites Work

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

This page was built for publication: ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS