Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Heuristic Algorithms for the L(2,1)-Labeling Problem
verfasst von : B. S. Panda, Preeti Goel
Erschienen in: Swarm, Evolutionary, and Memetic Computing
Verlag: Springer Berlin Heidelberg
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
An
L
(2, 1)-labeling of a graph
G
is an assignment
f
from the vertex set
V
(
G
) to the set of nonnegative integers such that |
f
(
x
) −
f
(
y
)| ≥ 2 if
x
and
y
are adjacent and |
f
(
x
) −
f
(
y
)| ≥ 1 if
x
and
y
are at distance two for all
x
and
y
in
V
(
G
). The span of an
L
(2,1)-labeling
f
is the maximum value of
f
(
x
) over all vertices
x
of
G
. The
L
(2,1)-labeling number of a graph
G
, denoted as
λ
(
G
), is the least integer
k
such that
G
has an
L
(2,1)-labeling with span
k
.
Since the decision version of the
L
(2,1)-labeling problem is NP-complete, it is important to investigate heuristic approaches. In this paper, we first implement some heuristic algorithms and then perform an analysis of the obtained results.