On approximating the maximum diameter ratio of graphs
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)\).
- Approximating maximum diameter-bounded subgraphs
- Approximating maximum diameter-bounded subgraph in unit disk graphs
- Optimal approximation algorithms for maximum distance-bounded subgraph problems
- Optimal approximation algorithms for maximum distance-bounded subgraph problems
- scientific article; zbMATH DE number 3857166
- Optimal approximation algorithms for maximum distance-bounded subgraph problems
- Parameterized computational complexity of finding small-diameter subgraphs
- A centrality notion for graphs based on Tukey depth
- Distance-based clique relaxations in networks: s-clique and s-club
- On Approximating the d-Girth of a Graph
- scientific article; zbMATH DE number 3857166 (Why is no real title available?)
- Optimal approximation algorithms for maximum distance-bounded subgraph problems
- Approximating maximum diameter-bounded subgraphs
- On inclusionwise maximal and maximum cardinality k-clubs in graphs
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
This page was built for publication: On approximating the maximum diameter ratio of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1349101)
