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