Distributed cycle detection and removal
Date
2018Source
IEEE Transactions on Control of Network SystemsVolume
5Issue
1Pages
194-204Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
In this paper, we provide distributed algorithms to detect and remove cycles in a directed relational graph by exploiting the underlying undirected communication graph; the relational graph models a relation among the agents, e.g., a pairwise ordering, while the communication graph captures how information can be shared among them. Specifically, we provide a synchronous distributed algorithm to detect cycles in the relational graph, by exploiting the fact that nodes with zero in-degree or zero outdegree can not be part of a cycle, and can be iteratively removed without creating new loops in the relational topology. The proposed algorithm considerably improves transmission efficiency (the number of messages and bandwidth required) compared to the state of the art. We demonstrate that the problem of making the relational graph acyclic by swapping the orientation of a minimum number of edges is NP-Complete and APX-Hard; for this reason, we develop an efficient, yet suboptimal, distributed algorithm to remove the cycles by swapping the direction of some of the links. The methodology provided in this paper finds application in several distributed control problems where the agents must be interconnected via a directed acyclic graph, such as cluster consensus, formation control or multiple leader election. Extensive numerical analysis emphasizes the effectiveness of the proposed solution with respect to the state of the art. © 2016 IEEE.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Article
A two-stage distributed architecture for voltage control in power distribution systems
Robbins, B. A.; Hadjicostis, Christoforos N.; Domínguez-Garcia, A. D. (2013)In this paper, we propose an architecture for voltage regulation in distribution networks that relies on controlling reactive power injections provided by distributed energy resources (DERs). A local controller on each bus ...
-
Article
A distributed generation control architecture for islanded ac microgrids
Cady, S. T.; Domínguez-Garcia, A. D.; Hadjicostis, Christoforos N. (2015)In this paper, we propose a distributed architecture for generation control in islanded ac microgrids with both synchronous generators and inverter-interfaced power supplies. Although they are smaller and have lower ratings, ...
-
Article
Outage probability under channel distribution uncertainty
Ioannou, I.; Charalambous, Charalambos D.; Loyka, S. (2012)Outage probability and capacity of a class of block-fading MIMO channels are considered under partial channel distribution information. Specifically, the channel or its distribution is not known but the latter is known to ...