Biology Reference
In-Depth Information
Fig. 7.1. Connectivity Index of nodes A,B,C,D is 3. Connectivity Index of E,F,G is 2. Connectivity
Index of H is 0.
the network connectivity in optimization models, we can impose constraints on
the connectivity indices of the nodes [8].
The
CARDINALITY CONSTRAINED CNDP
can be formulated in a similar man-
ner to the the
CNDP
above. Recall that in this problem, we are given an integer
L
V
such that the
connectivity index
of the remaining nodes in the vertex deleted sub-
graph
G
(
V
∈
Z
, and we are interested in determining a minimum cardinality subset
A
⊆
A
) does not exceed
L
.
Using the same definition of the variables as in the previous subsection, we can
formulate the
CC
-
CNDP
as the following integer linear programming problem.
\
Minimize
i∈V
(CC-CNDP)
v
i
(7.10)
s.t.
u
ij
+
v
i
+
v
j
≥
1
,
∀
(
i,j
)
∈
E,
(7.11)
u
ij
+
u
jk
−
u
ki
≤
1
,
∀
(
i,j,k
)
∈
V,
(7.12)
u
ij
−
u
jk
+
u
ki
≤
1
,
∀
(
i,j,k
)
∈
V,
(7.13)
−
u
ij
+
u
jk
+
u
ki
≤
1
,
∀
(
i,j,k
)
∈
V,
(7.14)
u
ij
≤
L,
(7.15)
i,j∈V
u
ij
∈{
0
,
1
}
,
∀
i,j
∈
V,
(7.16)
v
i
∈{
0
,
1
}
,
∀
i
∈
V,
(7.17)
where
L
is the maximum allowable connectivity index for any node in the vertex
deleted subgraph
G
(
V
A
). Notice that the objective is to minimize the num-
ber of nodes deleted. Constraints (7.11) follow exactly as in the
CNDP
model.
Also, Constraints (7.12)-(7.14) are equivalent to the constraint
u
ij
+
u
jk
+
\
Search WWH ::
Custom Search