The Clique Algorithm

Name: The Clique Algorithm
Rating: 5 (1 reviews)

Ashay Dharwadker

2006년 8월 · Institute of Mathematics

5.0

리뷰 1개

eBook

페이지

검증되지 않은 평점과 리뷰입니다. 자세히 알아보기

eBook 정보

We present a new polynomial-time algorithm for finding maximal cliques 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 clique 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 clique. The algorithm is demonstrated by finding maximum cliques for several famous graphs, including two large benchmark graphs with hidden maximum cliques. 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.