
06307575
j
2014d.00770
Mati\'c, Dragan
Bo\v{z}i\'c, Milan
Maximally balanced connected partition problem in graphs: application in education.
Teach. Math. 15, No. 2, 121132 (2012).
2012
,
EN
K34
N64
P24
graph partitioning
course organization
computeraided instruction
Summary: 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.