Approximation algorithms for covering a graph by vertex‐disjoint paths of maximum total weight | Zendy

Moran Shlomo | Zendy; Newman Ilan | Zendy; Wolfstahl Yaron | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Approximation algorithms for covering a graph by vertex‐disjoint paths of maximum total weight

Author(s) -

Moran Shlomo,

Newman Ilan,

Wolfstahl Yaron

Publication year - 1990

Publication title -

networks

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.977

H-Index - 64

eISSN - 1097-0037

pISSN - 0028-3045

DOI - 10.1002/net.3230200106

Subject(s) - bipartite graph , algorithm , mathematics , disjoint sets , combinatorics , approximation algorithm , vertex (graph theory) , time complexity , hopcroft–karp algorithm , matching (statistics) , subroutine , floyd–warshall algorithm , vertex cover , discrete mathematics , computer science , graph , shortest path problem , line graph , pathwidth , statistics , operating system , k shortest path routing

We consider the problem of covering a weighted graph G = (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 is O (| 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 of the algorithm.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research