Improved approximations for tour and tree covers

Improved approximations for tour and tree covers

0.00 Avg rating0 Votes
Article ID: iaor20053270
Country: Germany
Volume: 38
Issue: 3
Start Page Number: 441
End Page Number: 449
Publication Date: Dec 2003
Journal: Algorithmica
Authors: , , ,
Keywords: networks: path
Abstract:

A 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.

Reviews

Required fields are marked *. Your email address will not be published.