期刊论文详细信息
Algorithms
Exact Algorithms for Maximum Clique: A Computational Study
关键词: maximum clique;    exact algorithms;    empirical study;   
DOI  :  10.3390/a5040545
来源: mdpi
PDF
【 摘 要 】

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.

【 授权许可】

CC BY   
© 2012 by the authors; licensee MDPI, Basel, Switzerland.

【 预 览 】
附件列表
Files Size Format View
RO202003190040572ZK.pdf 1431KB PDF download
  文献评价指标  
  下载次数:30次 浏览次数:19次