This paper proposes a exible stochastic automaton-based network partitioning algorithm that is capable of find-ing the optimal k-way partition with respect to a broad range of cost functions, and given various constra...
详细信息
ISBN:
(纸本)0780389166
This paper proposes a exible stochastic automaton-based network partitioning algorithm that is capable of find-ing the optimal k-way partition with respect to a broad range of cost functions, and given various constraints, in directed and weighted graphs. Further, this iterative algorithm requires only local computation, with respect to the graph. Hence, by incorporating a distributed stopping criterion, we have been able to solve certain partitioning problems in a totally distributed manner. In this article, this inuence model-based partitioning algorithm is motivated and introduced, and is shown to find the optimal partition for a large class of problems. Also, a conceptual discussion of why the algorithm might be expected to find good partitions quickly is included, and the performance of the algorithm is illustrated through examples. Applications in partitioning distributed communicatin-agentnetworks, sensor systems, and power grids are discussed.
暂无评论