Vijaya Ramachandran: Current Research

My primary research interest is on algorithm design, and my current research explores three avenues: Design and analysis of efficient sequential and parallel algorithms for combinatorial problems; cache-efficient algorithms; and experimental evaluation of algorithms.

Postscript and Adobe pdf files of my recent papers are available below. Papers appearing in journals and conference proceedings are protected by the associated copyrights, and files posted here are for personal scholarly use only.

A complete listing of my papers is included in my vita.
[vita in postscript]    [vita in Adobe pdf]

Algorithm Design and Analysis

  • D. Fernholz, V. Ramachandran, "The k-orientability thresholds for G_{n,p}." Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2007.
  • G. Ganapathy, B. Goodson, R. Jansen, H. Le, V. Ramachandran, T. Warnow, "Pattern Identification in Biogeography." IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2006. (Special Issue for WABI'05.)

  • R. A. Chowdhury, V. Ramachandran, ``Cache-oblivious dynamic programming.'' Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2006.

  • S. Pettie, V. Ramachandran, ``A shortest path algorithm for real-weighted undirected graphs,'' SIAM Journal on Computing, 34(6):1398--1431, 2005.
  • D. Fernholz, V. Ramachandran, "The diameter of sparse random graphs." TR04-34, 2004. Submitted for publication. [Postscript file]    [PDF file]

  • D. Fernholz, V. Ramachandran, "Cores and connectivity in sparse random graphs". Technical report TR04-13, 2004. [Postscript file]    [PDF file]

  • D. Fernholz, V. Ramachandran, "The giant $k$-core of a random graph with a specified degree sequence," unpublished manuscript, November 2003. [Postscript file]    [PDF file]

  • R. A. Chowdhury, V. Ramachandran, "External-memory exact and approximate all-pairs shortest-paths in undirected graphs." Extended abstract in Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), January 2005.

  • R. A. Chowdhury, V. Ramachandran, "Cache-oblivious shortest paths in graphs using Buffer Heap." Extended abstract in Proc. ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), June 2004. [Postscript file]    [PDF file]

  • A. Prakash, A. Aziz, V. Ramachandran. "Randomized Parallel Schedulers for Switch-Memory-Switch Routers: Analysis and Numerical Studies." Extended abstract in Proc. INFOCOM, March 2004.

  • G. Ganapathy, V. Ramachandran, T. Warnow. "On Contract-and-Refine Transformations Between Phylogenetic Trees." Extended abstract in Proc. ACM-SIAM SODA, January 2004. [Postscript file]    [PDF file]

  • G. Ganapathy, V. Ramachandran, T. Warnow. "Better Hill-Climbing Searches for Parsimony." Proc. Workshop on Algorithms for Bioinformatics (WABI), September 2003, Budapest, Hungary.

  • A. Aziz, V. Ramachandran, A. Prakash. "A Near Optimal Scheduler for Switch-Memory-Switch Routers." Extended abstract in Proc ACM SPAA, June 2003.

  • X. Zhang, C. Bajaj, V. Ramachandran. "Isosurfaces: Parallel and out-of-core view-dependent isocontour visualization using random data distribution." Extended abstract in Proc. Data Visualisation 2002, Eurographics/IEEE TCVF Symposium, Barcelona, Spain 2002, pp. 9-18.

  • C. Demetrescu, M. Thorup, R. A. Chowdhury, V. Ramachandran. "Oracles for distances avoiding a node or link failure." submitted for publication. (Portions of these results appear in R. A. Chowdhury, V. Ramachandran. "Improved Distance Oracles for Avoiding Link-Failure." Proc. ISAAC, November 2002.)

  • S. Pettie, V. Ramachandran, "Minimizing randomness in minimum spanning tree , parallel connectivity, and set maxima algorithms." Extended abstract in Proc. ACM-SIAM Symp. on Discrete Algorithms, January 2002. [Postscript file]    [PDF file]

  • S. Pettie, V. Ramachandran, "Computing undirected shortest paths using comparisons and additions." Extended abstract in Proc. ACM-SIAM Symp. on Discrete Algorithms, January 2002. [Postscript file]    [PDF file]

  • S. Pettie, V. Ramachandran, S. Srinath, ``Experimental evaluation of a new shortest path algorithm,'' UTCS Technical Report TR-01-37, 2001. Proc. 4th Workshop on Algorithm Engineering and Experiments (ALENEX02), January 2002. [Postscript file]    [PDF file]

  • S. Pettie, V. Ramachandran, "An optimal minimum spanning tree algorithm." Journal of the ACM, vol. 49, no. 1, pp.16-34, 2002. (Extended abstract in Proc. 27th International Colloquium on Automata, Languages and Programming (ICALP'2000), LNCS Volume 1853, Springer, July 2000, pp. 49-60.) [Postscript file]    [PDF file]

  • S. Pettie, V. Ramachandran, "A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest." SIAM Journal on Computing, vol. 31, no. 6, pp. 1879-1895, 2002. (Extended abstract in Proc. Random-Approx'99, LNCS Volume 1671, Springer, August 1999, pp. 233-244.) [Postscript file]    [PDF file]

  • P. D. MacKenzie, V. Ramachandran, "Computational bounds for fundamental problems on general-purpose parallel models." Extended abstract in Proc. ACM Symp. on Parallel Algorithms and Architectures (SPAA'98), June-July 1998, pp. 152-163. [Postscript file]    [PDF file]

  • C. K. Poon, V. Ramachandran, "A randomized linear work EREW PRAM algorithm to find a minimum spanning forest." Algorithmica, vol. 35, no. 3, pp. 257-268, 2003. (Extended abstract in Proc. 8th Annual International Symposium on Algorithms and Computation (ISAAC '97), Springer-Verlag LNCS vol. 1530, December 1997, pp. 212-222.)
    [Postscript file]    [PDF file]

  • M. R. Korupolu, V. Ramachandran, "Quasi-fully dynamic algorithms for two-connectivity, cycle equivalence and related problems." Algorithmica, to appear. Extended abstract in Proc. European Symposium on Algorithms (ESA'97), Springer-Verlag LNCS vol. 1284, September 1997, pp. 326-340. [Postscript file]    [PDF file]

  • V. King, C. K. Poon, V. Ramachandran, S. Sinha, "An optimal EREW PRAM algorithm for minimum spanning tree verification." Information Processing Letters, vol. 62, no. 3, 1997, pp. 153-159. [Postscript file]    [PDF file]

  • P. Gibbons, Y. Matias, V. Ramachandran, "Efficient low-contention parallel algorithms." Journal of Computer and System Sciences, vol. 53, No. 3, 1996, pp. 395-416. (Special Issue on papers from ACM SPAA'94). [Postscript file]    [PDF file]

  • V. Ramachandran, H. Yang, "An efficient parallel algorithm for the general planar monotone circuit value problem." SIAM Journal on Computing. vol. 25, 1996, pp. 312-339. [Postscript file]    [PDF file]

  • X. Han, P. Kelsen, V. Ramachandran, R. E. Tarjan, "Finding minimal spanning subgraphs in linear time." SIAM Journal on Computing. vol. 24, 1995, pp. 1332-1358. [Postscript file]    [PDF file]

  • P. Kelsen, V. Ramachandran, "On finding minimal two connected subgraph." Journal of Algorithms. vol. 18, 1995, pp. 1-49. [Postscript file]    [PDF file]

  • V. Ramachandran, J.H. Reif, "Planarity testing in parallel." Journal of Computer and Systems Sciences (Special Issue on papers from FOCS'89). Vol. 49, 1994, pp. 517-561. [Postscript file]    [PDF file]

  • V. Ramachandran, H. Yang, "Finding the closed partition of a planar graph." Algorithmica. vol. 11, 1994, pp. 443-468. [Postscript file]    [PDF file]

  • T.-S. Hsu, V. Ramachandran, "On finding a minimum augmentation to biconnect a graph." SIAM Journal on Computing. 1993, pp. 889-912. [Postscript file]    [PDF file]

  • V. Ramachandran, "Parallel open ear decomposition with applications to graph biconnectivity and triconnectivity." Chapter in `Synthesis of Parallel Algorithms,' J.H. Reif, ed., Morgan-Kaufmann, 1993, pp. 275-340. [Postscript file]    [PDF file]

  • D. Fussell, V. Ramachandran, R. Thurimella, "Finding triconnected components by local replacement." SIAM Journal on Computing, 1993, pp. 587-616. [Postscript file]    [PDF file]

  • G. L. Miller, V. Ramachandran, "A new graph triconnectivity algorithm and its parallelization." Combinatorica. Vol. 12, 1992, pp. 53-76. [Postscript file]    [PDF file]

  • T.-S. Hsu, V. Ramachandran, "A linear time algorithm for triconnectivity augmentation." Proc. 32nd Annual IEEE Symposium on Foundations of Computer Science. 1991, pp. 548-559. [Postscript file]    [PDF file]

  • P. Gibbons, R. Karp, V. Ramachandran, D. Soroker, R. Tarjan, "Transitive compaction in parallel via branchings." Journal of Algorithms. Vol. 12, no. 1, 1991, pp. 110-125. [Postscript file]    [PDF file]

  • A. Kanevsky, V. Ramachandran, "Improved algorithms for graph four-connectivity." Jour. Computer and System Sciences (FOCS'87 Special Issue). Vol. 42, 1991, pp. 288-306. [Postscript file]    [PDF file]

    Models for Parallel Computation

  • V. Ramachandran, B.Grayson, M. Dahlin. "Emulations between QSM, BSP and LogP: A framework for general-purpose parallel algorithm design." Journal of Parallel and Distributed Computing, vol. 63, 2003, pp. 1175-1192. (Summary in Proc. ACM-SIAM SODA'99.) [Postscript file]    [PDF file]

  • B.Grayson, M. Dahlin, V. Ramachandran. "Experimental evaluation of QSM: A simple shared-memory model." TR98-21, CS dept., Univ. of Texas at Austin, November 1998. (Summary in Proc. IPPS/SPDP 1999.) [Postscript file]    [PDF file]

  • P. Gibbons, Y. Matias, V. Ramachandran. "Can a shared memory model serve as a bridging model for parallel computation?" Theory of Computing Systems Special Issue on papers from SPAA'97, vol. 32, no. 3, 1999, pp. 327-359. [Postscript file]    [PDF file]

  • V. Ramachandran. "A general purpose shared-memory model for parallel computation." Algorithms for Parallel Processing, Volume 105, IMA Volumes in Mathematics and its Applications, Springer-Verlag, 1999, pp. 1-17. [Postscript file]    [PDF file]

  • M. Adler, P. Gibbons, Y. Matias, V. Ramachandran. "Modeling parallel bandwidth: Local vs. global restrictions." Algorithmica Special Issue on Coarse Grained Parallel Algorithms, vol. 24, no. 3-4, 1999, pp. 381-404. [Postscript file]    [PDF file]

  • P.B. Gibbons, Y. Matias, V. Ramachandran. "The queue-read queue-write asynchronous PRAM model." Theoretical Computer Science, vol. 196, 1998, pp. 3-29. [Postscript file]    [PDF file]

  • P.D. MacKenzie, V. Ramachandran. "ERCW PRAMs and optical communication." Theoretical Computer Science, vol. 196, 1998, pp. 153-180. [Postscript file]    [PDF file]

  • P. Gibbons, Y. Matias, V. Ramachandran. "The QRQW PRAM: Accounting for contention in parallel algorithms." SIAM Journal on Computing, vol. 28, no. 2, pp. 733-769, 1999. [Postscript file]    [PDF file]

    Algorithm Implementation

  • R. Mettu, Y. Zhao, V. Ramachandran. "Experimental evaluation and comparison of algorithms for incremental graph biconnectivity." TR97-17, Univ. of Texas at Austin, June 1997. [Postscipt file]    [PDF file] View plots: [Plots in postscript]    [Plots in PDF]

  • T.-s. Hsu, V. Ramachandran, N. Dean, "Parallel implementation of algorithms for finding connected components in graphs." Parallel Algorithms: Third DIMACS Implementation Challenge, vol. 30, DIMACS Series, American Math. Soc., 1997, pp. 395--416. [Postscript file]    [PDF file]

  • T.-s. Hsu, V. Ramachandran. "Efficient massively parallel implementation of some combinatorial algorithms." Theoretical Computer Science, vol. 162, no. 2, 1996, pp. 297-322. [Postscript file]    [PDF file]

  • M. Korupolu, R. Mettu, V. Ramachandran, Y. Zhao, "Experimental evaluation of algorithms for incremental graph connectivity and biconnectivity." Presented at DIMACS Implementation Challenge Workshop V, October 1996. [Postscript file]    [PDF file]

  • T.-s. Hsu, V. Ramachandran, N. Dean. "Implementation of parallel graph algorithms on a massively parallel SIMD computer with virtual processing." Extended abstract in Proc. 9th International Parallel Processing Symposium. Santa Barbara, CA, April 1995, pp. 106-112. [Postscript file]    [PDF]

  • T.-s. Hsu, V. Ramachandran, N. Dean. "Implementation of efficient parallel algorithms on the MasPar." Computational Support for Discrete Mathematics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Volume 15, American Mathematical Society, 1994, pp. 165-198. [Postscript file]    [PDF file]

    Contact Information

    Office: 3.152 Taylor Hall
    Email: vlr AT cs.utexas DOT edu
    Phone: (512) 471-9554
    Fax: (512) 471-8885

    POSTAL ADDRESS:
    Department of Computer Sciences
    The University of Texas at Austin
    Austin, Texas 78712-1188
    U.S.A.