A heuristic approach for dividing graphs into bi-connected components with a size constraint

作者：Jovanovic Raka^*; Nishi Tatsushi; Voss Stefan

来源：Journal of Heuristics, 2017, 23(2): 111-136.

DOI：10.1007/s10732-017-9331-3

• Bi-connected graphs
• 2-Connected
• Breadth first search
• Growth algorithm
• Graph partitioning
• Heuristic

In this paper we propose a new problem of finding the maximal bi-connected partitioning of a graph with a size constraint (MBCPG-SC). With the goal of finding approximate solutions for the MBCPG-SC, a heuristic method is developed based on the open ear decomposition of graphs. Its essential part is an adaptation of the breadth first search which makes it possible to grow bi-connected subgraphs. The proposed randomized algorithm consists of growing several subgraphs in parallel. The quality of solutions generated in this way is further improved using a local search which exploits neighboring relations between the subgraphs. In order to evaluate the performance of the method, an algorithm for generating pseudo-random unit disc graphs with known optimal solutions is created. Computational experiments have also been conducted on graphs representing electrical distribution systems for the real-world problem of dividing them into a system of fault tolerant interconnected microgrids. The experiments show that the proposed method frequently manages to find optimal solutions and has an average error of only a few percent to known optimal solutions. Further, it manages to find high quality approximate solutions for graphs having up to 10,000 nodes in reasonable time.

• 出版日期2017-6