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. BoldiPrimo
;S. VignaUltimo
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.
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.
