neal young / Khuller95Approximating

  • publication/Khuller95Approximating.png The MEG (minimum equivalent graph) problem is, given a directed graph, to find a small subset of the edges that maintains all reachability relations between nodes. The problem is NP-hard. This paper gives an approximation algorithm with performance guarantee of pi2/6 ~ 1.64. The algorithm and its analysis are based on the simple idea of contracting long cycles.

    (This result was strengthened slightly in ``On strongly connected digraphs with bounded cycle length'' [1996].) The analysis applies directly to 2-Exchange, a simple local improvement algorithm, showing that its performance guarantee is 1.75. It was further improved by Berman et al, WADS 2009.)
    Journal version of [1994].

© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.