SCIENCE@home

Approximating the minimum equivalent digraph

S. Khuller,B. Raghavachari,N. Young

Published 1994 in ACM-SIAM Symposium on Discrete Algorithms

ABSTRACT

Introduction 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. Connectivity is fundamental to the study of graphs and graph algorithms. Recently, many approxima- tion algorithms for finding subgraphs that meet given connectivity requirements have been devel- oped (l, 9, 11, 15, 16, 241. These results provide practical approximation algorithms for NP-hard network-design problems via an increased under- standing of connectivity properties.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-27 of 27 references · Page 1 of 1

CITED BY

Showing 1-96 of 96 citing papers · Page 1 of 1