Maintaining Directed Reachability with Few Edges
| dc.contributor.author | Khuller, Samir | en_US |
| dc.contributor.author | Raghavachari, Balaji | en_US |
| dc.contributor.author | Young, Neal | en_US |
| dc.date.accessioned | 2004-05-31T22:24:04Z | |
| dc.date.available | 2004-05-31T22:24:04Z | |
| dc.date.created | 1993-09 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.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.'' 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 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. (Also cross-referenced as UMIACS-TR-93-87) | en_US |
| dc.format.extent | 319891 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/598 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3134 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-93-87 | en_US |
| dc.title | Maintaining Directed Reachability with Few Edges | en_US |
| dc.type | Technical Report | en_US |