File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: A 1-local asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs
  • Basic View
  • Metadata View
  • XML View
TitleA 1-local asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs
 
AuthorsZhang, Y1
Chin, FYL1
Zhu, H2
 
KeywordsHexagonal graphs
Multicoloring
Online algorithm
 
Issue Date2009
 
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
 
CitationAlgorithmica (New York), 2009, v. 54 n. 4, p. 557-567 [How to Cite?]
DOI: http://dx.doi.org/10.1007/s00453-008-9203-1
 
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 asymptotic 4/3-competitive distributed algorithm for multicoloring a triangle-free hexagonal graph, which is a special case of hexagonal graph. Based on this result, we then propose a 1-local asymptotic13/9-competitive algorithm for multicoloring the (general-case) hexagonal graph, thereby improving the previous 1-local 3/2-competitive algorithm. © 2008 Springer Science+Business Media, LLC.
 
ISSN0178-4617
2013 Impact Factor: 0.567
 
DOIhttp://dx.doi.org/10.1007/s00453-008-9203-1
 
ISI Accession Number IDWOS:000265880400007
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorZhang, Y
 
dc.contributor.authorChin, FYL
 
dc.contributor.authorZhu, H
 
dc.date.accessioned2010-12-23T08:45:07Z
 
dc.date.available2010-12-23T08:45:07Z
 
dc.date.issued2009
 
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 asymptotic 4/3-competitive distributed algorithm for multicoloring a triangle-free hexagonal graph, which is a special case of hexagonal graph. Based on this result, we then propose a 1-local asymptotic13/9-competitive algorithm for multicoloring the (general-case) hexagonal graph, thereby improving the previous 1-local 3/2-competitive algorithm. © 2008 Springer Science+Business Media, LLC.
 
dc.description.naturepostprint
 
dc.identifier.citationAlgorithmica (New York), 2009, v. 54 n. 4, p. 557-567 [How to Cite?]
DOI: http://dx.doi.org/10.1007/s00453-008-9203-1
 
dc.identifier.doihttp://dx.doi.org/10.1007/s00453-008-9203-1
 
dc.identifier.epage567
 
dc.identifier.hkuros178353
 
dc.identifier.isiWOS:000265880400007
 
dc.identifier.issn0178-4617
2013 Impact Factor: 0.567
 
dc.identifier.issue4
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-67349144685
 
dc.identifier.spage557
 
dc.identifier.urihttp://hdl.handle.net/10722/129980
 
dc.identifier.volume54
 
dc.languageeng
 
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
 
dc.publisher.placeUnited States
 
dc.relation.ispartofAlgorithmica (New York)
 
dc.relation.referencesReferences in Scopus
 
dc.rightsThe original publication is available at www.springerlink.com
 
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License
 
dc.subjectHexagonal graphs
 
dc.subjectMulticoloring
 
dc.subjectOnline algorithm
 
dc.titleA 1-local asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs
 
dc.typeArticle
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Zhang, Y</contributor.author>
<contributor.author>Chin, FYL</contributor.author>
<contributor.author>Zhu, H</contributor.author>
<date.accessioned>2010-12-23T08:45:07Z</date.accessioned>
<date.available>2010-12-23T08:45:07Z</date.available>
<date.issued>2009</date.issued>
<identifier.citation>Algorithmica (New York), 2009, v. 54 n. 4, p. 557-567</identifier.citation>
<identifier.issn>0178-4617</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/129980</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 asymptotic 4/3-competitive distributed algorithm for multicoloring a triangle-free hexagonal graph, which is a special case of hexagonal graph. Based on this result, we then propose a 1-local asymptotic13/9-competitive algorithm for multicoloring the (general-case) hexagonal graph, thereby improving the previous 1-local 3/2-competitive algorithm. &#169; 2008 Springer Science+Business Media, LLC.</description.abstract>
<language>eng</language>
<publisher>Springer New York LLC. The Journal&apos;s web site is located at http://link.springer.de/link/service/journals/00453/index.htm</publisher>
<relation.ispartof>Algorithmica (New York)</relation.ispartof>
<rights>The original publication is available at www.springerlink.com</rights>
<rights>Creative Commons: Attribution 3.0 Hong Kong License</rights>
<subject>Hexagonal graphs</subject>
<subject>Multicoloring</subject>
<subject>Online algorithm</subject>
<title>A 1-local asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs</title>
<type>Article</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=0178-4617&amp;volume=54&amp;issue=4&amp;spage=557&#8211;567&amp;epage=&amp;date=2009&amp;atitle=A+1-local+asymptotic+13/9-competitive+algorithm+for+multicoloring+hexagonal+graphs</identifier.openurl>
<description.nature>postprint</description.nature>
<identifier.doi>10.1007/s00453-008-9203-1</identifier.doi>
<identifier.scopus>eid_2-s2.0-67349144685</identifier.scopus>
<identifier.hkuros>178353</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-67349144685&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>54</identifier.volume>
<identifier.issue>4</identifier.issue>
<identifier.spage>557</identifier.spage>
<identifier.epage>567</identifier.epage>
<identifier.isi>WOS:000265880400007</identifier.isi>
<publisher.place>United States</publisher.place>
<bitstream.url>http://hub.hku.hk/bitstream/10722/129980/1/Content.pdf</bitstream.url>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. East China Normal University