On approximating the maximum diameter ratio of graphs (Q1349101)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On approximating the maximum diameter ratio of graphs |
scientific article |
Statements
On approximating the maximum diameter ratio of graphs (English)
0 references
21 May 2002
0 references
It is shown that the problem of determining the maximum diameter ratio (local density) \(\text{dr}(G)\) of a graph \(G\) is APX-complete, i.e. there is a polynomial time approximation algorithm which approximates \(\text{dr}(G)\) within factor 2 but there is a constant \(c> 1\) such that finding approximations within factor \(c\) from the optimum is NP-hard. The authors also prove that for every fixed integer \(d\geq 1\), finding a subgraph \(H\) of \(G\) with maximum number of vertices whose diameter is \(\leq d\) is polynomially equivalent to the MAX CLIQUE problem. If \(d\) is the diameter and \(n\) is the number of vertices of a given tree \(T\) then computing \(\text{dr}(T)\) can be implemented in time \(O(dn)\).
0 references
local density
0 references
APX-complete
0 references
approximation algorithm
0 references
diameter
0 references