✦ LIBER ✦

It is hard to know when greedy is good for finding independent sets

✍ Scribed by Hans L. Bodlaender; Dimitrios M. Thilikos; Koichi Yamazaki

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 591 KB
Volume: 61
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(96)00208-6

No coin nor oath required. For personal study only.

✦ Synopsis

The classes A, and S, are defined as the classes of those graphs, where the minimum degree greedy algorithm always approximates the maximum independent set (MIS) problem within a factor of r, respectively, where this algorithm has a sequence of choices that yield an output that is at most a factor r from optimal, r > 1 a rational number. It is shown that deciding whether a given graph belongs to A, is coNP-complete for any fixed r 2 1, and deciding whether a given graph belongs to SI is DP-hard, and belongs to A2P.

📜 SIMILAR VOLUMES

Recognizing when greed can approximate m

Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP

✍ Edith Hemaspaandra; Jörg Rothe 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 511 KB

investigate the computational complexity of the problem of whether the Minimum Degree Greedy Algorithm can approximate a maximum independent set of a graph within a constant factor of r, for fixed rational r > 1. They denote this problem by S, and prove that for each rational r 2 1, S, is coNP-hard.

A Good Duke is Hard to Find; Someday My

A Good Duke is Hard to Find; Someday My Duke Will Come; A Duke Worth Fighting For

✍ Christina Britton 📂 Fiction 🌐 English ⚖ 141 B 👁 3 views