On the Approximability of the Minimum Weight $t$-partite Clique Problem

DOI10.7155/jgaa.00525zbMath1447.05196OpenAlexW3015807429MaRDI QIDQ5119375

Geoffrey A. Solano, Guillaume Blin, Mathieu Raffinot, Jaime D. L. Caro, Jhoirene Clemente

Publication date: 4 September 2020

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00525

zbMATH Keywords

gene cluster2-approximation algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Genetics and epigenetics (92D10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Performance evaluation of a parallel ant colony optimization for the real-time train routing selection problem in large instances

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 2-approximation algorithm for finding a clique with minimum weight of vertices and edges
• Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph
• Solving the maximum edge weight clique problem via unconstrained quadratic programming
• Approximating the maximum vertex/edge weighted clique using local search
• An extended formulation approach to the edge-weighted maximal clique problem
• New facets and a branch-and-cut algorithm for the weighted clique problem.
• A New Algorithm for Generating All the Maximal Independent Sets
• Approximation Algorithms for the k-Clique Covering Problem
• An Analysis of Some Graph Theoretical Cluster Techniques
• Algorithm 457: finding all cliques of an undirected graph

This page was built for publication: On the Approximability of the Minimum Weight $t$-partite Clique Problem