Approximating the Minimum Equivalent Digraph

Details Approximating the Minimum Equivalent Digraph Approximating the Minimum Equivalent Digraph

2002-05-18

arxiv.org/abs/cs/0205040v1

SIAM J. Computing 24(4):859-872 (1995)

Computer Science

Data Structures and Algorithms

conference version in ACM-SIAM Symposium on Discrete Algorithms (1994)

Scientific paper

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 pi^2/6 ~ 1.64. The algorithm and its analysis are based on the simple idea of contracting long cycles. (This result is 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.

Affiliated with

Also associated with

No associations

Rating

Approximating the Minimum Equivalent Digraph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximating the Minimum Equivalent Digraph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating the Minimum Equivalent Digraph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-599156