Accession Number : ADA018424

Title :   A Connectedness Game, c-Complexity of Graphs, and a Linear-Time Shelling Algorithm.

Descriptive Note : Technical rept.,

Corporate Author : WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS

Personal Author(s) : Klee,Victor ; Danaraj,Gopal

Report Date : OCT 1975

Pagination or Media Count : 36

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.

Descriptors :   *Game theory, *Computer programming, Decision theory, Set theory, Strategy, Theorems

Subject Categories : Operations Research
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE