Abstract
This paper investigates the power of local computations on graphs, by considering a classical problem in distributed algorithms, the recognition problem. Formally, we want to compute some topological information on a network of processes, possibly using additional knowledge about the structure of the underlying graph. We propose the notion of recognition with structural knowledge by means of local computations. Then we characterize the graph classes that are recognizable with or without structural knowledge. The characterizations use graph coverings and a distributed enumeration algorithm proposed by A. Mazurkiewicz. Several applications are presented, in particular concerning minor-closed classes of graphs.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Godard, E., Métivier, Y. & Muscholl, A. Characterizations of Classes of Graphs Recognizable by Local Computations. Theory Comput Systems 37, 249–293 (2004). https://doi.org/10.1007/s00224-003-1062-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-003-1062-1