TY - GEN

T1 - Approximating the minimum equivalent digraph

AU - Khuller, Samir

AU - Raghavachari, Balaji

AU - Young, Neal

PY - 1994

Y1 - 1994

N2 - The MEG (minimum equivalent graph) problem is the following: `Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes.' The MEG problem is NP-hard; this paper gives an approximation algorithm achieving a performance guarantee of about 1.64 in polynomial time. We give a modification that improves the performance guarantee to about 1.61. The algorithm achieves a performance guarantee of 1.75 in the time required for transitive closure. The heart of the MEG problem is the minimum SCSS (strongly connected spanning subgraph) problem - the MEG problem restricted to strongly connected digraphs. For the minimum SCSS problem, the paper gives a practical, nearly linear-time implementation achieving a performance guarantee of 1.75. The algorithm and its analysis are based on the simple idea of contracting long cycles. The analysis applies directly to 2-EXCHANGE, a general `local improvement' algorithm, showing that its performance guarantee is 1.75.

AB - The MEG (minimum equivalent graph) problem is the following: `Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes.' The MEG problem is NP-hard; this paper gives an approximation algorithm achieving a performance guarantee of about 1.64 in polynomial time. We give a modification that improves the performance guarantee to about 1.61. The algorithm achieves a performance guarantee of 1.75 in the time required for transitive closure. The heart of the MEG problem is the minimum SCSS (strongly connected spanning subgraph) problem - the MEG problem restricted to strongly connected digraphs. For the minimum SCSS problem, the paper gives a practical, nearly linear-time implementation achieving a performance guarantee of 1.75. The algorithm and its analysis are based on the simple idea of contracting long cycles. The analysis applies directly to 2-EXCHANGE, a general `local improvement' algorithm, showing that its performance guarantee is 1.75.

UR - http://www.scopus.com/inward/record.url?scp=0028251789&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028251789&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0028251789

SN - 0898713293

T3 - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

SP - 177

EP - 186

BT - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

PB - Publ by ACM

T2 - Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms

Y2 - 23 January 1994 through 25 January 1994

ER -