Name
Abstract | ||
|---|---|---|
ABSTRACT We consider unidirectional, strongly connected networks of identical finite - state automata, of bounded in - and out - degree but unknown topology and unbounded size n Protocols which are quadratic or linear in n are provided which accomplish the following tasks: wake - up and report when done; construct spanning trees out from the root and in to the root; conduct breadth - first and depth - first searches; send a message from the end - point of an (unidirectional) arc to its start - point; run a slow clock; and solve the firing squad synchronization problem Our protocols are highly parallel and use a new tech - nique - a special kind of moving data structures we call snakes |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1006/jagm.1996.0840 | J. Algorithms |
Keywords | Field | DocType |
com,finite state automata,depth first search,spanning tree,data structure | Combinatorics,Computer science,Firing squad synchronization problem,Breadth-first search,Automaton,Depth-first search,Algorithm,Theoretical computer science,Finite-state machine,Spanning tree,Strongly connected component,Bounded function | Journal |
Volume | Issue | ISSN |
24 | 1 | 0196-6774 |
ISBN | Citations | PageRank |
0-8186-2082-X | 19 | 1.78 |
References | Authors | |
6 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| shimon even | 1 | 2873 | 981.78 |
| Ami Litman | 2 | 240 | 49.78 |
| Peter Winkler | 3 | 583 | 85.60 |