...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>INFORMS journal on computing >Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem
【24h】

Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem

机译：Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相关主题

摘要

We describe and analyze test case generators for the maximum clique problem (or equivalent^ for the maximum independent set or vertex cover problems). The generators produce graphs with specified number of vertices and edges, and known max-imum clique size. The experimental hardness of the test cases is evaluated in relation to several heuristics for the maximum clique problem, based on neural networks, and derived from the work of A. Jagota. Our results show that the hardness of the graphs produced by this method depends in a crucial way on the construction parameters; for a given edge density, chal-lenging graphs can only be constructed using this method for a certain range of maximum clique values; the location of this range depends on the expected maximum clique size for ran-dom graphs of that density; the size of the range depends on the density of the graph. We also show that one of the algo-rithms, based on reinforcement learning techniques, has more success than the others at solving the test cases produced by the generators. In addition, NP-completeness reductions are presented showing that (in spite of what might be suggested by the results just mentioned) the maximum clique problem re-mains NP-hard even if the domain is restricted to graphs having a constant edge density and a constant ratio of the maximum clique size to the number of vertices, for almost all valid com-binations of such values. Moreover, the set of all graphs pro-duced by the generators, and having a constant ratio and edge density, is also NP-hard for almost all valid parameter combi-nations.

著录项

获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号