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

DOI10.1134/S0081543815050089zbMATH Open1319.05125OpenAlexW1040622739MaRDI QIDQ492279FDOQ492279

Authors Eh. Kh. Gimadi, A. V. Kel'manov, Artem Pyatkin, M. Yu. Khachaĭ

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) Graph algorithms (graph-theoretic aspects) (05C85) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph
• 2-approximation algorithm for finding a clique with minimum weight of vertices and edges
• Approximation Algorithms for Some Graph Partitioning Problems
• Heuristically determining cliques of given cardinality and with minimal cost within weighted complete graphs
• A new algorithm for the maximum-weight clique problem

Cites work

• scientific article; zbMATH DE number 3485514 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1894374 (Why is no real title available?)
• scientific article; zbMATH DE number 3338967 (Why is no real title available?)
• 2-approximation algorithm for finding a clique with minimum weight of vertices and edges
• A 2-approximate algorithm to solve one problem of the family of disjoint vector subsets
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• A strongly polynomial algorithm for the transportation problem
• An extended formulation approach to the edge-weighted maximal clique problem
• Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2
• Assignment Problems
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Lower bounds for symmetricK-peripatetic salesman problems
• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• The traveling salesman problem and its variations

Cited in

(8)

• Performance evaluation of a parallel ant colony optimization for the real-time train routing selection problem in large instances
• On the approximability of the minimum weight \(t\)-partite clique problem
• 2-approximation algorithm for finding a clique with minimum weight of vertices and edges
• A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
• Heuristically determining cliques of given cardinality and with minimal cost within weighted complete graphs
• The maximum independent union of cliques problem: complexity and exact approaches
• Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q492279)