Approximating Transitive Reductions for Directed Networks

DOI10.1007/978-3-642-03367-4_7MaRDI QIDQ3183442zbMATH OpenOpenAlexFDO

Authors Piotr Berman, Bhaskar Dasgupta, 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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Inferring (biological) signal transduction networks via transitive reductions of directed graphs
• Approximating the Minimum Equivalent Digraph
• Approximation and hardness results for the maximum edges in transitive closure problem
• scientific article; zbMATH DE number 1003248
• On Making Directed Graphs Transitive

Cites work

• scientific article; zbMATH DE number 1305527 (Why is no real title available?)
• scientific article; zbMATH DE number 3316608 (Why is no real title available?)
• A simple derivation of edmonds' algorithm for optimum branchings
• An Algorithm for Finding a Minimum Equivalent Graph of a Digraph
• Approximating the Minimum Equivalent Digraph
• Approximating the minimum strongly connected subgraph via a matching lower bound
• Approximation Algorithms for Several Graph Augmentation Problems
• Inferring (biological) signal transduction networks via transitive reductions of directed graphs
• On strongly connected digraphs with bounded cycle length
• The Transitive Reduction of a Directed Graph

Cited in

(11)

• Finding strong components using depth-first search
• On best transitive approximations to simple graphs
• Fast exact algorithms for survivable network design with uniform requirements
• Directed capacity-preserving subgraphs: hardness and exact polynomial algorithms
• An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
• Minimum transactions problem
• Transitively reduced and transitively closed event networks
• Approximating the Minimum Equivalent Digraph
• Dual power assignment via second Hamiltonian cycle
• Inferring (biological) signal transduction networks via transitive reductions of directed graphs
• Minimal equivalent subgraphs containing a given set of arcs

Describes a project that uses

Uses Software

• NET-SYNTHESIS

This page was built for publication: Approximating Transitive Reductions for Directed Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3183442)