Name
Abstract | ||
|---|---|---|
Abstract. The minimum equivalent graph (MEG) problem is as follows: given a directed graph, find a smallest subset,of the,edges,that,maintains,all,teachability,relations,between,nodes.,This problem,is NP-hard; this paper,gives an approximation,algorithm achieving a performance,guarantee of about 1.64 in polynomial time. 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,strongly,connected,spanning subgraph,(SCSS) 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-EXCHANCE, a general "local improvement" algorithm, showing that its performance guarantee is 1.75. Key , graph, approximation algorithm, strong connectivity, local improvement AMS subject classifications. 68R10, 90C27, 90C35, 05C85, 68Q20 |
Year | DOI | Venue |
|---|---|---|
2002 | 10.5555/314464.314492 | SODA94: Conference on Discrete Algorithms
Arlington
Virginia
USA
January, 1994 |
Keywords | Field | DocType |
transitive closure,graph connectivity,np hard problem,approximation algorithm,directed graph,graph theory,polynomial time,implementation,approximation | Approximation algorithm,Discrete mathematics,Combinatorics,Computer science,Computational geometry,Directed graph,Reachability,Assignment problem,Transitive closure,Time complexity,Digraph | Journal |
Volume | Issue | ISSN |
cs.DS/0205040 | 4 | SIAM J. Computing 24(4):859-872 (1995) |
ISBN | Citations | PageRank |
978-0-89871-329-9 | 29 | 1.80 |
References | Authors | |
17 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samir Khuller | 1 | 4053 | 368.49 |
| Balaji Raghavachari | 2 | 1001 | 77.77 |
| Neal E. Young | 3 | 128 | 10.10 |