A Connectedness Game, c-Complexity of Graphs, and a Linear-Time Shelling Algorithm.
WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS
Pagination or Media Count:
When Z is a finite family of nonempty finite sets such that UZ an element of Z, there is an associated game DZ that can always be won by a certain player if he asks enough questions where a question is in effect a special sort of move in the game. The complexity of Z is defined as the minimum number of questions that suffices to win the game. As a specialization of this notion, there is associated with each connected graph G V,E a game that involves detecting the connectedness of a subgraph of G, and a number of questions required to win this game is called the c-complexity of G. It is shown that Gs c-complexity is OV when G is a path or circuit, and that plays a key role in the design of a linear-time shelling algorithm.
- Operations Research
- Computer Programming and Software