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

Raka Jovanovic, Tatsushi Nishi, Stefan Voß

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)111-136
Number of pages26
JournalJournal of Heuristics
Issue number2-3
Publication statusPublished - Jun 1 2017
Externally publishedYes


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

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Networks and Communications
  • Control and Optimization
  • Management Science and Operations Research
  • Artificial Intelligence


Dive into the research topics of 'A heuristic approach for dividing graphs into bi-connected components with a size constraint'. Together they form a unique fingerprint.

Cite this