| dc.description.abstract | This thesis concentrates on algorithms for finding all the maximal k-edge-connected components
in a given graph G = (V, E) where V and E represent the set of vertices and the set of edges,
respectively, which are further used to develop a scale reduction procedure for the maximum clique
problem. The proposed scale-reduction approach is based on the observation that a subset C of
k + 1 vertices is a clique if and only if one needs to remove at least k edges in order to disconnect
the corresponding induced subgraph G[C] (that is, G[C] is k-edge-connected). Thus, any clique
consisting of k + 1 or more vertices must be a subset of a single k-edge connected component of
the graph. This motivates us to look for subgraphs with edge connectivity at least k in a given
graph G, for an appropriately selected k value.
We employ the method based on the concept of the auxiliary graph, previously proposed in
the literature, for finding all maximal k-edge-connected subgraphs. This method processes the
input graph G to construct a tree-like graphic structure A, which stores the information of the edge
connectivity between each pair of vertices of the graph G. Moreover, this method could provide
us the maximal k-edge-connected components for all possible k and it shares the same vertex set
V with the graph G.
With the information from the auxiliary graph, we implement the scale reduction procedure
for the maximum clique problem on sparse graphs based on the k-edge-connected subgraphs with
appropriately selected values of k. Furthermore, we performed computational experiments to evaluate
the performance of the proposed scale reduction and compare it to the previously used k-core
method. The comparison results present the advancement of the scale reduction with k-edge-connected
subgraphs. Even though our scale reduction algorithm based has higher time complexity,
it is still of interest and deserves further investigation. | en |
