2-Approximation algorithm for finding a clique with minimum weight of vertices and edges
| Autor: | I. I. Eremin, Artem V. Pyatkin, E. Kh. Gimadi, Alexander Kel'manov, M. Yu. Khachai |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
Strength of a graph Clique graph Vertex (geometry) Combinatorics Minimum k-cut Mathematics (miscellaneous) Clique problem TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Independent set Multiple edges Time complexity MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Proceedings of the Steklov Institute of Mathematics. 284:87-95 |
| ISSN: | 1531-8605 0081-5438 |
| Popis: | The problem of finding a minimum clique (with respect to the total weight of its vertices and edges) of fixed size in a complete undirected weighted graph is considered along with some of its important subclasses. Approximability issues are analyzed. The inapproximability of the problem is proved for the general case. A 2-approximation efficient algorithm with time complexity O(n 2 ) is suggested for the cases when vertex weights are nonnegative and edge weights either satisfy the triangle inequality or are squared pairwise distances for some point configuration of Euclidean space. Keywords: complete undirected graph, clique of fixed size, minimum weight of vertices and edges, subset search, approximability, polynomial time approximation algorithm, approximation guarantee, time complexity. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink