Information Technology Reference
In-Depth Information
16
30
33
18
10
26
31
1
17
13
ₒ
ₒ
29
4
9
28
11
14
34
32
2
3
6
7
8
15
5
23
24
25
27
20
22
12
19
21
(a) original graph
(b) generate a dual collision graph
16
30
10
33
18
26
1
17
31
13
ₒ
29
4
9
28
11
14
34
32
2
3
6
8
15
5
23
24
25
7
27
20
22
12
19
21
(c) color vertices of the collision graph
(d) color edges of the original graph
Fig. 2.
T
he proposed pipeline for coloring the edges of the Zachary's Karate Club Graph: (a) the
original graph; (b) the dual collision graph, with each node representing an edge of the original
graph, and positioned at the center of that edge; (c) the collision graph, with nodes colored to
maximize color differences along the edges; (d) the original graph, with edges colored using the
node coloring in (c).
The problem of coloring the edges of
G
then becomes that of coloring nodes of the
collision graph
G
c
.Let
C
∈ C
∈
V
c
,
we want to find a coloring scheme such that the color of each node in the collision
graph is as different to its neighbors as possible. This task can be posed as a MaxMin
optimization problem:
be the color space, and
c
(
i
)
be the color of a node
i
2
2
4
4
1
1
3
3
(a)
(b)
(c)
Fig. 3.
A
n illustration of the rationale for collision condition C4. (a) Two edges that do not cross.
(b) When nodes are shown, it is difficult to tell if there are two edges (1
ₔ
2and3
ₔ
4), or three
edges (1
ₔ
2, 1
ₔ
4and1
ₔ
3), or whether there even exists an edge3
ₔ
2. (c) After coloring
each edges with a distinctive color, it is clear that there are two edges, 1
ₔ
2and3
ₔ
4
arg max
c
:
V
c
ₒC
min
{
i
,
j
}∈
E
c
w
ij
c
(
i
)
−
c
(
j
)
,
(1)
where
w
ij
>
0isaweight inversely proportional to how important it is to differentiate
colors of nodes
i
and
j
,and
c
(
i
)
−
c
(
j
)
is a measure of the difference between the
colors assigned to the two nodes.
