caa a22 4500 44580503X CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110201xx s 000 0 eng 10.1007/s00453-009-9302-7 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9302-7 Exact Algorithms for L (2,1)-Labeling of Graphs [Elektronische Daten] [Frédéric Havet, Martin Klazar, Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff] The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph G=(V,E) into an interval of integers {0, ,k} is an L(2,1)-labeling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed k≥4, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive O *((k+1)n) algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of k=4, where the running time of our algorithm is O(1.3006n). Furthermore we show that dynamic programming can be used to establish an O(3.8730n) algorithm to compute an optimal L(2,1)-labeling. Springer Science+Business Media, LLC, 2009 Graph nationallicence Algorithm nationallicence Moderately exponential time algorithm nationallicence L (2,1)-labeling nationallicence Havet Frédéric Projet Mascotte I3S (CNRS & UNSA) and INRIA, INRIA Sophia-Antipolis, 2004 route des Lucioles, BP 93, 06902, Sophia-Antipolis Cedex, France aut Klazar Martin Department of Applied Mathematics and Institute for Theoretical Computer Science, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czech Republic aut Kratochvíl Jan Department of Applied Mathematics and Institute for Theoretical Computer Science, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czech Republic aut Kratsch Dieter Laboratoire d'Informatique Théorique et Appliquée, Université Paul Verlaine-Metz, 57045, Metz Cedex 01, France aut Liedloff Mathieu Laboratoire d'Informatique Fondamentale d'Orléans, Université d'Orléans, 45067, Orléans Cedex 2, France aut Algorithmica Springer-Verlag 59/2(2011-02-01), 169-194 0178-4617 59:2<169 2011 59 453 https://doi.org/10.1007/s00453-009-9302-7 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9302-7 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Havet Frédéric Projet Mascotte I3S (CNRS & UNSA) and INRIA, INRIA Sophia-Antipolis, 2004 route des Lucioles, BP 93, 06902, Sophia-Antipolis Cedex, France aut NATIONALLICENCE 700 1- Klazar Martin Department of Applied Mathematics and Institute for Theoretical Computer Science, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czech Republic aut NATIONALLICENCE 700 1- Kratochvíl Jan Department of Applied Mathematics and Institute for Theoretical Computer Science, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czech Republic aut NATIONALLICENCE 700 1- Kratsch Dieter Laboratoire d'Informatique Théorique et Appliquée, Université Paul Verlaine-Metz, 57045, Metz Cedex 01, France aut NATIONALLICENCE 700 1- Liedloff Mathieu Laboratoire d'Informatique Fondamentale d'Orléans, Université d'Orléans, 45067, Orléans Cedex 2, France aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/2(2011-02-01), 169-194 0178-4617 59:2<169 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer