论文标题
最大欧拉循环分解问题的算法
Algorithms for the Maximum Eulerian Cycle Decomposition Problem
论文作者
论文摘要
给定一个欧拉图G，在最大的欧拉循环分解问题中，我们有兴趣找到g中的边缘 - 偶数周期{e_1，e_1，e_2，...，e_k}的集合，使得G的所有边缘恰好在一个循环中，并且k在一个周期中，k是最大的。我们提出了一种算法，以解决由Lancia和Serafini（2016）引入的列生成整数线性编程（ILP）模型的定价问题。此外，我们提出了一种贪婪的启发式，它可以从随机顶点开始搜索最小尺寸周期，以及基于部分求解ILP模型的启发式。我们使用不同的Eulerian图组进行了比较解决方案和执行时间质量的三种方法的测试，每个方法都将每个设置的分组图组与不同数量的顶点和边缘进行分组。我们的实验结果表明，基于ILP的启发式的表现优于其他方法。
Given an Eulerian graph G, in the Maximum Eulerian Cycle Decomposition problem, we are interested in finding a collection of edge-disjoint cycles {E_1, E_2, ..., E_k} in G such that all edges of G are in exactly one cycle and k is maximum. We present an algorithm to solve the pricing problem of a column generation Integer Linear Programming (ILP) model introduced by Lancia and Serafini (2016). Furthermore, we propose a greedy heuristic, which searches for minimum size cycles starting from a random vertex, and a heuristic based on partially solving the ILP model. We performed tests comparing the three approaches in relation to the quality of solutions and execution time, using distinct sets of Eulerian graphs, each set grouping graphs with different numbers of vertices and edges. Our experimental results show that the ILP based heuristic outperforms the other methods.
