Approximate maximum weight branchings

Amitabha Bagchi, Ankur Bhargava, Torsten Suel

    Research output: Contribution to journalArticle

    Abstract

    We consider a special subgraph of a weighted directed graph: one comprising only the k heaviest edges incoming to each vertex. We show that the maximum weight branching in this subgraph closely approximates the maximum weight branching in the original graph. Specifically, it is within a factor of k / ( k + 1 ). Our interest in finding branchings in this subgraph is motivated by a data compression application in which calculating edge weights is expensive but estimating which are the heaviest k incoming edges is easy. An additional benefit is that since algorithms for finding branchings run in time linear in the number of edges our results imply faster algorithms although we sacrifice optimality by a small factor. We also extend our results to the case of edge-disjoint branchings of maximum weight and to maximum weight spanning forests.

    Original languageEnglish (US)
    Pages (from-to)54-58
    Number of pages5
    JournalInformation Processing Letters
    Volume99
    Issue number2
    DOIs
    StatePublished - Jul 31 2006

    Keywords

    • Analysis of algorithms
    • Graph algorithms

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Signal Processing
    • Information Systems
    • Computer Science Applications

    Fingerprint Dive into the research topics of 'Approximate maximum weight branchings'. Together they form a unique fingerprint.

  • Cite this