Minimum mean cycle problem in bidirected and skew-symmetric graphs

DOI10.1016/J.DISOPT.2008.09.005zbMATH Open1161.05327arXivmath/0608443OpenAlexW2086432678MaRDI QIDQ1013299FDOQ1013299

Authors: Maxim Babenko, Alexander V. Karzanov 

Publication date: 17 April 2009

Published in: Discrete Optimization (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A characterization of the minimum cycle mean in a digraph
• Title not available (Why is that?)
• Maximum skew-symmetric flows and matchings
• Free multiflows in bidirected and skew-symmetric graphs
• Path problems in skew-symmetric graphs
• Antisymmetrical Digraphs
• Reducing Matching to Polynomial Size Linear Programming
• Title not available (Why is that?)

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)