Multicoloring of cannonball graphs

Authors

  • Petra Šparl University of Maribor
  • Rafał Witkowski Adam Mickiewicz University
  • Janez Žerovnik University of Ljubljana

DOI:

https://doi.org/10.26493/1855-3974.528.751

Keywords:

Graph coloring, approximation algorithm, frequency planning, cellular networks.

Abstract

The frequency allocation problem that appeared in the design of cellular telephone networks can be regarded as a multicoloring problem on a weighted hexagonal graph, which opened some still interesting mathematical problems. We generalize the multicoloring problem into higher dimension and present the first approximation algorithms for multicoloring of the so called cannonball graphs.

Published

2015-03-03

Issue

Section

Articles