论文标题
冬季道路维护
Arc-routing for winter road maintenance
论文作者
论文摘要
众所周知，路由问题很难。我们在这里研究树木上的天然弧路由问题，更普遍地在有界的树宽度图上研究，令人惊讶地表明它可以在多项式时间内解决。这意味着平面图和少量维护汽车的次数算法，这是实际相关性的。
The arc-routing problems are known to be notoriously hard. We study here a natural arc-routing problem on trees and more generally on bounded tree-width graphs and surprisingly show that it can be solved in a polynomial time. This implies a sub-exponential algorithm for the planar graphs and small number of maintaining cars, which is of practical relevance.
