Improved Approximations for Tour and Tree Covers
Improved Approximations for Tour and Tree Covers
复制标题
改进了旅游和树木覆盖的近似值
DOI：
10.1007/s00453-003-1071-0
复制
发表时间：
2000
期刊：
影响因子：
1.1
通讯作者：
Amitabh Sinha
中科院分区：
文献类型：
--
作者：
J. Könemann;G. Konjevod;Ojas D. Parekh;Amitabh Sinha
边加权图的树（游）盖是一组边
AbstractA tree (tour) cover of an edge-weighted graph is a set of edges
which forms a tree (closed walk) and covers every other edge in the graph.
Arkin et al. give approximation
algorithms with ratios 3.55 (tree cover) and 5.5 (tour cover).
We present algorithms with a worst-case ratio of 3 for both problems.
加权边支配集问题推广的 2 1/10 近似算法
DOI：
10.1007/3-540-45253-2_13
发表时间：
2000
期刊：
ArXiv
影响因子：
--
作者：
R. Carr;Toshihiro Fujito;G. Konjevod;Ojas D. Parekh
通讯作者：
Ojas D. Parekh