Fast algorithms for the undirected negative cost cycle detection problem

DOI10.1007/s00453-014-9945-xzbMath1336.05140OpenAlexW2077125082MaRDI QIDQ261362

Pavlos Eirinakis, Matthew Williamson, K. Subramani and Vahan Mkrtchyan

Publication date: 23 March 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-014-9945-x

zbMATH Keywords

perfect matching\(b\)-matching\(T\)-joinall pairs shortest pathnegative cost cycleundirected graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

A Branch-and-Price Algorithm for Solving the Hamiltonian p-Median Problem

Uses Software

• Blossom V
• Blossom IV
• DIMACS
• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Blossom V: A new implementation of a minimum cost perfect matching algorithm
• Solving (large scale) matching problems combinatorially
• Matching theory
• A zero-space algorithm for negative cost cycle detection in networks
• On a routing problem
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Solving matching problems with linear programming
• An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
• Efficiency of a Good But Not Linear Set Union Algorithm
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Faster scaling algorithms for general graph matching problems
• Computing Minimum-Weight Perfect Matchings
• Matching, Euler tours and the Chinese postman
• A Staged Primal-Dual Algorithm for Perfect b-Matching with Edge Capacities
• Fibonacci heaps and their uses in improved network optimization algorithms
• Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs
• Paths, Trees, and Flowers
• Implementation of O ( nm log n ) weighted matchings in general graphs
• Maximum matching and a polyhedron with 0,1-vertices
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Fast algorithms for the undirected negative cost cycle detection problem