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
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, F. Silvestri, B. Blakeley, V. Ramachandran,
``Oblivious algorithms for multicores and network of processors,''
Proc. IEEE IPDPS, April 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.
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