Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2007 Copyright 2007 Universität Bonn, Institut für Informatik, Abt. V
85284

05.12.2007

Approximating Transitive Reductions for Directed Networks
Piotr Berman, Bhaskar DasGupta and Marek Karpinski
[Download PostScript] [Download PDF]

We consider minimum equivalent digraph (directed network) problem (also known as the strong transitive reduction), its maximumoptimization variant, and some extensions of those two types of problems. We prove the existence of polynomial time approximation algorithms with ratios1.5 for all the minimization problems and 2 for all the maximization problems. We establish also approximation hardness result for those problems to within aconstant even if the length of cycles is bounded by 5.

Last Change: 11/05/14 at 10:39:07
 English
Universität Bonn -> Institut für Informatik -> Abteilung V