20 citations · 206 across the 49 of their papers we have counts for
Showing 2001Show all
2 papers · 1 filter
cs.CC2001★ 3 cited
Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP
Edith Hemaspaandra, Jörg Rothe, Holger Spakowski
For both the edge deletion heuristic and the maximum-degree greedy heuristic, we study the problem of recognizing those graphs for which that heuristic can approximate the size of…
cs.CC2001
Using the No-Search Easy-Hard Technique for Downward Collapse
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
The top part of the preceding figure [figure appears in actual paper] shows some classes from the (truth-table) bounded-query and boolean hierarchies. It is well-known that if eith…