The application of graph partitioning to modern scientific problems with various objectives has been attempted by many researchers in a variety of fields. Such applications are many and the following may be mentioned only to name a few examples. Applications such as vulnerability assessment of large power systems, power system islanding, design of VLSI circuits, dynamic system modeling and simulation, innovation graph state estimation, internet-like network partitioning, task mapping of parallel computation, database management, archaeological dating, power system transient studies, load balancing of parallel computing, molecular dynamics, DNA sequencing, categorizing amino acids, circuit netlists partitioning, etc. have been reported in the literature. In this paper, the complexities of the application of graph partitioning in modern scientific applications are thoroughly investigated in order to shed some light on this issue with such a diverse domain of applications. Fundamental graph theoretical and matrix algebraic concepts are discussed with sufficient examples. Application of these concepts to the problem of power system islanding is presented with suggestions to improve the speed and the objective function being used.

Keywords