Showing cs.DSShow all
2 papers · 1 filter
cs.DS2016
Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners
Jakub Pachocki, Liam Roditty, Aaron Sidford +2
The girth of a graph, i.e. the length of its shortest cycle, is a fundamental graph parameter. Unfortunately all known algorithms for computing, even approximately, the girth and g…
cs.DS2014
New routing techniques and their applications
Liam Roditty, Roei Tov
Let be an undirected graph with vertices and edges. We obtain the following new routing schemes: - A routing scheme for unweighted graphs that uses $\tilde O(\fra…