1998 | OriginalPaper | Buchkapitel
A Hamiltonian Approach to the Assignment of Non-reusable Frequencies
verfasst von : Dimitris A. Fotakis, Paul G. Spirakis
Erschienen in: Foundations of Software Technology and Theoretical Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The problem of Radio Labelling is to assign distinct integer labels to all the vertices of a graph, such that adjacent vertices get labels at distance at least two. The objective is to minimize the label span. Radio labelling is a combinatorial model for frequency assignment in case that the transmitters are not allowed to operate at the same channel.We show that radio labelling is related to TSP(1,2). Hence, it is ${\cal NP}$-complete and MAX-SNP-hard. Then, we present a polynomial-time algorithm for computing an optimal radio labelling, given a coloring of the graph with constant number of colors. Thus, we prove that radio labelling is in ${\cal P}$ for planar graphs. We also obtain a $\frac{3}{2}$-approximation ${\cal NC}$ algorithm and we prove that approximating radio labelling in graphs of bounded maximum degree is essentially as hard as in general graphs.We obtain similar results for TSP(1,2). In particular, we present the first $\frac{3}{2}$-approximation ${\cal NC}$ algorithm for TSP(1,2), and we prove that dense instances of TSP(1,2) do not admit a PTAS, unless ${\cal P}= {\cal NP}$.