Show simple item record

dc.contributor.authorOliva, Gabrieleen
dc.contributor.authorSetola, Robertoen
dc.contributor.authorGlielmo, Luigien
dc.contributor.authorHadjicostis, Christoforos N.en
dc.creatorOliva, Gabrieleen
dc.creatorSetola, Robertoen
dc.creatorGlielmo, Luigien
dc.creatorHadjicostis, Christoforos N.en
dc.description.abstractIn this paper, we provide distributed algorithms to detect and remove cycles in a directed relational graph by exploiting the underlying undirected communication graphen
dc.description.abstractthe 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-Harden
dc.description.abstractfor 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.en
dc.sourceIEEE Transactions on Control of Network Systemsen
dc.titleDistributed Cycle Detection and Removalen
dc.description.endingpage204Πολυτεχνική Σχολή / Faculty of EngineeringΤμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών / Department of Electrical and Computer Engineering
dc.contributor.orcidHadjicostis, Christoforos N. [0000-0002-1706-708X]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record