Minimum Mean Cycle Problem in Bidirected and Skew-Symmetric Graphs
| dc.creator | Babenko, Maxim A. | |
| dc.creator | Karzanov, Alexander V. | |
| dc.date | 2006-08-17 | |
| dc.date.accessioned | 2026-07-07T07:21:53Z | |
| dc.date.available | 2026-07-07T07:21:53Z | |
| dc.description | 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. | |
| dc.description | 10 pages, 2 figures | |
| dc.identifier | https://arxiv.org/abs/math/0608443 | |
| dc.identifier | http://arxiv.org/abs/math/0608443 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/115463 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C38, 05C85, 90C27 | |
| dc.title | Minimum Mean Cycle Problem in Bidirected and Skew-Symmetric Graphs | |
| dc.type | text |