English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper revisits two classical distributed problems in anonymous networks,namely spanning tree construction and topology recognition, from the point ofview of graph covering theory. For both problems, we characterize necessary andsufficient conditions on the communication graph in terms of directed symmetriccoverings. These characterizations answer along-standing open question posed byYamashita and Kameda [YK96], and shed new light on the connection betweencoverings and the concepts of views and quotient graphs developed by the sameauthors. Characterizing conditions in terms of coverings is significant becauseit connects the field with a vast body of classical literature in graph theoryand algebraic topology. In particular, it gives access to powerful tools suchas Reidemeister's theorem and Mazurkiewicz's algorithm. Combined together,these tools allow us to present elegant proofs of otherwise intricate results,and their constructive nature makes them effectively usable in the algorithms.This paper also gives us the opportunity to present the field of coveringtheory in a pedagogical way, with a focus on the two aforementioned tools,whose potential impact goes beyond the specific problems considered in thiswork.

Revisiting the Role of Coverings in Anonymous Networks: Spanning Tree Construction and Topology Recognition