Approximating Transitive Reductions for Directed Networks
From MaRDI portal
Publication:3183442
DOI10.1007/978-3-642-03367-4_7zbMath1253.68354MaRDI QIDQ3183442
Marek Karpinski, Piotr Berman, Bhaskar Das Gupta
Publication date: 20 October 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03367-4_7
68R10: Graph theory (including graph drawing) in computer science
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Inferring (biological) signal transduction networks via transitive reductions of directed graphs
- On strongly connected digraphs with bounded cycle length
- Approximation Algorithms for Several Graph Augmentation Problems
- Approximating the Minimum Equivalent Digraph
- An Algorithm for Finding a Minimum Equivalent Graph of a Digraph
- A simple derivation of edmonds' algorithm for optimum branchings
- The Transitive Reduction of a Directed Graph