COVERING RECTILINEAR POLYGONS WITH AXIS-PARALLEL RECTANGLES ∗ (2008)
Abstract. We give an O ( log n) factor approximation algorithm for covering a rectilinear polygon with holes using axis-parallel rectangles. This is the first polynomial time approximation algorithm...
Rewriting P Systems with Conditional Communication: Improved Hierarchies (2008)
Summary. We consider here a variant of rewriting P systems [1], where communication is controlled by the contents of the strings, not by the evolution rules used for obtaining these strings. Some new...
Sunil Arya, Siu-wing Cheng, David M. Mount, H. Ramesh
Abstract. Planar point location is among the most fundamental search problems in computational geometry. Although this problem has been heavily studied from the perspective of worst-case query time,...
An Algorithm for Enumerating All Spanning Trees of a Directed Graph (2007)
Sanjiv Kapoor, Vijay Kumar, H. Ramesh
We present an algorithm for enumerating all spanning trees of a directed graph with V vertices, E edges and N spanning trees. The algorithm takes O(logV ) time per spanning tree; more precisely, it...
Coupling vs. Conductance for the (2007)
Jerrum-sinclair Chain, H. Ramesh
We address the following question: is the Causal Coupling method as strong as the Conductance method in showing rapid mixing of Markov Chains? A causal coupling is a coupling which uses only past and...
We show how to determine whether a given pattern p of length m occurs in a given text t of length n in ~ O(
log n) factor approximation algorithm for covering a rectilinear polygon with holes using axis-parallel rectangles. This is the rst polynomial time approximation algorithm for this problem with a...
Mesocolic hernia: An unusual internal hernia (2007)
Tauro, L, Vijaya, G, D«SQ»Souza, C, Ramesh, H, Shetty, S, Hegde, B, ...
Prakash, K, Ramesh, H, Jacob, G, Venugopal, A, Lekha, V, Varma, D, ...
Covering Rectilinear Polygons with Axis-Parallel Rectangles (2003)
We give an $O(\sqrt{\log n})$ factor approximation algorithm for covering a rectilinear polygon with holes using axis-parallel rectangles. This is the first polynomial time approximation algorithm...
Covering Rectilinear Polygons with Axis-Parallel Rectangles (2003)
We give an $O(\sqrt{\log n})$ factor approximation algorithm for covering a rectilinear polygon with holes using axis-parallel rectangles. This is the first polynomial time approximation algorithm...
Lower bounds for embedding graphs into graphs of smaller characteristic (2002)
The subject of graph embeddings deals with embedding a finite point set in a given metric space by points in another target metric space in such a way that distances in the new space are at least as...
Lower bounds for embedding graphs into graphs of smaller characteristic (2002)
The subject of graph embeddings deals with embedding a finite point set in a given metric space by points in another target metric space in such a way that distances in the new space are at least as...
The restriction mapping problem revisited (2002)
In computational molecular biology, the aim of restriction mapping is to locate the restriction sites of a given enzyme on a DNA molecule. Double digest and partial digest are two well-studied...
The restriction mapping problem revisited (2002)
In computational molecular biology, the aim of restriction mapping is to locate the restriction sites of a given enzyme on a DNA molecule. Double digest and partial digest are two well-studied...
Coupling vs. conductance for the Jerrum-Sinclair chain (2001)
We address the following question: is the causal coupling method as strong as the conductance method in showing rapid mixing of Markov chains? A causal coupling is a coupling which uses only past and...
String Matching in ${\tilde O}(\sqrt{n}+\sqrt{m})$ Quantum Time (2000)
We show how to determine whether a given pattern p of length m occurs in a given text t of length n in ${\tilde O}(\sqrt{n}+\sqrt{m})$\footnote{${\tilde O}$ allows for logarithmic factors in m and...
An Algorithm for Numerating All Spanning Trees of a Directed Graph (2000)
We present an O.NV CV3/ time algorithm for enumerating all spanning trees of a directed graph.This improves the previous best known bound of O.NECV C E/ [1] when V2 Do.N/, which will be true for most...
Efficient Expected-Case Algorithms for Planar Point Location (2000)
Arya, Sunil, Cheng, Siu-Wing, Mount, David M, Ramesh, H
Planar point location is among the most fundamental search problems in computational geometry. Although this problem has been heavily studied from the perspective of worst-case query time, there has...
Hardness of set cover with intersection 1 (2000)
Kumar, Anil VS, Arya, Sunil, Ramesh, H
We consider a restricted version of the general Set Covering problem in which each set in the given set system intersects with any other set in at most 1 element. We show that the Set Covering...
An Algorithm for Numerating All Spanning Trees of a Directed Graph (2000)
We present an O.NV CV3/ time algorithm for enumerating all spanning trees of a directed graph.This improves the previous best known bound of O.NECV C E/ [1] when V2 Do.N/, which will be true for most...
Efficient Expected-Case Algorithms for Planar Point Location (2000)
Arya, Sunil, Cheng, Siu-Wing, Mount, David M, Ramesh, H
Planar point location is among the most fundamental search problems in computational geometry. Although this problem has been heavily studied from the perspective of worst-case query time, there has...
Hardness of set cover with intersection 1 (2000)
Kumar, Anil VS, Arya, Sunil, Ramesh, H
We consider a restricted version of the general Set Covering problem in which each set in the given set system intersects with any other set in at most 1 element. We show that the Set Covering...
An algorithm for enumerating all spanning trees of a directed graph (2000)
) time algorithm for enumerating all spanning trees of a directed graph. This improves the previous best known bound of O(NE +V +E) ([1]) when V 2 = o(N), which will be true for most graphs. Here, N...
Efficient expected-case algorithms for planar point location (2000)
Sunil Arya, Siu-wing Cheng, David M. Mount, H. Ramesh
Abstract. Planar point location is among the most fundamental search problems in computational geometry. Although this problem has been heavily studied from the perspective of worst-case query time,...
Markovian Coupling vs. Conductance for the Jerrum-Sinclair Chain (1999)
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...
Markovian Coupling vs. Conductance for the Jerrum-Sinclair Chain (1999)
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...
Derandomizing approximation algorithms based on semidefinite programming (1999)
Abstract. Remarkable breakthroughs have been made recently in obtaining approximate solutions to some fundamental NP-hard problems, namely Max-Cut, Max k-Cut, Max-Sat, Max-Dicut, Max-bisection,...
Derandomizing approximation algorithms based on semidefinite programming (1999)
Abstract. Remarkable breakthroughs have been made recently in obtaining approximate solutions to some fundamental NP-Hard problems, namely Max-Cut, Max k-Cut, Max-Sat, Max-Dicut, Max-Bisection,...
A 2.5-factor approximation algorithm for the k-MST problem (1998)
The k-MST problem requires finding that subset of at least k vertices of a given graph whose Minimum Spanning Tree has least weight amongst all subsets of at least k vertices, There has been much...
A 2.5-factor approximation algorithm for the k-MST problem (1998)
The k-MST problem requires finding that subset of k vertices of a given graph whose Minimum Spanning Tree has least weight amongst all subsets of k vertices. There has been much work on this problem...
A 2.5-factor approximation algorithm for the k-MST problem (1998)
The k-MST problem requires finding that subset of at least k vertices of a given graph whose Minimum Spanning Tree has least weight amongst all subsets of at least k vertices. There has been much...
A 2.5 Factor Approximation Algorithm for the k-MST Problem (1997)
The k-MST problem requires finding that subset of at least k vertices of a given graph whose Minimum Spanning Tree has least weight amongst all subsets of at least k vertices. There has been much...
Derandomizing approximation algorithms based on semidefinite programming (1996)
Remarkable breakthroughs have been made recently in obtaining approximate solutions to some fundamental NP-hard problems, namely Max-Cut, Max k-Cut, Max-Sat, Max-Dicut, Max-bisection, k-vertex...
Derandomizing approximation algorithms based on semidefinite programming (1996)
Remarkable breakthroughs have been made recently in obtaining approximate solutions to some fundamental NP-hard problems, namely Max-Cut, Max k-Cut, Max-Sat, Max-Dicut, Max-bisection, k-vertex...
Algorithms for enumerating all spanning trees of undirected and weighted graphs (1995)
In this paper, we present algorithms for enumeration of spanning trees in undirected graphs, with and without weights. The algorithms use a search tree technique to construct a computation tree. The...
On Traversing Layered Graphs On-line (1995)
The following bounds on the competitive ratios of deterministic and randomized on-line algorithms for traversing width-w layered graphs are obtained. 1. A deterministic algorithm with a competitive...
Organizational analysis of a public enterprise- A case of HMT (1991)
Organizational analysis of a public enterprise
Friess, H, Shrikhande, S, Shrikhande, M, Martignoni, M, Kulli, C, Zimmermann, A, ...
Background and aims: Among various causes, nerve alterations and neuroimmune interactions have been suggested to participate in the generation of pain in chronic pancreatitis (CP). In this study, we...