A Connectedness Game, c-Complexity of Graphs, and a Linear-Time Shelling Algorithm.
Abstract
When Z is a finite family of nonempty finite sets such that UZ an element of Z, there is an associated game D(Z) 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 G's c-complexity is O(/V/) when G is a path or circuit, and that plays a key role in the design of a linear-time shelling algorithm.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1975
- Accession Number
- ADA018424
Entities
People
- Gopal Danaraj
- Victor Klee
Organizations
- University of Washington