Carnegie Mellon University
Browse

Min-Max Tree Covers of Graphs

Download (219.89 kB)
journal contribution
posted on 1986-05-01, 00:00 authored by G. Even, N. Garg, J. Könemann, Ramamoorthi RaviRamamoorthi Ravi, A. Sinha
We provide constant factor approximation algorithms for covering the nodes of a graph using trees (rooted or unrooted), under the objective function of minimizing the weight of the maximum weight tree, subject to an upper bound on the number of trees used. These problems are related to location routing and traveling salesperson problems.

History

Date

1986-05-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC