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
Lau, HYTing, HF
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?
DOI: http://dx.doi.org/10.1023/A:1011672624624
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
1382-6905
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.370
ISI Accession Number ID
WOS:000170784300003
References
References in Scopus

 

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