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
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
approximation algorithmmetric problemperformance guaranteeattainable boundsminimum total weight of vertices and edgesquadratic Euclidean problemsearch for vertex-disjoint cliques
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Assignment Problems
- Title not available (Why is that?)
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- The traveling salesman problem and its variations
- Title not available (Why is that?)
- A strongly polynomial algorithm for the transportation problem
- A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
- Title not available (Why is that?)
- Title not available (Why is that?)
- 2-approximation algorithm for finding a clique with minimum weight of vertices and edges
- 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
- A 2-approximate algorithm to solve one problem of the family of disjoint vector subsets
- 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
Cited In (8)
- On the Approximability of the Minimum Weight $t$-partite Clique Problem
- 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
- A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
- The maximum independent union of cliques problem: complexity and exact approaches
- Performance evaluation of a parallel ant colony optimization for the real-time train routing selection problem in large instances
- Heuristically determining cliques of given cardinality and with minimal cost within weighted complete graphs
- Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
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)
