Approximating Transitive Reductions for Directed Networks
From MaRDI portal
Publication:3183442
DOI10.1007/978-3-642-03367-4_7zbMath1253.68354MaRDI QIDQ3183442
Piotr Berman, Bhaskar Das Gupta, Marek Karpinski
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
Fast exact algorithms for survivable network design with uniform requirements, Dual power assignment via second Hamiltonian cycle, An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
Uses Software
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item