文件名称：在避免单色循环的同时为图形着色-研究论文
文件大小：717KB
文件格式：PDF
更新时间：2024-06-30 06:44:59
directed graph undirected
我们考虑决定一个给定的有向图是否可以被顶点分割成两个无环子图的问题。 这个问题的应用包括测试集体消费行为的合理性，这是微观经济学的一个主题。 我们证明该问题是 NP 完全的，即使对于有向图也是如此，并认为对于优化版本而言，常数因子近似算法的存在是不可能的，该版本最大化可以使用两种颜色着色的顶点数量，同时避免单色循环。 我们提出了三种精确算法，即基于循环识别的整数规划算法、回溯算法和分支检查算法。 我们在现实生活中的实例和随机生成的图上比较了这三种算法。 我们发现对于后一组图，每个算法都在几秒钟内解决了相当大的实例； 然而，整数规划算法的 CPU 时间随着图中顶点数的增加而增加，而其他两个过程的 CPU 时间则没有。 对于现实生活中的实例，整数规划算法在大约半小时内解决了最大的实例，而分支检查算法大约需要十分钟，回溯算法不到五分钟。 最后，对于每个算法，我们还根据经验研究了从高概率到低概率的 YES 答案的转变，作为弧数除以顶点数的函数。