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.

Complexity of deciding sense of direction

P. Boldi
Primo
;
S. Vigna
Ultimo
2000

Abstract

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.
distributed systems ; computational complexity ; sense of direction ; Cayley graphs
Settore INF/01 - Informatica
2000
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/154158
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 11
social impact