STOC Conference 1999 Conference Paper
Covering Rectilinear Polygons with Axis-Parallel Rectangles
- V. S. Anil Kumar 0001
- H. Ramesh
Author name cluster
H. Ramesh
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
4 papers
2 author rows
Possible papers
4FOCS Conference 1999 Conference Paper
Markovian Coupling vs. Conductance for the Jerrum-Sinclair Chain
- V. S. Anil Kumar 0001
- H. Ramesh
We show that no Markovian coupling argument can prove rapid mixing of the Jerrum-Sinclair Markov chain for sampling almost uniformly from the set of perfect and near perfect matchings of a given graph. In particular, we show that there exists a bipartite graph G such that any Markovian coupling argument on the Jerrum-Sinclair Markov chain for G must necessarily take time exponential in the number of vertices in G. This holds even when the coupling argument is time-variant, i. e. , the transition probabilities used by the coupling process depend upon the history of the process. In contrast, the above Markov chain on G has been shown to mix in polynomial time using conductance arguments.
I&C Journal 1995 Journal Article
String Matching under a General Matching Relation
- S. Muthukrishnan
- H. Ramesh
In standard string matching, each symbol matches only itself, In other string matching problems, e. g. , the string matching with "don′t-cares" problem, a symbol may match several symbols. In general, an arbitrary many-to-many matching relation might hold between symbols. We consider a general string matching problem in which such a matching relation is specified and those positions in a text t, of length n, are sought at which the pattern p, of length m, matches under this relation. Depending upon the existence of a simple and easily recognizable property in the given matching relation, we show that string matching either requires linear (i. e. , O(n + m)) time or is at least as hard as boolean convolution. As an application, we show that the matching relations of several independently studied string matching problems do indeed fall into the latter (hard) category. We also give a generic string matching algorithm that works far any matching relation and has complexity o(nm) except for very "large" matching relations.