کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141764 957089 2009 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Minimum mean cycle problem in bidirected and skew-symmetric graphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
Minimum mean cycle problem in bidirected and skew-symmetric graphs
چکیده انگلیسی

The problem of finding, in an edge-weighted bidirected   graph G=(V,E)G=(V,E), a cycle whose mean edge weight is minimum 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.) We develop an algorithm to solve this problem in O(V2min{V2,ElogV})O(V2min{V2,ElogV}) time (to compare: the complexity of an improved version of Barahona’s algorithm for undirected cycles is O(V4)O(V4)). 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 6, Issue 1, February 2009, Pages 92–97
نویسندگان
, ,