Distributed cycle detection and removal
Hadjicostis, Christoforos N.
SourceIEEE Transactions on Control of Network Systems
Google Scholar check
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
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 ...
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, ...
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 ...