File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

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

TitleA 1-local asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs
Authors
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
Citation
Algorithmica (New York), 2009, v. 54 n. 4, p. 557-567 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 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.
Persistent Identifierhttp://hdl.handle.net/10722/129980
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.905
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorZhang, Yen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorZhu, Hen_HK
dc.date.accessioned2010-12-23T08:45:07Z-
dc.date.available2010-12-23T08:45:07Z-
dc.date.issued2009en_HK
dc.identifier.citationAlgorithmica (New York), 2009, v. 54 n. 4, p. 557-567en_HK
dc.identifier.issn0178-4617en_HK
dc.identifier.urihttp://hdl.handle.net/10722/129980-
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.en_HK
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_HK
dc.relation.ispartofAlgorithmica (New York)en_HK
dc.rightsThe original publication is available at www.springerlink.comen_US
dc.subjectHexagonal graphsen_HK
dc.subjectMulticoloringen_HK
dc.subjectOnline algorithmen_HK
dc.titleA 1-local asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0178-4617&volume=54&issue=4&spage=557–567&epage=&date=2009&atitle=A+1-local+asymptotic+13/9-competitive+algorithm+for+multicoloring+hexagonal+graphs-
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturepostprint-
dc.identifier.doi10.1007/s00453-008-9203-1en_HK
dc.identifier.scopuseid_2-s2.0-67349144685en_HK
dc.identifier.hkuros178353en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-67349144685&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume54en_HK
dc.identifier.issue4en_HK
dc.identifier.spage557en_HK
dc.identifier.epage567en_HK
dc.identifier.isiWOS:000265880400007-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridZhang, Y=7601329213en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridZhu, H=7404664147en_HK
dc.identifier.issnl0178-4617-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats