.png){kind=icon}
返回
Predicting algorithmic complexity through structure analysis and compression
.png){kind=icon}
OA
AI
DOI：10.1016/j.asoc.2013.04.018.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The complexity of an algorithm is usually specified by the maximum number of steps made by the algorithm, as a function of the size of the input. However, as different inputs of equal size can yield dramatically different algorithm runtime, the size of the input is not always an appropriate basis for predicting algorithm runtime. In this paper, we argue that the compressed size of the input is more appropriate for this purpose. In particular, we devise a genetic algorithm for compressing a graph by finding the most compact description of its structure, and we demonstrate how the compressed size of the problem instance correlates with the runtime of an exact algorithm for two hard combinatorial problems (graph coloring and Boolean satisfiability). (C) 2013 Elsevier B. V. All rights reserved.
Keyword:
Algorithm complexity
Compression
Genetic algorithm
Graph coloring
#SAT
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6.6
论文数:
1.4W
被引数:
4.8W
机构
引用论文
.png){kind=icon}
分享收藏
没有更多内容
没有更多内容