Vijaya Ramachandran: Recent Papers

Current Research Interests

My primary research interest is in algorithm design, and my current research interests are in algorithmic and modeling aspects of multicore computing.

Postscript and Adobe pdf files of some of my recent papers are available below. Most of my papers are also available from online copies of journals and conferences.

Copyright Disclaimer

The documents available from this site are provided as a means to ensure timely dissemination of technical work on a non-commercial basis. The electronic version of some of the works available from this site may differ from the definitive published version. Papers appearing in journals and conference proceedings are protected by the associated copyrights, and files posted here are for personal scholarly use only.

Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder (ACM, Springer-Verlag, Elsevier, etc.). Permission to make digital or hard copies of part or all of these works for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage.

Recent Papers

  • Meghana Nasre, Matteo Pontecorvi, Vijaya Ramachandran, ``Decremental all-pairs all shortest paths and betweenness centrality,'' arXiv:1411.4073, 2014. Refereed conference version to appear in Proc. Intl. Symp. on Algorithms and Computation (ISAAC), December 2014. [PDF file]

  • Meghana Nasre, Matteo Pontecorvi, Vijaya Ramachandran, ``Betweenness centrality --- Incremental and faster,'' arXiv:1311.2147v3, 2013. Refereed conference version in Proc. Math. Foundations of Comp. Sci. (MFCS), August 2014. [PDF file]

  • R.A. Chowdhury, V. Ramachandran, F. Silvestri, B. Blakeley, ``Oblivious algorithms for multicores and network of processors'' Jour. of Parallel and Distributed Processing, Vol 73, pp. 911-925, 2013. [PDF file]

  • R. Cole and V. Ramachandran, ``Analysis of randomized work-stealing with false sharing,'' Proc 27th IPDPS, 2013. [PDF file]

  • F. Ellen, V. Ramachandran, and P. Woelfel, ``Efficient Fetch-and-Increment,'' Proc. DISC 2012, LNCS 7611, pp. 16-30, 2012. [PDF file]

  • R. Cole and V. Ramachandran, ``Efficient resource oblivious algorithms for multicores with false sharing,'' IPDPS 2012. [PDF file]

  • A. Katti and V. Ramachandran, ``Competitive cache replacement strategies for shared cache environments,'' IPDPS 2012. [PDF file] [A. Katti Masters Thesis]

  • R. Cole and V. Ramachandran, ``Revisiting the cache miss analysis of multithreaded algorithms,'' LATIN 2012. [PDF file]

  • R. Cole and V. Ramachandran, ``Resource-oblivious sorting on multicores,'' Proc. International Colloquium of Automata, Languages and Programming (ICALP), Track A, Springer LNCS Volume 6198, pp. 226-237, 2010. [PDF file]

  • P. Chuong, F. Ellen, V. Ramachandran, ``A Universal Construction for Wait-Free Transaction Friendly Data Structures,'' ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 335-344, 2010. [PDF file]

  • R. A. Chowdhury, V. Ramachandran, ``The cache-oblivious Gaussian elimination paradigm: Theoretical framework, parallelization and experimental evaluation.'' Theory of Computing Systems, 47(1):878--919, 2010. Special Issue for SPAA 2007. [PDF file]

  • R.A. Chowdhury, H. Le, V. Ramachandran, ``Cache-oblivious Dynamic Programming for Bioinformatics,'' IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), 7(3):495--510, 2010. [PDF file]

  • S. Pettie, V. Ramachandran, ``New randomized minimum spanning tree algorithms using exponentially fewer random bits,'' ACM Transactions on Algorithms (TALG), vol. 4, no. 1, article 5, March 2008. [PDF file]

  • R. A. Chowdhury and V. Ramachandran, ``Cache-efficient dynamic programming algorithms for multicores,'' Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 207-216, 2008. [PDF file]

  • G. Blelloch, R. A. Chowdhury, P. Gibbons, V. Ramachandran, S. Chen, M. Kozuch, ``Provably good multicore cache performance for divide-and-conquer algorithms,'' Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 501-510, 2008. [PDF file]

  • O. Ruwase, P.B. Gibbons, T.C. Mowry, V. Ramachandran, S. Chen, M. Kozuch, M. Ryan, ``Parallelizing Dynamic Information Flow Tracking,'' Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, pp. 35-45, 2008

  • S. Chen, M. Kozuch, T. Strigkos, B. Falsafi, P.B. Gibbons, T.C. Mowry, V. Ramachandran, O. Ruwase, M. Ryan, E. Vlachos, ``Flexible hardware acceleration for instruction-grain program monitoring,'' Proc. Intl. Conf. Computer Architecture (ISCA), pp. 377-388, 2008

  • C. Demetrescu, M. Thorup, R. Chowdhury, V. Ramachandran, ``Oracles for distances avoiding a failed node or link", SIAM Journal on Computing, vol. 37, no. 5, pp. 1299-1318, 2008. [PDF file]

  • R. A. Chowdhury, V. Ramachandran, ``The cache-oblivious Gaussian elimination paradigm: Theoretical framework, parallelization and experimental evaluation.'' Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 71-80, June 2007. Invited to Theory of Computing Systems} Special Issue for SPAA'07. [PDF file]

  • D. Fernholz, V. Ramachandran, ``The $k$-orientability thresholds for $G_{n,p}$.'' Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 459-468, January 2007. [PDF file]`

  • D. Fernholz, V. Ramachandran, ``The diameter of sparse random graphs,'' Random Structures and Algorithms (RSA), vol. 31, no. 4, pp. 482-516, 2007. [PDF file]

    Selected Papers 2006 and Earlier

  • 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. [pdf file]   

  • S. Pettie, V. Ramachandran, ``A shortest path algorithm for real-weighted undirected graphs,'' SIAM Journal on Computing, 34(6):1398--1431, 2005. [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. [pdf file]   

  • 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. [PDF file]

  • 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]

  • 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. [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.

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

  • 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]

  • 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]

  • S. Buss, S. A. Cook, A. Gupta, V. Ramachandran, ``An optimal parallel algorithm for formula evaluation.'' SIAM Jour. Computing, Vol 21, 1992, pp. 755-780.

  • 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]

    Contact Information

    Email: vlr "at" cs "dot" utexas "dot" edu
    Phone:(512) 471-9554
    Fax:(512) 471-8885
    Office: ACES 3.432
    Postal: Department of Computer Science
    Mailcode D9500
    The University of Texas at Austin
    Austin, Texas 78712-1188