93 citations · 244 across the 16 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
cs.DM2014
A Generalized Cheeger Inequality
Ioannis Koutis, Gary Miller, Richard Peng
The generalized conductance between two graphs and on the same vertex set is defined as the ratio $$ ϕ(G,H) = \min_{S\subseteq V} \frac{cap_G(S,\bar{S})}{ cap_…
cs.DS2014
Simple parallel and distributed algorithms for spectral graph sparsification
Ioannis Koutis
We describe a simple algorithm for spectral graph sparsification, based on iterative computations of weighted spanners and uniform sampling. Leveraging the algorithms of Baswana an…