NDLI: Computing transparently: the independent sets in a graph

Content Provider	Springer Nature Link
Author	Head, Tom
Copyright Year	2010
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.
Starting Page	129
Ending Page	138
Page Count	10
File Format	PDF
ISSN	15677818
Journal	Natural Computing
Volume Number	10
Issue Number	1
e-ISSN	15729796
Language	English
Publisher	Springer Netherlands
Publisher Date	2010-03-30
Publisher Place	Dordrecht
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Unconventional computing Photo-computing Light-based computing Optical computing Xerography Statistical Physics, Dynamical Systems and Complexity Theory of Computation Evolutionary Biology Artificial Intelligence (incl. Robotics) Processor Architectures
Content Type	Text
Resource Type	Article
Subject	Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Unconventional complexity measures for unconventional computers

Preface to the Special Issue Unconventional Computing 2008

Editorial for special issue on unconventional computation

Non-conventional computing paradigms

Editorial: Computing with biomolecules

Solving problems with natural computing

Computation in Sofic Quantum Dynamical Systems

Introduction ( Natural Computing , Volume 8 , Issue 3 )

Introduction ( Natural Computing , Volume 10 , Issue 4 )

Computing transparently: the independent sets in a graph

Similar Documents

Unconventional complexity measures for unconventional computers

Preface to the Special Issue Unconventional Computing 2008

Editorial for special issue on unconventional computation

Non-conventional computing paradigms

Editorial: Computing with biomolecules

Solving problems with natural computing

Computation in Sofic Quantum Dynamical Systems

Introduction ( Natural Computing , Volume 8 , Issue 3 )

Introduction ( Natural Computing , Volume 10 , Issue 4 )

Computing transparently: the independent sets in a graph