IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.
AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.
EnglishIn 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:
http://hdl.handle.net/2434/154158
Copyright © 2021