Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021
Inspired by recent algorithms for electing a leader in a distributed system, we study the following game in a directed graph: each vertex selects one of its outgoing arcs (if any) and eliminates the other endpoint of this arc; the remaining vertices play on until no arcs remain. We call a directed graph lethal if the game must end with all vertices eliminated and mortal if it is possible that the game ends with all vertices eliminated. We show that lethal graphs are precisely collections of vertex-disjoint cycles, and that the problem of deciding whether or not a given directed graph is mortal is NP-complete (and hence it is likely that no "nice" characterization of mortal graphs exists). © 2001 Elsevier Science B.V. All rights reserved.
Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021
S. Sattanathan, N.C. Narendra, et al.
CONTEXT 2005
Victor Valls, Panagiotis Promponas, et al.
IEEE Communications Magazine
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009