Rural postman parameterized by the number of components of required edges
Rural postman parameterized by the number of components of required edges
复制标题
农村邮递员通过所需边的分量数量进行参数化
DOI：
10.1016/j.jcss.2016.06.001
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Anders Yeo
中科院分区：
文献类型：
--
作者：
G. Gutin;Magnus Wahlström;Anders Yeo
在有向乡村邮递员问题（DRPP）中，给定一个强连通有向多重图D=（V，A），其弧上具有非负整数权，所需弧的子集R和一个非负整数R，判定D是否有一个闭有向游动包含R的每一条弧，且权至多为R。设k是R诱导的D的子图中弱连通分支的个数。索尔热等人[30]问DRPP是否是固定参数易处理（FPT）时，参数为k，即是否有一个算法的运行时间O（f（k）），其中f是一个函数的k只和O符号抑制多项式的因素。利用代数方法证明了当DRPP的运行时间为O ∞（2k）时，DRPP的运行时间为O ∞（2k）.同样的结果也适用于DRPP的无向版本。
Abstract In the Directed Rural Postman Problem (DRPP), given a strongly connected directed multigraph D=(V, A) with nonnegative integral weights on the arcs, a subset R of required arcs and a nonnegative integer ℓ, decide whether D has a closed directed walk containing every arc of R and of weight at most ℓ. Let k be the number of weakly connected components in the subgraph of D induced by R. Sorge et al.[30] asked whether the DRPP is fixed-parameter tractable (FPT) when parameterized by k, ie, whether there is an algorithm of running time O⁎(f (k)) where f is a function of k only and the O⁎ notation suppresses polynomial factors. Using an algebraic approach, we prove that DRPP has a randomized algorithm of running time O⁎(2 k) when ℓ is bounded by a polynomial in the number of vertices in D. The same result holds for the undirected version of DRPP.
欧拉扩展及其在无等待流水作业调度中的应用
影响因子：
2
作者：
W. Höhn;T. Jacobs;N. Megow.
通讯作者：
N. Megow.