Approximation algorithms for covering a graph by vertex‐disjoint paths of maximum total weight
作者:
Shlomo Moran,
Ilan Newman,
Yaron Wolfstahl,
期刊:
Networks
(WILEY Available online 1990)
卷期:
Volume 20,
issue 1
页码: 55-64
ISSN:0028-3045
年代: 1990
DOI:10.1002/net.3230200106
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractWe consider the problem of covering a weighted graphG = (V, E) by a set of vertex‐disjoint paths, such that the total weight of these paths is maximized. This problem is clearly NP‐complete, since it contains the Hamiltonian path problem as a special case. Three approximation algorithms for this problem are presented, exhibiting a complexity‐performance trade‐off. First, we develop an algorithm for covering undirected graphs. The time complexity of this algorithm isO(|E|log|E|), and its performance‐ratio is ½. Second, we present an algorithm for covering undirected graphs, whose performance‐ratio is ⅔. This algorithm uses a maximum weight matching algorithm as a subroutine, which dominates the overall complexity of our algorithm. Finally, we develop an algorithm for covering directed graphs, whose performanceratio is ⅔. This algorithm uses a maximum weight bipartite matching algorithm as a subroutine, which dominates the overall complexity
点击下载:
PDF
(464KB)
返 回