Determining L(2,1)-Span in Polynomial Space

Details Determining L(2,1)-Span in Polynomial Space Determining L(2,1)-Span in Polynomial Space

2011-04-22

arxiv.org/abs/1104.4506v1

Computer Science

Discrete Mathematics

Scientific paper

A $k$-L(2,1)-labeling of a graph is a function from its vertex set into the set $\{0,...,k\}$, such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. It is known that finding the smallest $k$ admitting the existence of a $k$-L(2,1)-labeling of any given graph is NP-Complete. In this paper we present an algorithm for this problem, which works in time $O(\complexity ^n)$ and polynomial memory, where $\eps$ is an arbitrarily small positive constant. This is the first exact algorithm for L(2,1)-labeling problem with time complexity $O(c^n)$ for some constant $c$ and polynomial space complexity.

Affiliated with

Also associated with

No associations

Rating

Determining L(2,1)-Span in Polynomial Space does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Determining L(2,1)-Span in Polynomial Space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determining L(2,1)-Span in Polynomial Space will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-483737