Approximating the Minimum Equivalent Digraph
From MaRDI portal
Publication:4852628
DOI10.1137/S0097539793256685zbMath0830.68100OpenAlexW2952664587MaRDI QIDQ4852628
Samir Khuller, Balaji Raghavachari, Neal E. Young
Publication date: 1 November 1995
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539793256685
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (21)
Approximating Transitive Reductions for Directed Networks ⋮ Redundancy in logic. II: 2CNF and Horn propositional formulae ⋮ An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph ⋮ On strongly connected digraphs with bounded cycle length ⋮ Sparse certificates for 2-connectivity in directed graphs ⋮ Minimum equivalent precedence relation systems ⋮ Semicomplete compositions of digraphs ⋮ Dual power assignment via second Hamiltonian cycle ⋮ Every strong digraph has a spanning strong subgraph with at most \(n+2\alpha-2\) arcs ⋮ Capacity-preserving subgraphs of directed flow networks ⋮ An improved algorithm for finding maximum outerplanar subgraphs ⋮ Inferring (biological) signal transduction networks via transitive reductions of directed graphs ⋮ Directed hypergraphs: introduction and fundamental algorithms -- a survey ⋮ Approximating the smallest k -edge connected spanning subgraph by LP-rounding ⋮ Dual-based approximation algorithms for cut-based network connectivity problems ⋮ Approximating the smallest 2-vertex connected spanning subgraph of a directed graph ⋮ 1.61-approximation for min-power strong connectivity with two power levels ⋮ The minimum spanning strong subdigraph problem is fixed parameter tractable ⋮ A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem ⋮ Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs ⋮ Strongly Connected Spanning Subgraph for Almost Symmetric Networks
This page was built for publication: Approximating the Minimum Equivalent Digraph
