**Problem of the Week**

**BUGCAT**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

**BingAWM**

**Math Club**

You are here: Homepage » Seminars - Academic year 2023-24 » Combinatorics Seminar » Tom Head (Binghamton)

seminars:comb:abstract.200910hea

I give a procedure 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.

My ultimate purpose here is to give hand tested 'ultra parallel' algorithmic procedures that may prove suitable for realization using future optical technologies.

seminars/comb/abstract.200910hea.txt · Last modified: 2020/01/29 14:03 (external edit)