The Independent Set Algorithm (Paperback)

We present a new polynomial-time algorithm for finding maximal independent sets in graphs. As a corollary, we obtain new bounds on the famous Ramsey numbers in terms of the maximum and minimum vertex degrees of the corresponding Ramsey graphs. The algorithm finds a maximum independent set in all known examples of graphs. In view of the importance of the P versus NP question, we ask if there exists a graph for which the algorithm cannot find a maximum independent set. The algorithm is demonstrated by finding maximum independent sets for several famous graphs, including two large benchmark graphs with hidden maximum independent sets. We implement the algorithm in C++ and provide a demonstration program for Microsoft Windows.

General

Imprint:	Createspace Independent Publishing Platform
Country of origin:	United States
Release date:	October 2011
First published:	October 2011
Authors:	Ashay Dharwadker
Dimensions:	279 x 216 x 3mm (L x W x T)
Format:	Paperback - Trade
Pages:	46
ISBN-13:	978-1-4663-8769-0
Categories:	Books > Computing & IT > General theory of computing > General Books > Computing & IT > Applications of computing > General Promotions
LSN:	1-4663-8769-6
Barcode:	9781466387690

Is the information for this product incomplete, wrong or inappropriate? Let us know about it.

Does this product have an incorrect or missing image? Send us a new image.

Is this product missing categories? Add more categories.

Review This Product

No reviews yet - be the first to create one!