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):

Report Date:

1975-10-01

Pagination or Media Count:

36.0

Abstract:

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.

Subject Categories:

  • Operations Research
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE