Hardness of Approximate Diameter: Now for Undirected Graphs.
Mina DalirrooyfardRay LiVirginia Vassilevska WilliamsPublished in: FOCS (2022)
Keyphrases
- undirected graph
- average degree
- phase transition
- directed graph
- directed acyclic graph
- approximation algorithms
- np hard
- spanning tree
- minimum cost
- graph structure
- connected components
- disjoint paths
- multicommodity flow
- complex networks
- multi dimensional
- computational complexity
- random walk
- np complete
- random graphs
- positive integer
- probabilistic model
- strongly connected
- vertex set
- special case
- bayesian networks