The Independent Set Algorithm
2006年8月 · Institute of Mathematics
5.0star
1 則評論report
電子書
50
頁
report評分和評論未經驗證 瞭解詳情
關於本電子書
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.
評分和評論
5.0
1 則評論
關於作者
Ashay Dharwadker is the Distinguished Professor of Mathematics & Natural Sciences at the Institute of Mathematics, Gurgaon, India. He is the author of a dozen exquisitely illustrated books describing his fundamental contributions to combinatorics, graph theory, computer science and the foundations of physics.
為這本電子書評分
歡迎提供意見。
閱讀資訊
智慧型手機與平板電腦
筆記型電腦和電腦
你可以使用電腦的網路瀏覽器聆聽你在 Google Play 購買的有聲書。
電子書閱讀器與其他裝置
如要在 Kobo 電子閱讀器這類電子書裝置上閱覽書籍，必須將檔案下載並傳輸到該裝置上。請按照說明中心的詳細操作說明，將檔案傳輸到支援的電子閱讀器上。
