MPI-INF D1 Publications

Search the publication database

Your search returned the following 4 documents:

  1. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
    Surender Baswana and Sandeep Sen
    Random Structures & Algorithms 30 (4): 532-563, 2007
  2. All-pairs nearly 2-approximate shortest paths in $O(n^2 \mathrm polylog n)$ time
    Surender Baswana, Vishrut Goyal, and Sandeep Sen
    In: STACS 2005 : 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, 2005, 666-679
    [PS: Download:]
  3. Approximate distance oracle for unweighted graphs in Expected O(n²) time
    Surender Baswana and Sandeep Sen
    In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04), New Orleans, USA, 2004, 271-280
    [PS: Download:]
  4. Randomized graph data-structures for approximate shortest path problem
    Surender Baswana and Sandeep Sen
    In: Handbook of Data Structures and Applications, 2004, 38.1-38.19