Title: Approximating the L(h, k)-labelling problem

Authors: Magnus M. Halldorsson

Addresses: Department of Computer Science, University of Iceland, IS-107 Reykjavik, Iceland

Abstract: The (h, k)-colouring problem, better known as the L(h, k)-labelling problem, is that of vertex colouring an undirected graph with non-negative integers so that adjacent vertices receive colours that differ by at least h and vertices of distance-2 receive colours that differ by at least k. We give tight bounds on approximations for this problem on general graphs as well as for bipartite, chordal and split graphs.

Keywords: L(h, k)-labelling; distance-constrained colouring; frequency allocation; approximation algorithms; vertex colouring; undirected graphs; wireless networks; mobile networks.

DOI: 10.1504/IJMNDI.2006.010813

International Journal of Mobile Network Design and Innovation, 2006 Vol.1 No.2, pp.113 - 117

Published online: 05 Sep 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article