A 1-local asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs
From MaRDI portal
Publication:1040645
DOI10.1007/S00453-008-9203-1zbMath1177.68246OpenAlexW2122488564MaRDI QIDQ1040645
Francis Y. L. Chin, Hong Zhu, Yong Zhang
Publication date: 25 November 2009
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10722/129980
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Online algorithms; streaming algorithms (68W27)
Related Items (4)
1-local 7/5-competitive Algorithm for Multicoloring Hexagonal Graphs ⋮ An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space ⋮ 1-local 7/5-competitive algorithm for multicoloring hexagonal graphs ⋮ Online call control in cellular networks revisited
Uses Software
Cites Work
- Efficient on-line frequency allocation and call control in cellular networks
- Greedy online frequency allocation in cellular networks
- Worst-case analysis of a dynamic channel assignment strategy
- 2-local 5/4-competitive algorithm for multicoloring triangle-free 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
- Frequency Allocation Problems for Linear Cellular Networks
- Models and solution techniques for frequency assignment problems
- Static frequency assignment in cellular networks
- Channel assignment and multicolouring of the induced subgraphs of the triangular lattice
This page was built for publication: A 1-local asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs
