File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: The Greedier the Better: An Efficient Algorithm for Approximating Maximum Independent Set

TitleThe Greedier the Better: An Efficient Algorithm for Approximating Maximum Independent Set
Authors
KeywordsApproximation
Combinatorial optimization
Greedy algorithms
Maximum independent set
Issue Date2001
PublisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905
Citation
Journal Of Combinatorial Optimization, 2001, v. 5 n. 4, p. 411-420 How to Cite?
AbstractThe classical greedy heuristic for approximating maximum independent set is simple and efficient. It achieves a performance ratio of (Δ + 2)/3, where Δ is the maximum node degree of the input graph. All known algorithms for the problem with better performance ratios are much more complicated and inefficient. In this paper, we propose a natural extension of the greedy heuristic. It is as simple and as efficient as the classical greedy heuristic. By a careful analysis on the structure of the intermediate graphs manipulated by our heuristic, we prove that the performance ratio is improved to (Δ + 3)/3.25.
Persistent Identifierhttp://hdl.handle.net/10722/89029
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.370
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorLau, HYen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-09-06T09:51:30Z-
dc.date.available2010-09-06T09:51:30Z-
dc.date.issued2001en_HK
dc.identifier.citationJournal Of Combinatorial Optimization, 2001, v. 5 n. 4, p. 411-420en_HK
dc.identifier.issn1382-6905en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89029-
dc.description.abstractThe classical greedy heuristic for approximating maximum independent set is simple and efficient. It achieves a performance ratio of (Δ + 2)/3, where Δ is the maximum node degree of the input graph. All known algorithms for the problem with better performance ratios are much more complicated and inefficient. In this paper, we propose a natural extension of the greedy heuristic. It is as simple and as efficient as the classical greedy heuristic. By a careful analysis on the structure of the intermediate graphs manipulated by our heuristic, we prove that the performance ratio is improved to (Δ + 3)/3.25.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905en_HK
dc.relation.ispartofJournal of Combinatorial Optimizationen_HK
dc.subjectApproximationen_HK
dc.subjectCombinatorial optimizationen_HK
dc.subjectGreedy algorithmsen_HK
dc.subjectMaximum independent seten_HK
dc.titleThe Greedier the Better: An Efficient Algorithm for Approximating Maximum Independent Seten_HK
dc.typeArticleen_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1023/A:1011672624624en_HK
dc.identifier.scopuseid_2-s2.0-0042879930en_HK
dc.identifier.hkuros70677en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0042879930&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume5en_HK
dc.identifier.issue4en_HK
dc.identifier.spage411en_HK
dc.identifier.epage420en_HK
dc.identifier.isiWOS:000170784300003-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridLau, HY=54970872400en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.issnl1382-6905-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats