Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs

DOI10.1007/978-3-642-02270-8_7zbMath1248.05198OpenAlexW2140226761MaRDI QIDQ5321692

Xiaofeng Gu, Hong-Jian Lai, Kamesh Madduri, K. Subramani and Vahan Mkrtchyan

Publication date: 14 July 2009

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02270-8_7

zbMATH Keywords

design of algorithmsmatching problemnegative cost cycleefficiency of algorithmjoin problemundirected mgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles ⋮ MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles ⋮ Fast algorithms for the undirected negative cost cycle detection problem

Uses Software

• DIMACS

Cites Work

• Scaling Algorithms for the Shortest Paths Problem
• Combinatorial optimization. Theory and algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs