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

DOI10.1016/j.ipl.2004.02.017zbMath1192.68917OpenAlexW2020207405MaRDI 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 coloringgraph algorithmsapproximation algorithmscellular networksfrequency planning2-local distributed algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items

1-local 7/5-competitive algorithm for multicoloring hexagonal graphs ⋮ A linear time algorithm for \(7\)-\([3\)coloring triangle-free hexagonal graphs] ⋮ Simpler multicoloring of triangle-free hexagonal graphs ⋮ 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 1-local asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs ⋮ 2-local distributed algorithms for generalized coloring of hexagonal graphs

Cites Work

• Unnamed Item
• 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
• Channel assignment and weighted coloring
• Static frequency assignment in cellular networks
• Channel assignment and multicolouring of the induced subgraphs of the triangular lattice