Minimum mean cycle problem in bidirected and skew-symmetric graphs

DOI10.1016/J.DISOPT.2008.09.005MaRDI QIDQ1013299zbMATH OpenOpenAlexFDO

Authors Maxim Babenko, Alexander V. Karzanov

Publication date 17 April 2009

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0608443

zbMATH Keywords

bidirected graphminimum mean cycleskew-symmetric graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Paths and cycles (05C38)

Abstract: 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,ElogV))$-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.

Recommendations

• Algorithms for finding the minimum cycle mean in the weighted directed graph
• Approximating the minimum cycle mean
• A note on finding minimum mean cycle
• Approximating the minimum cycle mean
• Algorithms to compute minimum cycle basis in directed graphs

Cites work

• scientific article; zbMATH DE number 634021 (Why is no real title available?)
• scientific article; zbMATH DE number 3409134 (Why is no real title available?)
• A characterization of the minimum cycle mean in a digraph
• Antisymmetrical Digraphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Free multiflows in bidirected and skew-symmetric graphs
• Maximum skew-symmetric flows and matchings
• Path problems in skew-symmetric graphs
• Reducing Matching to Polynomial Size Linear Programming

Cited in

(3)

• Shortest paths in nearly conservative digraphs
• A note on finding minimum mean cycle
• Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure

This page was built for publication: Minimum mean cycle problem in bidirected and skew-symmetric graphs

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