57 citations · 175 across the 38 of their papers we have counts for
3 papers · 1 filter
Bicriteria Network Design Problems
Madhav V. Marathe, R. Ravi, Ravi Sundaram +3
We study a general class of bicriteria network design problems. A generic problem in this class is as follows: Given an undirected graph and two minimization objectives (under diff…
Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems
Madhav V. Marathe, Harry B. Hunt, Richard E. Stearns +1
We study the efficient approximability of basic graph and logic problems in the literature when instances are specified hierarchically as in \cite{Le89} or are specified by 1-dimen…
The Complexity of Planar Counting Problems
Harry B. Hunt, Madhav V. Marathe, Venkatesh Radhakrishnan +1
We prove the #P-hardness of the counting problems associated with various satisfiability, graph and combinatorial problems, when restricted to planar instances. These problems incl…