File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Approximated distributed minimum vertex cover algorithms for bounded degree graphs

TitleApproximated distributed minimum vertex cover algorithms for bounded degree graphs
Authors
KeywordsApproximation results
Bounded degree graphs
Distributed algorithm
Maximal degree
Minimum vertex cover
Issue Date2010
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 16th Annual International Computing and Combinatorics Conference (COCOON 2010), Nha Trang, Vietnam, 19-21 July 2010. In Lecture Notes in Computer Science, 2010, v. 6196, p. 100–109 How to Cite?
AbstractIn this paper, two distributed algorithms for the minimum vertex cover problem are given. In the unweighted case, we propose a 2.5-approximation algorithm with round complexity O(Δ), where Δ is the maximal degree of G, improving the previous 3-approximation result with the same round complexity O(Δ). For the weighted case, we give a 4-approximation algorithm with round complexity O(Δ). © 2010 Springer-Verlag Berlin Heidelberg.
DescriptionLNCS v. 6196 is the Conference Proceedings of COCOON 2010
Persistent Identifierhttp://hdl.handle.net/10722/129585
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorZhang, Yen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-12-23T08:39:30Z-
dc.date.available2010-12-23T08:39:30Z-
dc.date.issued2010en_HK
dc.identifier.citationThe 16th Annual International Computing and Combinatorics Conference (COCOON 2010), Nha Trang, Vietnam, 19-21 July 2010. In Lecture Notes in Computer Science, 2010, v. 6196, p. 100–109en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/129585-
dc.descriptionLNCS v. 6196 is the Conference Proceedings of COCOON 2010-
dc.description.abstractIn this paper, two distributed algorithms for the minimum vertex cover problem are given. In the unweighted case, we propose a 2.5-approximation algorithm with round complexity O(Δ), where Δ is the maximal degree of G, improving the previous 3-approximation result with the same round complexity O(Δ). For the weighted case, we give a 4-approximation algorithm with round complexity O(Δ). © 2010 Springer-Verlag Berlin Heidelberg.en_HK
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectApproximation results-
dc.subjectBounded degree graphs-
dc.subjectDistributed algorithm-
dc.subjectMaximal degree-
dc.subjectMinimum vertex cover-
dc.titleApproximated distributed minimum vertex cover algorithms for bounded degree graphsen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-14031-0_13en_HK
dc.identifier.scopuseid_2-s2.0-77955037047en_HK
dc.identifier.hkuros178325en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77955037047&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume6196 LNCSen_HK
dc.identifier.spage100en_HK
dc.identifier.epage109en_HK
dc.publisher.placeGermanyen_HK
dc.description.otherThe 16th Annual International Computing and Combinatorics Conference (COCOON 2010), Nha Trang, Vietnam, 19-21 July 2010. In Lecture Notes in Computer Science, 2010, v. 6196, p. 100–109-
dc.identifier.scopusauthoridZhang, Y=7601329213en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats