Hardness of Approximate Diameter: Now for Undirected Graphs.
Mina DalirrooyfardRay LiVirginia Vassilevska WilliamsPublished in: CoRR (2021)
Keyphrases
- undirected graph
- average degree
- directed graph
- phase transition
- directed acyclic graph
- approximation algorithms
- spanning tree
- minimum cost
- np hard
- connected components
- positive integer
- vertex set
- graph structure
- disjoint paths
- random graphs
- computational complexity
- complex networks
- np complete
- worst case
- strongly connected
- random walk
- lower bound