Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph

DOI10.1134/S0081543815050089zbMath1319.05125OpenAlexW1040622739MaRDI QIDQ492279

Mikhail Yu. Khachay, Alexander Kel'Manov, E. Kh. Gimadi, Artem V. Pyatkin

Publication date: 20 August 2015

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0081543815050089

zbMATH Keywords

approximation algorithmmetric problemperformance guaranteeattainable boundsminimum total weight of vertices and edgesquadratic Euclidean problemsearch for vertex-disjoint cliques

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Performance evaluation of a parallel ant colony optimization for the real-time train routing selection problem in large instances ⋮ The maximum independent union of cliques problem: complexity and exact approaches ⋮ On the Approximability of the Minimum Weight $t$-partite Clique Problem ⋮ A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 2-approximate algorithm to solve one problem of the family of disjoint vector subsets
• 2-approximation algorithm for finding a clique with minimum weight of vertices and edges
• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• An extended formulation approach to the edge-weighted maximal clique problem
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• The traveling salesman problem and its variations
• A strongly polynomial algorithm for the transportation problem
• Assignment Problems
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• Lower bounds for symmetricK-peripatetic salesman problems

This page was built for publication: Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph