Conference Paper: A 1-local 13/9-competitive algorithm for multicoloring hexagonal graphs
| Title | A 1-local 13/9-competitive algorithm for multicoloring hexagonal graphs |
|---|---|
| Authors | Chin, FYL1 Zhang, Y1 Zhu, H2 |
| Issue Date | 2007 |
| Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
| Citation | Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4598 LNCS, p. 526-536 [How to Cite?] |
| Abstract | In the frequency allocation problem, we are given a mobile telephone network, whose geographical coverage area is divided into cells, wherein phone calls are serviced by assigning frequencies to them so that no two calls emanating from the same or neighboring cells are assigned the same frequency. The problem is to use the frequencies efficiently, i.e., minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph. In this paper, we give a 1-local 4/3-competitive distributed algorithm for multicoloring a triangle-free hexagonal graph, which is a special case. Based on this result, we then propose a 1-local 13/9-competitive algorithm for multicoloring the (general-case) hexagonal graph, thereby improving the previous 1-local 3/2-competitive algorithm. © Springer-Verlag Berlin Heidelberg 2007. |
| ISSN | 0302-9743 2011 SCImago Journal Rankings: 0.034 |
| References | References in Scopus |
| dc.contributor.author | Chin, FYL |
|---|---|
| dc.contributor.author | Zhang, Y |
| dc.contributor.author | Zhu, H |
| dc.date.accessioned | 2010-09-25T14:53:04Z |
| dc.date.available | 2010-09-25T14:53:04Z |
| dc.date.issued | 2007 |
| dc.description.abstract | In the frequency allocation problem, we are given a mobile telephone network, whose geographical coverage area is divided into cells, wherein phone calls are serviced by assigning frequencies to them so that no two calls emanating from the same or neighboring cells are assigned the same frequency. The problem is to use the frequencies efficiently, i.e., minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph. In this paper, we give a 1-local 4/3-competitive distributed algorithm for multicoloring a triangle-free hexagonal graph, which is a special case. Based on this result, we then propose a 1-local 13/9-competitive algorithm for multicoloring the (general-case) hexagonal graph, thereby improving the previous 1-local 3/2-competitive algorithm. © Springer-Verlag Berlin Heidelberg 2007. |
| dc.description.nature | Link_to_subscribed_fulltext |
| dc.identifier.citation | Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4598 LNCS, p. 526-536 [How to Cite?] |
| dc.identifier.epage | 536 |
| dc.identifier.hkuros | 137496 |
| dc.identifier.issn | 0302-9743 2011 SCImago Journal Rankings: 0.034 |
| dc.identifier.scopus | eid_2-s2.0-37849016440 |
| dc.identifier.spage | 526 |
| dc.identifier.uri | http://hdl.handle.net/10722/93172 |
| dc.identifier.volume | 4598 LNCS |
| dc.language | eng |
| dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
| dc.publisher.place | Germany |
| dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| dc.relation.references | References in Scopus |
| dc.title | A 1-local 13/9-competitive algorithm for multicoloring hexagonal graphs |
| dc.type | Conference_Paper |
Author Affiliations
- The University of Hong Kong
- East China Normal University