Database Reference
In-Depth Information
Fig. 17.4: An example of decomposition using articulation points.
After creating the constraints graph G, [25] identifies all its articulation points
(also known as cut-vertexes). The rationale behind this process is that the removal
of a cut-vertex will disconnect graph G and the best cut-vertex u
nm
will be the one
that leads to the largest number of connected components in G. Each of these com-
ponents will then itself constitute a new subproblem to be solved independently
from the others. As presented in [25] the computation of the best articulation point
can be achieved in linear time O(V+E) through a DFS traversal of the graph.
After identifying the best articulation point, the next step is to remove the corre-
sponding u
nm
variable from graph G. Then, each component of the resulting graph
corresponds to a new subproblem (i.e., is a new CSP) that can be derived in linear
time and be solved independently. To provide the same solution as the original CSP,
the solutions of the various created subproblems need to be cross-examined. This
process is discussed in Section 17.1.3.
A final step to be addressed involves the situation in which no single cut-vertex
can be found in the graph. In such a case, an empirical approach is proposed in
[25] which is based on the premises that nodes having high degrees in graph G are
more likely than others to correspond to cut-vertexes. The runtime of the empirical
approach is also linear in the number of vertexes and edges of graph G.
Figure 17.4
demonstrates an example of decomposition using articulation points. In this graph,
we denote as “cut-vertex”, the vertex which, when removed, leads to a disconnected
graph having the maximum number of connected components (here 3).
