In this paper we prove that deciding whether a distributed system (represented as a coloured digraph with n nodes) has weak sense of direction is in AC^1 (using n^6 processors). Moreover, we show that deciding sense of direction is in P. Our algorithms can also be used to decide in AC^1 whether a coloured graph is a Cayley colour graph.
Complexity of deciding sense of direction / P. Boldi, S. Vigna. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 29:3(2000), pp. 779-789.
Titolo: | Complexity of deciding sense of direction |
Autori: | BOLDI, PAOLO (Primo) VIGNA, SEBASTIANO (Ultimo) |
Parole Chiave: | distributed systems ; computational complexity ; sense of direction ; Cayley graphs |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Data di pubblicazione: | 2000 |
Rivista: | |
Tipologia: | Article (author) |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1137/S0097539796310801 |
Appare nelle tipologie: | 01 - Articolo su periodico |
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.