Skip to main content
Algorithms for the Balanced Edge Partitioning Problem
Lecture Notes in Computer Science: Experimental Algorithms, 6th International Workshop
  • Ekaterina Smorodkina
  • Mayur Thakur
  • Daniel R. Tauritz, Missouri University of Science and Technology

We consider the problem of minimizing communication overhead while balancing load across cooperative agents. In the past, similar problems have been modeled as the balanced node partitioning problem, where the objective is to partition the nodes into components such that each component has roughly the same number of nodes while the number of edges connecting components is minimized. We describe some real-world scenarios where one needs to find partitions in which all components have an approximately equal number of edges, while minimizing the number of edges connecting components. We introduce the (k, r)-BALANCED EDGE PARTITIONING problem to model this type of scenario and present approximation algorithms for this problem on certain graphs. In addition, we present five heuristics for the restricted case of the problem. We evaluate these heuristics on three kinds of graphs: power network-like graphs, preferential attachment graphs, and the class of spatial preferential attachment graphs that we introduce in this paper. Our results show that the choice of the heuristic with the best results depends on the properties of the input graph and the quality of our solution depends on the initial conditions.

Meeting Name
6th Workshop on Experimental Algorithms (WEA 2007) (2007: Jun. 6-9, Rome, Italy)
Computer Science
Keywords and Phrases
  • Approximation Algorithms,
  • Graph Theory,
  • Heuristic Algorithms,
  • Optimization,
  • Problem Solving,
  • Resource Allocation, Balanced Graph Partitioning,
  • Graph Partitioning,
  • Kernighan-Lin Heuristics, Edge Detection
International Standard Book Number (ISBN)
Document Type
Article - Conference proceedings
Document Version
File Type
© 2007 Springer, All rights reserved.
Publication Date
Citation Information
Ekaterina Smorodkina, Mayur Thakur and Daniel R. Tauritz. "Algorithms for the Balanced Edge Partitioning Problem" Lecture Notes in Computer Science: Experimental Algorithms, 6th International Workshop Vol. 4525 (2007) p. 311 - 323 ISSN: 0302-9743
Available at: