TY - GEN
T1 - A decomposition approach for solving critical clique detection problems
AU - Walteros, Jose L.
AU - Pardalos, Panos M.
PY - 2012
Y1 - 2012
N2 - The problem of detecting critical elements in a network involves the identification of a subset of elements (nodes, arcs, paths, cliques, etc.) whose deletion minimizes a connectivity measure over the induced network. This problem has attracted significant attention in recent years because of its applications in several fields such as telecommunications, social network analysis, and epidemic control. In this paper we examine the problem of detecting critical cliques (CCP). We first introduce a mathematical formulation for the CCP as an integer linear program. Additionally, we propose a two-stage decomposition strategy that first identifies a candidate clique partition and then uses this partition to reformulate and solve the problem as a generalized critical node problem (GCNP). To generate candidate clique partitions we test two heuristic approaches and solve the resulting (GCNP) using a commercial optimizer. We test our approach in a testbed of 13 instances ranging from 25 to 100 nodes.
AB - The problem of detecting critical elements in a network involves the identification of a subset of elements (nodes, arcs, paths, cliques, etc.) whose deletion minimizes a connectivity measure over the induced network. This problem has attracted significant attention in recent years because of its applications in several fields such as telecommunications, social network analysis, and epidemic control. In this paper we examine the problem of detecting critical cliques (CCP). We first introduce a mathematical formulation for the CCP as an integer linear program. Additionally, we propose a two-stage decomposition strategy that first identifies a candidate clique partition and then uses this partition to reformulate and solve the problem as a generalized critical node problem (GCNP). To generate candidate clique partitions we test two heuristic approaches and solve the resulting (GCNP) using a commercial optimizer. We test our approach in a testbed of 13 instances ranging from 25 to 100 nodes.
KW - clique partitioning
KW - critical clique detection
KW - Critical element detection
UR - https://www.scopus.com/pages/publications/84864369648
U2 - 10.1007/978-3-642-30850-5_34
DO - 10.1007/978-3-642-30850-5_34
M3 - Conference contribution
AN - SCOPUS:84864369648
SN - 9783642308499
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 393
EP - 404
BT - Experimental Algorithms - 11th International Symposium, SEA 2012, Proceedings
T2 - 11th International Symposium on Experimental Algorithms SEA 2012
Y2 - 7 June 2012 through 9 June 2012
ER -