Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs
verfasst von : Xiaofeng Gu, Kamesh Madduri, K. Subramani, Hong-Jian Lai
Erschienen in: Frontiers in Algorithmics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we explore the design of algorithms for the problem of checking whether an
undirected
graph contains a negative cost cycle (UNCCD). It is known that this problem is significantly harder than the corresponding problem in directed graphs. Current approaches for solving this problem involve reducing it to either the
b
-matching problem or the
T
-join problem. The latter approach is more efficient in that it runs in
O
(
n
3
) time on a graph with
n
vertices and
m
edges, while the former runs in
O
(
n
6
) time. This paper shows that instances of the UNCCD problem, in which edge weights are restricted to be in the range { −
K
··
K
} can be solved in
O
(
n
2.75
·log
n
) time. Our algorithm is basically a variation of the
T
-join approach, which exploits the existence of extremely efficient shortest path algorithms in graphs with integral positive weights. We also provide an implementation profile of the algorithms discussed.