caa a22 4500 44584275X CHVBK 20180317145350.0 cr unu---uuuuu 170323e20110301xx s 000 0 eng 10.1007/s11047-010-9186-0 doi (NATIONALLICENCE)springer-10.1007/s11047-010-9186-0 Head Tom Mathematical Sciences, Binghamton University, 13902-6000, Binghamton, NY, USA aut Computing transparently: the independent sets in a graph [Elektronische Daten] [Tom Head] 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. Springer Science+Business Media B.V., 2010 Unconventional computing nationallicence Photo-computing nationallicence Light-based computing nationallicence Optical computing nationallicence Xerography nationallicence Natural Computing Springer Netherlands 10/1(2011-03-01), 129-138 1567-7818 10:1<129 2011 10 11047 https://doi.org/10.1007/s11047-010-9186-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11047-010-9186-0 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Head Tom Mathematical Sciences, Binghamton University, 13902-6000, Binghamton, NY, USA aut NATIONALLICENCE 773 0- Natural Computing Springer Netherlands 10/1(2011-03-01), 129-138 1567-7818 10:1<129 2011 10 11047 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer