Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Home
Experience
Publications
Contact
Light
Dark
Automatic
Hypergraph algorithm
Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition
We design an algorithm for computing connectivity in hypergraphs which runs in time $\hat O_r(p + \min{\lambda n^2, n^r/\lambda})$, where $p$ is the size, $n$ is the number of vertices, $r$ is the rank (size of the largest hyperedge), and $\lambda$ is the connectivity of the hypergraph.
Calvin Beideman
,
Karthekeyan Chandrasekaran
,
Sagnik Mukhopadhyay
,
Danupon Nanongkai
PDF
arXiv
Cite
×