Biology Reference
In-Depth Information
u
ki
V
, which ensures that if nodes
i
and
j
are in the same
component and nodes
j
and
k
are in the same component, then necessarily
i
and
k
belong to the same component (as in the
CNDP
model). Constraints (7.15) en-
sure that the connectivity indices of all nodes does not exceed
L
.The
CC
-
CNDP
is
also
=2
,
∀
(
i,j,k
)
∈
-hard as proved by Arulselvan et al [3]. For the application of interest in
this chapter, the
CC
-
CNDP
is the most applicable critical node optimization model.
Therefore as we consider solutions approaches and computational experiments in
the following sections, this is the problem on which we will focus.
NP
7.4. Heuristic Approaches for Critical Node Detection
Due to the computational complexity of the mathematical programming formula-
tions presented above, the prior work in this area has concentrated on the devel-
opment of efficient heuristics for critical node detection problems [2, 3, 7].
7.4.1.
Multi-Start Combinatorial Heuristic
Arulselvan et al. [3] have proposed an efficient combinatorial heuristic for the
CNDP
. Pseudo-code for the proposed algorithm is provided in Fig. 7.2. The
heuristic starts off by identifying a maximal independent set (MIS). This array
holds the set of non-critical nodes. In the main loop from lines 4-16, the proce-
dure iterates through the vertices and determines which of them can be added back
to the graph while still maintaining feasibility. If vertex
i
can be replaced, MIS is
augmented to include
i
in step 7, otherwise NoAdd is incremented. When NoAdd
is equal to
, then no nodes can be returned to the graph and OPT is
set to
TRUE
. The loop is then exited and the algorithm returns the set of critical
nodes, i.e.,
V
|
V
|−|
MIS
|
MIS.
The solution found by this procedure is then further improved through a local
search step and incorporated within a multi-start mechanism (see Fig. 7.3). Com-
putational testing was carried out on a benchmark network of the social interac-
tions of the terrorists involved in the 9
\
11 hijacking [18] and on some networks
generated by the authors. Their tests indicated that the heuristic is very effective
in producing optimal solutions in modest computing time as compared to solving
the mixed integer formulation of the problem using the branch-and-bound based
solver CPLEX [9].
\
Search WWH ::
Custom Search