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; effective modeling of parallel machines for algorithm design; and experimental evaluation of algorithms.

Postscript and Adobe pdf files of my recent papers are available below.

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 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]   e [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]   e [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]   e [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.