首页> 外文会议>Algorithmic aspects in information and management >Exact Algorithms for Coloring Graphs While Avoiding Monochromatic Cycles
【24h】

Exact Algorithms for Coloring Graphs While Avoiding Monochromatic Cycles

机译:避免单色循环的同时为图形着色的精确算法

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

摘要

We consider the problem of deciding whether a given directed graph can be vertex partitioned into two acyclic subgraphs. Applications of this problem include testing rationality of collective consumption behavior, a subject in micro-economics. We identify classes of directed graphs for which the problem is easy and prove that the existence of a constant factor approximation algorithm is unlikely for an optimization version which maximizes the number of vertices that can be colored using two colors while avoiding monochromatic cycles. We present three exact algorithms, namely an integer-programming algorithm based on cycle identification, a backtracking algorithm, and a branch-and-check algorithm. We compare these three algorithms both on real-life instances and on randomly generated graphs. We find that for the latter set of graphs, every algorithm solves instances of considerable size within few seconds; however, the CPU time of the integer-programming algorithm increases with the number of vertices in the graph while that of the two other procedures does not. For every algorithm, we also study empirically the transition from a high to a low probability of YES answer as function of a parameter of the problem. For real-life instances, the integer-programming algorithm fails to solve the largest instance after one hour while the other two algorithms solve it in about ten minutes.
机译:我们考虑确定一个给定的有向图是否可以在顶点上划分为两个非循环子图的问题。这个问题的应用包括检验集体消费行为的合理性,这是微观经济学的一个主题。我们确定问题容易解决的有向图类别,并证明对于优化版本而言,常量因子近似算法的存在不太可能,该优化版本可最大化使用两种颜色着色的顶点数量,同时避免单色循环。我们提出了三种精确的算法,即基于循环识别的整数编程算法,回溯算法和分支检查算法。我们在实际实例和随机生成的图上都比较了这三种算法。我们发现,对于后一组图形,每种算法都可以在几秒钟内解决尺寸相当大的实例。但是,整数编程算法的CPU时间随着图中顶点数的增加而增加,而其他两个过程的CPU时间则没有。对于每种算法,我们还根据问题的参数经验性地研究从“是”答案的高概率到低概率的过渡。对于现实生活中的实例,整数编程算法无法在一小时后求解最大实例,而其他两种算法则需要约十分钟才能求解完。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号