A Noise Reduction Algorithm for the maximum clique problem /
This research work implemented a Noise Reduction ographics.
| Main Author: | |
|---|---|
| Format: | Thesis Book |
| Language: | English |
| Published: |
[Place of publication not identified] :
[publisher not identified] ;
1998.
|
| Subjects: |
| Summary: | This research work implemented a Noise Reduction ographics. Algorithm to find the maximum clique in an arbitrary undirected and unweighted graph. The algorithm will first pick 1 vertices that form a pivot clique, which induces a sub-graph containing all vertices that have edges to all i vertices in the pivot clique. Then a greedy algorithm will pick a vertex of largest degree to join the pivot clique and delete all vertices that are not adjacent to the one just picked. The greedy algorithm is executed repeatedly until the sub-graph is exhausted. The implementation was tested against benchmark graphs from the second DIMACS challenge in 1993. The results indicate that the algorithm did quite well on all graphs, especially Brockington graphs that are considered difficult in general. Due to the complexity of the algorithm, [], i = (1, 2, 3,. . ., n) , where n is the number of vertices in the graph, we were unable to test some graphs with large number of vertices n > 800) with i > 1, the better setting for our algorithm. |
|---|---|
| Item Description: | Vita. "Major subject: Computer Science". |
| Physical Description: | viii, 46 leaves : illustrations ; 28 cm. |
| Bibliography: | Includes bibliographical references (leaves 33-38). |