A Flexible Stochastic Automaton-Based Algorithm for Network Self-Partitioning

Yan Wan, Sandip Roy, Ali Saberi and Bernard Lesieutre

International Journal of Distributed Sensor Networks, 2008, vol. 4, issue 3, 223-246

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.

Keywords: Partitioning; Distributed Partitioning; Islanding; Stochastic Automata (search for similar items in EconPapers)
Date: 2008
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.sagepub.com/doi/10.1080/15501320701260063 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:intdis:v:4:y:2008:i:3:p:223-246

DOI: 10.1080/15501320701260063

Access Statistics for this article

More articles in International Journal of Distributed Sensor Networks
Bibliographic data for series maintained by SAGE Publications ().