Approximating the minimum equivalent digraph

Samir Khuller*, Balaji Raghavachari, Neal Young

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
PublisherPubl by ACM
Pages177-186
Number of pages10
ISBN (Print)0898713293
StatePublished - 1994
EventProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms - Arlington, VA, USA
Duration: Jan 23 1994Jan 25 1994

Publication series

NameProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

Other

OtherProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms
CityArlington, VA, USA
Period1/23/941/25/94

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Approximating the minimum equivalent digraph'. Together they form a unique fingerprint.

Cite this