Minimum Mean Cycle Problem in Bidirected and Skew-Symmetric Graphs

Details Minimum Mean Cycle Problem in Bidirected and Skew-Symmetric Graphs Minimum Mean Cycle Problem in Bidirected and Skew-Symmetric Graphs

2006-08-17

arxiv.org/abs/math/0608443v1

Mathematics

Combinatorics

10 pages, 2 figures

Scientific paper

The problem of finding, in an edge-weighted bidirected graph $G=(V,E)$, a cycle with minimum mean weight of its edges generalizes similar problems for both directed and undirected graphs. (The problem is considered in two variants: for the cycles without repeated edges and for the cycles without repeated nodes.) In this note we develop an algorithm to solve this problem in $O(V^2 \min(V^2, E\log V))$-time (to compare: the complexity of an improved version of Barahona's algorithm for undirected cycles is $O(V^4)$). Our algorithm is based on a certain general approach to minimum mean problems and uses, as a subroutine, Gabow's algorithm for the minimum weight 2-factor problem in a graph. The problem admits a reformulation in terms of regular cycles in a skew-symmetric graph.

Affiliated with

Also associated with

No associations

Rating

Minimum Mean Cycle Problem in Bidirected and Skew-Symmetric Graphs 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 Minimum Mean Cycle Problem in Bidirected and Skew-Symmetric Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Mean Cycle Problem in Bidirected and Skew-Symmetric Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-389108