ECCC-Report TR07-119https://eccc.weizmann.ac.il/report/2007/119Comments and Revisions published for TR07-119en-usWed, 05 Dec 2007 12:45:47 +0200
Paper TR07-119
| Approximating Transitive Reductions for Directed Networks |
Piotr Berman,
Bhaskar DasGupta,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2007/119We consider <i>minimum equivalent digraph</i> (<i>directed network</i>) problem (also known as the <i>strong transitive reduction</i>), its maximum optimization variant, and some extensions of those two types of problems. We prove the existence of polynomial time approximation algorithms with ratios 1.5 for all the minimization problems and 2 for all the maximization problems. We establish also approximation hardness result for those problems to within a constant even if the length of cycles is bounded by 5.
Wed, 05 Dec 2007 12:45:47 +0200https://eccc.weizmann.ac.il/report/2007/119