File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: A 1-local 13/9-competitive algorithm for multicoloring hexagonal graphs
  • Basic View
  • Metadata View
  • XML View
TitleA 1-local 13/9-competitive algorithm for multicoloring hexagonal graphs
 
AuthorsChin, FYL1
Zhang, Y1
Zhu, H2
 
Issue Date2007
 
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
CitationLecture 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?]
 
AbstractIn 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.
 
ISSN0302-9743
2013 SCImago Journal Rankings: 0.310
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorChin, FYL
 
dc.contributor.authorZhang, Y
 
dc.contributor.authorZhu, H
 
dc.date.accessioned2010-09-25T14:53:04Z
 
dc.date.available2010-09-25T14:53:04Z
 
dc.date.issued2007
 
dc.description.abstractIn 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.natureLink_to_subscribed_fulltext
 
dc.identifier.citationLecture 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.epage536
 
dc.identifier.hkuros137496
 
dc.identifier.issn0302-9743
2013 SCImago Journal Rankings: 0.310
 
dc.identifier.scopuseid_2-s2.0-37849016440
 
dc.identifier.spage526
 
dc.identifier.urihttp://hdl.handle.net/10722/93172
 
dc.identifier.volume4598 LNCS
 
dc.languageeng
 
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
dc.publisher.placeGermany
 
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
 
dc.relation.referencesReferences in Scopus
 
dc.titleA 1-local 13/9-competitive algorithm for multicoloring hexagonal graphs
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Chin, FYL</contributor.author>
<contributor.author>Zhang, Y</contributor.author>
<contributor.author>Zhu, H</contributor.author>
<date.accessioned>2010-09-25T14:53:04Z</date.accessioned>
<date.available>2010-09-25T14:53:04Z</date.available>
<date.issued>2007</date.issued>
<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</identifier.citation>
<identifier.issn>0302-9743</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/93172</identifier.uri>
<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. &#169; Springer-Verlag Berlin Heidelberg 2007.</description.abstract>
<language>eng</language>
<publisher>Springer Verlag. The Journal&apos;s web site is located at http://springerlink.com/content/105633/</publisher>
<relation.ispartof>Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</relation.ispartof>
<title>A 1-local 13/9-competitive algorithm for multicoloring hexagonal graphs</title>
<type>Conference_Paper</type>
<description.nature>Link_to_subscribed_fulltext</description.nature>
<identifier.scopus>eid_2-s2.0-37849016440</identifier.scopus>
<identifier.hkuros>137496</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-37849016440&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>4598 LNCS</identifier.volume>
<identifier.spage>526</identifier.spage>
<identifier.epage>536</identifier.epage>
<publisher.place>Germany</publisher.place>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. East China Normal University