On Strongly Connected Digraphs with Bounded Cycle Length

Abstract Given a directed graph G = ( V , E ), a natural problem is to choose a minimum number of the edges in E such that, for any two vertices u and v , if there is a path from u to v in E , then there is a path from u to v among the chosen edges. We show that in graphs having no directed cycle with more than three edges, this problem is equivalent to Maximum Bipartite Matching. This leads to a small improvement in the performance guarantee of the previous best approximation algorithm for the general problem.

• Publication year

  1996

• Venue

  Discrete Applied Mathematics

• Publication date

  1996-08-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0166-218X(95)00105-ZarXiv cs/0205011
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximating the minimum equivalent digraph

  1994cited by this paper
• Easy Problems for Tree-Decomposable Graphs

  1991cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• Computers and Intractability: A Guide to the Theory of NP-Completeness

  1979cited by this paper
• An Algorithm for Finding a Minimal Equivalent Graph of a Digraph

  1975cited by this paper
• The Transitive Reduction of a Directed Graph

  1972cited by this paper
• A n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs

  1971cited by this paper
• An Algorithm for Finding a Minimum Equivalent Graph of a Digraph

  1969cited by this paper
• An algorithm for a minimum cover of a graph

  1959cited by this paper

• Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs

  2024cites this paper
• A characterization of positive spanning sets with ties to strongly connected digraphs

  2024cites this paper
• On the Complexity of Minimum-Cost Networked Estimation of Self-Damped Dynamical Systems

  2019cites this paper
• Range assignment with k-power levels in a Wireless Sensor Network

  2018cites this paper
• Approximating minimum representations of key Horn functions

  2018cites this paper
• Minimal representation of elementary Horn functions

  2018cites this paper
• Strongly Connected Spanning Subgraph for Almost Symmetric Networks

  2017cites this paper
• Cellular Interaction Networks

  2016cites this paper
• Dual-Based Approximation Algorithms for Cut-Based Network Connectivity Problems

  2015cites this paper
• Efficient Evaluation of Query for XML Graph Based on Single Source Shortest Path

  2015cites this paper
• Dual-Fitting Approximation Algorithms for Network Connectivity Problems

  2015cites this paper
• DAG‐Width and Circumference of Digraphs

  2015cites this paper
• Dual power assignment via second Hamiltonian cycle

  2014influential citation
• 1.61-approximation for min-power strong connectivity with two power levels

  2014influential citation
• Algorithmic Perspectives of Network Transitive Reduction Problems and their Applications to Synthesis and Analysis of Biological Networks

  2013cites this paper
• A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem

  2012cites this paper
• A New Computationally Efficient Measure of Topological Redundancy of Biological and Social Networks

  2011influential citation
• Inference of signal transduction networks from double causal evidence.

  2010cites this paper
• Min-Power Strong Connectivity

  2010influential citation
• Approximating Transitive Reductions for Directed Networks

  2009influential citation
• Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs

  2008influential citation
• Approximating Transitivity in Directed Networks

  2008cites this paper
• The minimum spanning strong subdigraph problem is fixed parameter tractable

  2008cites this paper
• A Novel Method for Signal Transduction Network Inference from Indirect Experimental Evidence

  2007influential citation
• Online Algorithms To Maintain A Transitive Reduction CS 294-8 Class Project , Fall 2006

  2006cites this paper
• INFERRING THE STRUCTURE OF SIGNAL TRANSDUCTION NETWORKS FROM INTERACTIONS BETWEEN CELLULAR COMPONENTS AND INFERRING HAPLOTYPES FROM INFORMATIVE SNPS by KELLY WESTBROOKS Under the Direction of

  2006cites this paper
• Inferring the Structure of Signal Transduction Networks from Interactions between Cellular Components and Inferring Haplotypes from Informative SNPS

  2006cites this paper
• Redundancy in logic II: 2CNF and Horn propositional formulae

  2005cites this paper
• Algorithms and complexity analyses for some combinatorial optimization problems

  2005cites this paper
• Special edges, and approximating the smallest directed k-edge connected spanning subgraph

  2004cites this paper
• Spanning k‐arc‐strong subdigraphs with few arcs in k‐arc‐strong tournaments

  2004cites this paper
• New regular embeddings of n-cubes Q n

  2004influential citation
• A linear time 5/3-approximation for the minimum strongly-connected spanning subgraph problem

  2003cites this paper
• Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs

  2003cites this paper
• Studying Graph Connectivity

  2002cites this paper
• Digraphs - theory, algorithms and applications

  2002cites this paper
• The Minimum Spanning Strong Subdigraph Problem for Extended Semicomplete Digraphs and Semicomplete Bipartite Digraphs

  2001cites this paper
• Finding small k-arc-strong Spanning Subdigraphs in k-arc-strong Tournaments

  2000cites this paper
• Strongly connected spanning subgraphs with the minimum number of arcs in semicomplete multipartite digraphs

  1999cites this paper
• Complexity and Approximation

  1999cites this paper
• Approximation algorithms for finding highly connected subgraphs

  1996cites this paper
• Approximating minimum-size k-connected spanning subgraphs via matching

  1996cites this paper
• Approximating the minimum equivalent digraph

  1994cites this paper
• A compendium of NP optimization problems

  1994cites this paper