Article: A 1-local asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • 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
2011 Impact Factor: 0.604
2011 SCImago Journal Rankings: 0.042
DOIhttp://dx.doi.org/10.1007/s00453-008-9203-1
ISI Accession Number IDWOS:000265880400007
ReferencesReferences in Scopus
DC Field
Value
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
2011 Impact Factor: 0.604
2011 SCImago Journal Rankings: 0.042
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
Author Affiliations
  1. The University of Hong Kong
  2. East China Normal University