Exact Algorithms for Maximum Clique: A Computational Study
We investigate a number of recently reported exact algorithms for the maximum clique problem. The program code is presented and analyzed to show how small changes in implementation can have a drastic effect on performance. The computational study demonstrates how problem features and hardware platfo...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2012-11-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/5/4/545 |
| _version_ | 1819137155487760384 |
|---|---|
| author | Patrick Prosser |
| author_facet | Patrick Prosser |
| author_sort | Patrick Prosser |
| collection | DOAJ |
| description | We investigate a number of recently reported exact algorithms for the maximum clique problem. The program code is presented and analyzed to show how small changes in implementation can have a drastic effect on performance. The computational study demonstrates how problem features and hardware platforms influence algorithm behaviour. The effect of vertex ordering is investigated. One of the algorithms (MCS) is broken into its constituent parts and we discover that one of these parts frequently degrades performance. It is shown that the standard procedure used for rescaling published results (i.e., adjusting run times based on the calibration of a standard program over a set of benchmarks) is unsafe and can lead to incorrect conclusions being drawn from empirical data. |
| first_indexed | 2024-12-22T10:46:23Z |
| format | Article |
| id | doaj.art-c63db3cf45b34c91910ee770af2af025 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-12-22T10:46:23Z |
| publishDate | 2012-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-c63db3cf45b34c91910ee770af2af0252022-12-21T18:28:55ZengMDPI AGAlgorithms1999-48932012-11-015454558710.3390/a5040545Exact Algorithms for Maximum Clique: A Computational StudyPatrick ProsserWe investigate a number of recently reported exact algorithms for the maximum clique problem. The program code is presented and analyzed to show how small changes in implementation can have a drastic effect on performance. The computational study demonstrates how problem features and hardware platforms influence algorithm behaviour. The effect of vertex ordering is investigated. One of the algorithms (MCS) is broken into its constituent parts and we discover that one of these parts frequently degrades performance. It is shown that the standard procedure used for rescaling published results (i.e., adjusting run times based on the calibration of a standard program over a set of benchmarks) is unsafe and can lead to incorrect conclusions being drawn from empirical data.http://www.mdpi.com/1999-4893/5/4/545maximum cliqueexact algorithmsempirical study |
| spellingShingle | Patrick Prosser Exact Algorithms for Maximum Clique: A Computational Study Algorithms maximum clique exact algorithms empirical study |
| title | Exact Algorithms for Maximum Clique: A Computational Study |
| title_full | Exact Algorithms for Maximum Clique: A Computational Study |
| title_fullStr | Exact Algorithms for Maximum Clique: A Computational Study |
| title_full_unstemmed | Exact Algorithms for Maximum Clique: A Computational Study |
| title_short | Exact Algorithms for Maximum Clique: A Computational Study |
| title_sort | exact algorithms for maximum clique a computational study |
| topic | maximum clique exact algorithms empirical study |
| url | http://www.mdpi.com/1999-4893/5/4/545 |
| work_keys_str_mv | AT patrickprosser exactalgorithmsformaximumcliqueacomputationalstudy |