Given a set of intervals (pairs of real numbers), we look at the problem of finding a minimal partition of this set such that no element of the partition contains two overlapping intervals. We ...exhibit a Θ(N log N) algorithm which is optimal. The problem has applications in LSI layout design and job scheduling.
In this paper, we present an O(1) time algorithm to solve the minimum coloring problem defined on a set of intervals, which is also called the channel assignment problem. This problem has not been ...solved in O(1) time before, even on the idealistic CRCW PRAM model. For large-sized problems, it is desirable to have fast hardware-solutions. Our algorithm is based on the processor arrays with a reconfigurable bus system (abbreviated to PARBS) that consists of a processor array and a reconfigurable bus system. In order to solve this problem with constant time complexity, we first transform the "left-edge" channel assignment algorithm to the parenthesis-matching problem. Based on this novel scheme, we are able to explore constant-time parallel algorithms to solve the minimum coloring problem for n intervals, which is also called the channel assignment problem, on a PARBS with O(n/sup 2/) processors.< >
Full Color Theorems for L(2,1)-Colorings Fishburn, Peter C.; Roberts, Fred S.
SIAM journal on discrete mathematics,
01/2006, Volume:
20, Issue:
2
Journal Article
Peer reviewed
The span $\lambda$ (G) of a graph G is the smallest k for which G's vertices can be L(2,1)-colored, i.e., colored with integers in $\{0,1, \ldots, k \}$ so that adjacent vertices' colors differ by at ...least 2, and colors of vertices at distance two differ. G is full-colorable if some such coloring uses all colors in $\{0,1, \ldots, \lambda (G) \}$ and no others. We prove that all trees except stars are full-colorable. The connected graph G with the smallest number of vertices exceeding $\lambda$ (G) which is not full-colorable is C6. We describe an array of other connected graphs that are not full-colorable and go into detail on full-colorability of graphs of maximum degree four or less.
No-hole L(2,1)-colorings Fishburn, Peter C.; Roberts, Fred S.
Discrete Applied Mathematics,
08/2003, Volume:
130, Issue:
3
Journal Article
Peer reviewed
Open access
An
L(2,1)-
coloring of a graph
G is a coloring of
G's vertices with integers in {0,1,…,
k} so that adjacent vertices’ colors differ by at least two and colors of distance-two vertices differ. We ...refer to an
L(2,1)-coloring as a coloring. The
span
λ(
G) of
G is the smallest
k for which
G has a coloring, a
span coloring is a coloring whose greatest color is
λ(
G), and the
hole index
ρ(
G) of
G is the minimum number of colors in {0,1,…,
λ(
G)} not used in a span coloring. We say that
G is
full-colorable if
ρ(
G)=0. More generally, a coloring of
G is a
no-hole coloring if it uses all colors between 0 and its maximum color. Both colorings and no-hole colorings were motivated by channel assignment problems. We define the
no-hole span
μ(
G) of
G as ∞ if
G has no no-hole coloring; otherwise
μ(
G) is the minimum
k for which
G has a no-hole coloring using colors in {0,1,…,
k}.
Let
n denote the number of vertices of
G, and let
Δ be the maximum degree of vertices of
G. Prior work shows that all non-star trees with
Δ⩾3 are full-colorable, all graphs
G with
n=
λ(
G)+1 are full-colorable,
μ(
G)⩽
λ(
G)+
ρ(
G) if
G is not full-colorable and
n⩾
λ(
G)+2, and
G has a no-hole coloring if and only if
n⩾
λ(
G)+1. We prove two extremal results for colorings. First, for every
m⩾1 there is a
G with
ρ(
G)=
m and
μ(
G)=
λ(
G)+
m. Second, for every
m⩾2 there is a connected
G with
λ(
G)=2
m,
n=
λ(
G)+2 and
ρ(
G)=
m.
The channel assignment problem is the problem of efficiently assigning frequencies to radio transmitters located at various places such that communications do not interfere. Griggs and Yeh 5 ...introduced a variation of the channel assignment problem known as the L(2, 1)-colorings of graphs. An L(2, 1)-coloring of a graph G = (V, E) is a vertex coloring f: V(G) → {0, 1, 2,..., k}, k ≥ 2 such that |f(u) - f(v)| ≥ 2 for all uv ∊ E(G) and |f(u) - f(v)| ≥ 1 if d(u, v) = 2. The span of G, λ(G), is the smallest integer k for which G has an L(2, 1)-coloring. An L(2, 1)-coloring f is irreducible if there does not exist an L(2, 1)-coloring g such that g(u) ≤ f(u) for all u ∊ V(G) and g(v) < f(v) for some v ∊ V(G). A span coloring is an L(2, 1)-coloring whose greatest color is λ(G). Let f be an L(2, 1)-coloring that uses colors from 0 to k. Then h ∊ (0, k) is a hole if there is no vertex v in V(G) such that f(v) = h. In this paper, we investigate maximum number of holes in span colorings of certain classes of graphs. We give exact values for the maximum number of holes in a span coloring of a path, cycle, star, complete bipartite graph and characterize complete graphs in terms of their maximum number of holes. Upper bounds for an arbitrary graph and other classes of graphs are also given.
For a given graph
G of order
n, a
k-
L
(
2
,
1
)
-labelling is defined as a function
f
:
V
(
G
)
→
{
0
,
1
,
2
,
…
k
}
such that
|
f
(
u
)
-
f
(
v
)
|
⩾
2
when
d
G
(
u
,
v
)
=
1
and
|
f
(
u
)
-
f
(
v
...)
|
⩾
1
when
d
G
(
u
,
v
)
=
2
. The
L
(
2
,
1
)
-labelling number of
G, denoted by
λ
(
G
)
, is the smallest number
k such that
G has a
k-
L
(
2
,
1
)
-labelling. The hole index
ρ
(
G
)
of
G is the minimum number of integers not used in a
λ
(
G
)
-
L
(
2
,
1
)
-labelling of
G. We say
G is full-colorable if
ρ
(
G
)
=
0
; otherwise, it will be called non-full colorable. In this paper, we consider the graphs with
λ
(
G
)
=
2
m
and
ρ
(
G
)
=
m
, where
m is a positive integer. Our main work generalized a result by Fishburn and Roberts No-hole
L
(
2
,
1
)
-colorings, Discrete Appl. Math. 130 (2003) 513–519.
For a given graph
G of order
n, a
k-
L
(
2
,
1
)
-labelling is defined as a function
f
:
V
(
G
)
→
{
0
,
1
,
2
,
…
,
k
}
such that
|
f
(
u
)
-
f
(
v
)
|
⩾
2
when
d
G
(
u
,
v
)
=
1
and
|
f
(
u
)
-
f
(
...v
)
|
⩾
1
when
d
G
(
u
,
v
)
=
2
. The
L
(
2
,
1
)
-labelling number of
G, denoted by
λ
(
G
)
, is the smallest number
k such that
G has a
k-
L
(
2
,
1
)
-labelling. The consecutive
L
(
2
,
1
)
-labelling is a variation of
L
(
2
,
1
)
-labelling under the condition that the labelling
f is an onto function. The consecutive
L
(
2
,
1
)
-labelling number of
G is denoted by
λ
¯
(
G
)
. Obviously,
λ
(
G
)
⩽
λ
¯
(
G
)
⩽
|
V
(
G
)
|
-
1
if
G admits a consecutive
L
(
2
,
1
)
-labelling. In this paper, we investigate the graphs with
λ
¯
(
G
)
=
|
V
(
G
)
|
-
1
and the graphs with
λ
¯
(
G
)
=
λ
(
G
)
, in terms of their sizes, diameters and the number of components.
PDF
