首页> 外文期刊>Journal of Logic and Algebraic Programming >Computing minimal extending sets by relation-algebraic modeling and development
【24h】

Computing minimal extending sets by relation-algebraic modeling and development

机译:通过关系代数建模和开发计算最小扩展集

获取原文
获取原文并翻译 | 示例

摘要

In 2009 F. Brandt introduced minimal extending sets as a new tournament solution. Until now no efficient algorithm is known for their computation and, in fact, the NP-hardness of the corresponding decision problem has been proved quite recently by F. Brandt, P. Harrenstein and H.G. Seedig in a working paper. We develop a relation-algebraic specification of minimal extending sets. It is algorithmic and can be directly translated into the programming language of the ROBDD-based computer algebra system RelView. By this general and model-oriented approach we obtain almost the same efficiency as the specifically tailored program for minimal extending sets mentioned in another recent working paper of F. Brandt, A. Dau and H.G. Seedig. We also discuss an alternative approach that is based on testing the extending set property with relation-algebraic means, and a greedy strategy. Under favorable conditions it allows to solve much larger problem instances than our first solution and that of F. Brandt, A. Dau and H.G. Seedig.
机译:在2009年,F。Brandt引入了最少的扩展套作为新的锦标赛解决方案。直到现在,还没有一种有效的算法可用于其计算,事实上,F。Brandt,P。Harrenstein和H.G. Seedig在工作论文中已经证明了相应决策问题的NP难度。我们开发了最小扩展集的关系代数规范。它是算法算法,可以直接转换为基于ROBDD的计算机代数系统RelView的编程语言。通过这种面向模型的通用方法,我们可以获得与F. Brandt,A。Dau和H.G. Seedig的另一篇最新工作论文中提到的针对最小扩展集的量身定制的程序几乎相同的效率。我们还将讨论一种替代方法,该方法基于使用关系代数方法和贪婪策略测试扩展集属性。在有利的条件下,它可以解决比我们的第一个解决方案以及F.Brandt,A.Dau和H.G.Seedig更大的问题实例。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号