A Flexible Stochastic Automaton-Based Algorithm for Network Self-Partitioning
Abstract
This article proposes a flexible and distributed stochastic automaton-based network partitioning algorithm that is capable of finding the optimal k-way partition with respect to a broad range of cost functions, and given various constraints, in directed and weighted graphs. Specifically, we motivate the distributed partitioning (self-partitioning) problem, introduce the stochastic automaton-based partitioning algorithm, and show that the algorithm finds the optimal partition with probability 1 for a large class of partitioning tasks. Also, a discussion of why the algorithm can be expected to find good partitions quickly is included, and its performance is further illustrated through examples. Finally, applications to mobile/sensor classification in ad hoc networks, fault-isolation in electric power systems, and control of autonomous vehicle teams are pursued in detail.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jul 01, 2008
- Source ID
- 10.1080/15501320701260063
Entities
People
- Ali Saberi
- Bernard Lesieutre
- Sandip Roy
- Yan Wan
Organizations
- Lawrence Berkeley National Laboratory
- Office of Naval Research
- Washington State University