File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-642-14031-0_13
- Scopus: eid_2-s2.0-77955037047
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Approximated distributed minimum vertex cover algorithms for bounded degree graphs
| Title | Approximated distributed minimum vertex cover algorithms for bounded degree graphs |
|---|---|
| Authors | |
| Keywords | Approximation results Bounded degree graphs Distributed algorithm Maximal degree Minimum vertex cover |
| Issue Date | 2010 |
| Publisher | Springer 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? |
| Abstract | In 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. |
| Description | LNCS v. 6196 is the Conference Proceedings of COCOON 2010 |
| Persistent Identifier | http://hdl.handle.net/10722/129585 |
| ISSN | 2023 SCImago Journal Rankings: 0.606 |
| References |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Zhang, Y | en_HK |
| dc.contributor.author | Chin, FYL | en_HK |
| dc.contributor.author | Ting, HF | en_HK |
| dc.date.accessioned | 2010-12-23T08:39:30Z | - |
| dc.date.available | 2010-12-23T08:39:30Z | - |
| dc.date.issued | 2010 | en_HK |
| dc.identifier.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 | en_HK |
| dc.identifier.issn | 0302-9743 | en_HK |
| dc.identifier.uri | http://hdl.handle.net/10722/129585 | - |
| dc.description | LNCS v. 6196 is the Conference Proceedings of COCOON 2010 | - |
| dc.description.abstract | In 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.language | eng | en_US |
| dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | en_HK |
| dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | en_HK |
| dc.rights | The original publication is available at www.springerlink.com | - |
| dc.subject | Approximation results | - |
| dc.subject | Bounded degree graphs | - |
| dc.subject | Distributed algorithm | - |
| dc.subject | Maximal degree | - |
| dc.subject | Minimum vertex cover | - |
| dc.title | Approximated distributed minimum vertex cover algorithms for bounded degree graphs | en_HK |
| dc.type | Conference_Paper | en_HK |
| dc.identifier.email | Chin, FYL:chin@cs.hku.hk | en_HK |
| dc.identifier.email | Ting, HF:hfting@cs.hku.hk | en_HK |
| dc.identifier.authority | Chin, FYL=rp00105 | en_HK |
| dc.identifier.authority | Ting, HF=rp00177 | en_HK |
| dc.description.nature | link_to_subscribed_fulltext | - |
| dc.identifier.doi | 10.1007/978-3-642-14031-0_13 | en_HK |
| dc.identifier.scopus | eid_2-s2.0-77955037047 | en_HK |
| dc.identifier.hkuros | 178325 | en_US |
| dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-77955037047&selection=ref&src=s&origin=recordpage | en_HK |
| dc.identifier.volume | 6196 LNCS | en_HK |
| dc.identifier.spage | 100 | en_HK |
| dc.identifier.epage | 109 | en_HK |
| dc.publisher.place | Germany | en_HK |
| dc.description.other | 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 | - |
| dc.identifier.scopusauthorid | Zhang, Y=7601329213 | en_HK |
| dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_HK |
| dc.identifier.scopusauthorid | Ting, HF=7005654198 | en_HK |
| dc.identifier.issnl | 0302-9743 | - |