57 citations · 95 across the 10 of their papers we have counts for
3 papers · 1 filter
Geometry based heuristics for unit disk graphs
Madhav V. Marathe, H. Breu, Harry B. Hunt +2
Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP-hard optimization probl…
The complexity of approximating PSPACE-Complete problems for hierarchical specifications
Madhav V. Marathe, Harry B. Hunt, S. S. Ravi
We extend the concept of polynomial time approximation algorithms to apply to problems for hierarchically specified graphs, many of which are PSPACE-complete. Assuming P != PSPACE,…
Spanning trees short or small
R. Ravi, R. Sundaram, Madhav V. Marathe +2
We study the problem of finding small trees. Classical network design problems are considered with the additional constraint that only a specified number of nodes are required…