Abstract

This paper presents the maximally balanced connected partition (MBCP) problem in graphs. MBCP is to partition a weighted connected graph into the two connected subgraphs with minimal misbalance, i.e., the sums of vertex weights in two subgraphs are as much equal as possible. The MBCP has many applications both in science and practice, including education. As an illustration of the application of MBCP, a concrete example of organizing the course Selected Topics of Number Theory is analyzed and one balanced partition is suggested. Several algorithms for solving this NP hard problem are also studied.

Keywords: Graph partitioning; computers in education; course organization.

Pages:  121$-$132     

Volume  XV ,  Issue  2 ,  2012