Algorithmic trade-offs for girth approximation in undirected graphs.
Avi KadriaLiam RodittyAaron SidfordVirginia Vassilevska WilliamsUri ZwickPublished in: SODA (2022)
Keyphrases
- undirected graph
- approximation algorithms
- trade off
- directed graph
- disjoint paths
- graph structure
- directed acyclic graph
- np hard
- connected components
- spanning tree
- minimum cost
- strongly connected
- special case
- closed form
- complex networks
- positive integer
- multicommodity flow
- random graphs
- graphical models
- average degree
- worst case