1-local 7/5-competitive algorithm for multicoloring hexagonal graphs

DOI10.1007/S00453-011-9562-XzbMath1262.68143OpenAlexW2116077644MaRDI QIDQ1945170

Petra Šparl, Janez Žerovnik, Rafał Witkowski

Publication date: 3 April 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9562-x

zbMATH Keywords

cellular networkhexagonal graphfrequency assignmentmulticoloringcompetitivehexagonal1-local

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Communication, information (94A99) Coloring of graphs and hypergraphs (05C15)

Related Items (2)

Maximum induced matching of hexagonal graphs ⋮ 3-path vertex cover and dissociation number of hexagonal graphs

Cites Work

• Unnamed Item
• A 1-local asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs
• Finding a five bicolouring of a triangle-free subgraph of the triangular lattice
• 2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs
• A technique for multicoloring triangle-free hexagonal graphs
• 1-Local 17/12-Competitive Algorithm for Multicoloring Hexagonal Graphs
• Distributed Online Frequency Assignment in Cellular Networks
• Channel assignment and weighted coloring
• 2-local <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mn>4</mml:mn><mml:mo stretchy="false">/</mml:mo><mml:mn>3</mml:mn></mml:math>-competitive algorithm for multicoloring hexagonal graphs
• Static frequency assignment in cellular networks

This page was built for publication: 1-local 7/5-competitive algorithm for multicoloring hexagonal graphs