Computing transparently: the independent sets in a graph |
| |
Authors: | Tom Head |
| |
Affiliation: | (1) Mathematical Sciences, Binghamton University, Binghamton, NY 13902-6000, USA |
| |
Abstract: | A procedure is given for finding the independent sets in an undirected graph by xeroxing onto transparent plastic sheets.
Let an undirected graph having n vertices and m edges be given. A list of all the independent subsets of the set of vertices of the graph is constructed by using a xerox machine in a manner that requires
the formation of only n + m + 1 successive transparencies. An accompanying list of the counts of the elements in each independent set is then constructed
using only O(n
2) additional transparencies. The list with counts provides a list of all maximum independent sets. This gives an O(n
2) step solution for the classical problem of finding the cardinality of a maximal independent set in a graph. The applicability
of these procedures is limited, of course, by the increase in the information density on the transparencies when n is large. Our ultimate purpose here is to give hand tested ‘ultra parallel’ algorithmic procedures that may prove suitable for realization
using future optical technologies. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|