On Strongly Connected Digraphs with Bounded Cycle Length

Details On Strongly Connected Digraphs with Bounded Cycle Length On Strongly Connected Digraphs with Bounded Cycle Length

2002-05-10

arxiv.org/abs/cs/0205011v1

Discrete Applied Mathematics 69(3):281-289 (1996)

Computer Science

Data Structures and Algorithms

Scientific paper

The MEG (minimum equivalent graph) problem is, given a directed graph, to find a small subset of the edges that maintains all reachability relations between nodes. The problem is NP-hard. This paper gives a proof that, for graphs where each directed cycle has at most three edges, the MEG problem is equivalent to maximum bipartite matching, and therefore solvable in polynomial time. This leads to an improvement in the performance guarantee of the previously best approximation algorithm for the general problem in ``Approximating the Minimum Equivalent Digraph'' (1995).

Affiliated with

Also associated with

No associations

Rating

On Strongly Connected Digraphs with Bounded Cycle Length does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Strongly Connected Digraphs with Bounded Cycle Length, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Strongly Connected Digraphs with Bounded Cycle Length will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-382479