2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs

DOI10.1016/j.ipl.2004.02.017zbMath1192.68917MaRDI QIDQ2390258

Petra Šparl, Janez Žerovnik

Publication date: 21 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.02.017

zbMATH Keywords

graph coloring; graph algorithms; approximation algorithms; cellular networks; frequency planning; 2-local distributed algorithms

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68W25: Approximation algorithms

68W15: Distributed algorithms

Related Items

2-local 7/6-competitive algorithm for multicolouring a sub-class of hexagonal graphs, On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, A linear time algorithm for \(7\)-\([3\)coloring triangle-free hexagonal graphs], Simpler multicoloring of triangle-free hexagonal graphs, A 1-local asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs, 1-local 7/5-competitive algorithm for multicoloring hexagonal graphs, 2-local distributed algorithms for generalized coloring of hexagonal graphs

Cites Work

• Corrigendum: Static frequency assignment in cellular networks
• Finding a five bicolouring of a triangle-free subgraph of the triangular lattice
• Distributed Online Frequency Assignment in Cellular Networks
• Static frequency assignment in cellular networks
• Channel assignment and multicolouring of the induced subgraphs of the triangular lattice
• Unnamed Item
• Unnamed Item