Publications

A list of publications with downloadable pdfs (in most cases) appears below.

Book

• Genomic Quirks: The Search for Spelling Errors

  This is a book of real stories about the search for genomic spelling errors that have stark consequences -- infants who pass away mysteriously, siblings with misplaced organs, a family with several instances of vision loss, sisters whose hearts fail in the prime of their youth, a boy whose blood cannot carry enough oxygen, a baby with cancer in the eye, a middle-aged patient battling cancer, and the author’s own color blindness. The search in each case proves to be a detective quest that connects the world of medical practice with that of molecular biology, traversing the world of computer algorithms along the way.

Enumerating Spanning Trees

• Algorithms for Enumerating All Spanning Trees of an Undirected Graph.
  R. Hariharan and S. Kapoor.
  SIAM Journal on Computing, Vol. 24, No. 2, pp. 247--265, 1995.
  Workshop on Algorithms and Data Structures, LNCS 519, pp. 461--472, Aug. 1991.
  


• Algorithms for Enumerating All Spanning Trees of a Directed Graph.
  R. Hariharan and S. Kapoor.
  Algorithmica, 27, 2, pp. 120--130, 2000.
  Workshop on Algorithms and Data Structures, LNCS 519, pp. 461--472, Aug. 1991.
  

On-Line Graph Traversal

• On Traversing Layered Graphs On-line.
  R. Hariharan.
  SODA 93 Special Issue of Journal of Algorithms, Vol. 18, No. 3, pp. 480--512, 1995.
  4th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 412--421, Jan. 1993.
  

Finding Maximum Agreement Subtrees

• An $O(n\log n)$ algorithm for the Maximum Agreement Subtree Problem for Binary Trees.
  R. Cole, M. Farach, R. Hariharan, T.. Przytycka, M. Thorup.
  SIAM Journal on Computing, Vol. 30, No. 5, pp. 1385 -- 1404, 2002.
  7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 323--332, Jan. 1996.
  

Least Common Ancestor Computation in Trees

• Dynamic LCA Queries on Trees.
  R. Cole, R. Hariharan.
  SIAM Journal on Computing, Vol. 34, No. 4., pp. 894-923, 2005.
  10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 235--244, Jan. 1999.
  

Applications of Semi-Definite Programming

• Colouring Hypergraphs using Semi-Definite Programming.
  N. Alon, R. Hariharan, P. Kelsen, S. Mahajan.
  SWAT special issue of Nordic Journal on Computing, 3(4), pp. 425--439, 1996.
  Scandinavian Workshop on Algorithm Theory, pp. 41--52, Aug. 1996.


• Derandomizing Semidefinite Programming Based Approximation Algorithms.
  R. Hariharan, S. Mahajan.
  SIAM Journal on Computing, 28, 5, pp. 1641--1663, 1999.
  36th IEEE Symposium on Foundations of Computer Science, pp. 162--169, 1995.
  

Set-Cover Variations

• Hardness of Set Covering with Intersection 1.
  V.S. Anil Kumar, S. Arya, R. Hariharan.
  Journal submission not made yet.
  27th International Colloquium on Automata, Languages and Programming, pp. 624--635, Jul 2000.
  


• Covering Rectilinear Polygons with Rectangles.
  V.S. Anil Kumar, R. Hariharan.
  SIAM J. Comput. 32(6): 1509-1541 (2003)
  31st Annual ACM Symposium on Theory of Computing, pp. 445--454, May 1999.
  
  

All-Pairs Shortest Paths and Transitive Closure in Graphs

• Improved Algorithms for Maintaining Transitive Closure and All-Pairs Shortest Paths in Digraphs under Edge Deletions.
  S. Baswana, R. Hariharan, S. Sen.
  J. Algorithms 62(2): 74-92 (2007)
  34nd Annual ACM Symposium on Theory of Computing, 2002.
  


• Maintaining all-pairs approximate shortest paths under deletion of edges.
  Surender Baswana, Ramesh Hariharan, Sandeep Sen.
  Proceedings of the 13th Annual Symposium on Discrete Algorithms, 2003.
  

The Exact Complexity of String Matching

• Tighter Upper Bounds on the Exact Complexity of String Matching.
  R. Cole and R. Hariharan.
  SIAM Journal on Computing, Vol. 26, No. 3, pp. 803--856, 1997.
  33rd IEEE Symposium on Foundations of Computer Science, pp. 600--609, Oct. 1992.
  


• Tighter Lower Bounds on the Exact Complexity of String Matching.
  R. Cole, R. Hariharan, M. Paterson, U. Zwick.
  SIAM Journal on Computing., Vol. 24, No. 1, pp. 30--45, 1995.
  2nd Israel Symposium on Theoretical Computer Science, pp. 59--68, Jun. 1993.
  

Suffix Trees

• Faster Suffix Tree Construction with Missing Suffix Links.
  R. Cole, R. Hariharan.
  SIAM J. Comput. 33(1):26-42, 2003
  32nd Annual ACM Symposium on Theory of Computing, pp. 407--415, May 2000.
  
  
• Optimal Parallel Suffix Tree Construction.
  R. Hariharan.
  STOC 94 Special Issue of Journal of Computer and System Sciences, Vol. 55, No. 1, pp. 44--69, Aug 1997.
  26th ACM Symposium on Theory of Computing, pp. 290--299, May 1994.
  

Tree Pattern Matching

• Tree Pattern Matching and Subset Matching in $O(n\log^3 m)$ Deterministic Time.
  R. Cole, R. Hariharan, P. Indyk.
  Journal submission not made yet.
  7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 245--254, Jan. 1999.
  


• Tree Pattern Matching to Subset Matching in Linear Time.
  R. Cole, R. Hariharan.
  SIAM J. Comput. 32(4): 1056-1066 (2003)
  29th ACM Symposium on Theory of Computing, pp. 66--75, May 1997.
  

Pattern Matching Variations

• String Matching over a General Matching Relation.
  R. Hariharan and S. Muthukrishnan.
  Information and Computation, Vol. 122, No. 1, pp. 140--148, 1995.
  18th Annual Symposium on Foundations of Software Technology and Theoretical Computer Science, LNCS 652, pp. 356--367, Dec. 1992.
  


• Optimal Parallel Construction of the Smallest Automaton Recognizing all Substrings of a String.
  D. Breslauer, R. Hariharan.
  Parallel Processing Letters, Vol. 6, No. 1, pp. 35--44, 1996.
  


• Parallel Two-Dimensional Witness Computation.
  R. Cole, Z. Galil, R. Hariharan, S. Muthukrishnan, K. Park.
  Information and Computation 188(1): 20-67 (2004)
  34th IEEE Symposium on Foundations of Computer Science, pp. 248--258, Nov. 1993.
  


• An Optimal Constant Time Parallel Algorithm for 2D Pattern Matching.
  M. Crochemore, L. Gasieniec, R. Hariharan, S. Muthukrishnan, W. Rytter.
  SIAM Journal on Computing, 27, 3, pp. 668--681, 1998.
  34th IEEE Symposium on Foundations of Computer Science, pp. 248--258, Nov. 1993.
  


• Optimal Parallel Algorithms for Prefix Matching.
  R. Hariharan, S. Muthukrishnan.
  Journal submission not made yet.
  21st International Colloquia on Automata, Languages and Programming, pp. 203--214, Jun. 1994.
  


• Approximate String Matching: A Simpler Faster Algorithm.
  R. Cole, R. Hariharan.
  SIAM Journal on Computing, 31(6): 1761-178, 2002.
  6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 463--472, Jan. 1998.
  


• Verifying Candidate Matches in Sparse and Wildcard Matching.
  R. Cole, R. Hariharan.
  Journal submission not made yet.
  34nd Annual ACM Symposium on Theory of Computing, 2002.
  


• Swap Matching in $O(m \log m \log |\Sigma| )$ time.
  A. Amir, R. Cole, R. Hariharan, M. Lewenstein, E. Porat.
  Inf. Comput. 181(1): 57-74 (2003) 11th ACM-SIAM Symposium on Discrete Algorithms, 2001.
  


• String Matching in $\tilde{O}(\sqrt{n}+\sqrt{m})$ Quantum Time.
  R. Hariharan, V. Vinay.
  Journal of Discrete Algorithms, Vol. 2, No. 1, 2001.
  

Biology-Related Stuff

• Polypurine-polypyrimidine sequences in complete bacterial genomes: preference for polypurines in protein-coding regions.
  S. Raghavan, R. Hariharan, S.K. Brahmachari.
  Gene, 242(1-2), pp. 275--283, 2000.
  


• The Restriction Mapping Problem Revisited.
  R. Hariharan, G. Pandurangan.
  Journal of Computer and System Sciences, 65(3): 526-544, 2002.
  


• The Analysis of Microarray Data.
  R. Hariharan.
  Pharmacogenomics. 4(4), 477--497, 2003.
  


• Endocytosis by random initiation and stabilization of clathrin coated pits.
  M. Ehrlich, W. Boll, A. van Oijen, R. Hariharan, K. Chandran, M. Nilbert, T. Kirchhausen.
  Cell, 118, 591--605, 2004.
  


• MultiMCS: A Fast Algorithm for the Maximum Common Substructure Problem on Multiple Molecules
  Ramesh Hariharan, Anand Janakiraman, Ramaswamy Nilakantan, Bhupender Singh, Sajith Varghese, Gregory Landrum, and Ansgar Schuffenhauer
  J. Chem. Inf. Model., Mar 2011
  


• Next-Generation Sequencing of Human Mitochondrial Reference Genomes Uncovers High Heteroplasmy Frequency.
  Maria Ximena Sosa, I. K. Ashok Sivakumar, Samantha Maragh, Vamsi Veeramachaneni, Ramesh Hariharan, Minothi Parulekar, Karin M. Fredrikson, Timothy T. Harkins, Jeffrey Lin, Andrew B. Feldman, Pramila Tata, Georg B. Ehret, Aravinda Chakravarti
  PLoS Computational Biology, 8(10), 2012
  

Geometry

• Efficient Expected-Case Algorithms for Planar Point Location.
  S. Arya, S.W. Cheng, R. Hariharan, D. Mount.
  Scandinavian Workshop on Algorithm Theory, pp. 353--366, Jul 2000.
  


• Short-cuts on Star, Source and Planar Unfoldings.
  Vijay Chandru, Ramesh Hariharan, Narasimha M. Krishnakumar.
  Journal submission not made yet.
  Foundations of Software Technology and Theoretical Computer Science, 2004.
  

Cuts, Connectivity, Arborescences, Edge-Splitting

• A Fast Algorithm for Computing Steiner Edge Connectivity.
  R.Cole, R.Hariharan.
  35th Annual ACM Symposium on Theory of Computing, 2003.
  


• Fast edge splitting and Edmonds' arborescence construction for unweighted graphs.
  Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi.
  Journal submission not made yet.
  Annual ACM-SIAM Symposium on Discrete Algorithms, 2008, pp. 455-464.
  


• Efficient algorithms for computing all low s-t edge connectivities and related problems
  Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi.
  Annual ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 127--136.
  


• An �(mn) Gomory-Hu tree construction algorithm for unweighted graphs.
  Submitted to SICOMP special issue for STOC 2008.
  Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi.
  Annual ACM-SIAM Symposium on Theory of Computing, 2008, pp. 605-614
  


• Fast Edge Orientation for Unweighted Graphs
  Anand Bhalgat, Ramesh Hariharan.
  Journal submission not made yet.
  Annual ACM-SIAM Symposium on Discrete Algorithms, 2009.
  


• A General Framework for Graph Sparsification
  Wai Shing Fung, Ramesh Hariharan, Nicholas Harvey, Debmalya Panigrahi
  Journal submission not made yet.
  Annual ACM-SIAM Symposium on Theory of Computing, 2011
  

Assorted Stuff

• Faster Algorithms for Minimum Cycle Basis in Directed Graphs.
  Ramesh Hariharan, Telikepalli Kavitha, Kurt Mehlhorn
  SIAM J. Comput. (SIAMCOMP) 38(4):1430-1447 (2008)
  ICALP (1) 2006: 250-261


• Lower Bounds for Embedding Graphs into Graphs of Smaller Characteristic.
  K. V. M. Naidu, H. Ramesh.
  Journal submission not made yet.
  Foundations of Software Technology and Theoretical Computer Science, 2002.
  


• A 2.5 Factor Approximation Algorithm for the $k$-MST Problem.
  S. Arya, H. Ramesh.
  Information Processing Letters, 65(3), pp. 117-118, 1998.
  


• A Faster Implementation of the Goemans-Williamson Clustering Algorithm.
  R. Cole, R. Hariharan, M. Lewenstein, E. Porat.
  Journal submission not made yet.
  11th ACM-SIAM Symposium on Discrete Algorithms, 2001.
  


• Markovian Coupling v/s Conductance for the Jerrum-Sinclair Chain.
  V.S. Anil Kumar, R. Hariharan.
  Random Structures and Algorithms, 18, pp. 1--17, 2001.
  40th Annual IEEE Symposium on Foundations of Computer Science, pp. 241--252, Oct. 1999.
  


• A Randomized Algorithm for Large Scale Support Vector Learning.
  Krishnan S, C. Bhattacharyya, R. Hariharan.
  21st Annual Conference on Neural Information Processing Systems (NIPS), 2007.
  

Popular Articles

• Is it Prime or not?
  Samasya.


• Who will win the toss?
  Resonance.


• Turing and animal coat patterns
  Current Science