2 papers
cs.CC1998
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…
cs.CC1998
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…