Empirical analysis of algorithms for the shortest negative cost cycle problem

DOI10.1016/J.DAM.2018.03.055MaRDI QIDQ1634773zbMATH OpenOpenAlexFDO

Authors Y. Aharonov

Publication date 18 December 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2018.03.055

zbMATH Keywords

cycledistinct edge widthgraph theorypath widthsingle source shortest path

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Randomized algorithms for finding the shortest negative cost cycle in networks
• Negative-cycle detection algorithms
• Negative-cycle detection algorithms
• Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs
• Computational Science – ICCS 2005

Cites work

• An analysis of totally clairvoyant scheduling
• Automated Reasoning
• Deciding Quantifier-Free Presburger Formulas Using Parameterized Solution Bounds
• Fast and Flexible Difference Constraint Propagation for DPLL(T)
• Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems
• scientific article; zbMATH DE number 5345853 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 2090312 (Why is no real title available?)
• scientific article; zbMATH DE number 3325539 (Why is no real title available?)
• Improved algorithms for optimal length resolution refutation in difference constraint systems
• Introduction to algorithms.
• On the negative cost girth problem in planar networks
• Optimal length resolution refutations of difference constraint systems
• Randomized algorithms for finding the shortest negative cost cycle in networks
• Self-testing/correcting with applications to numerical problems

Cited in

(8)

• Randomized algorithms for finding the shortest negative cost cycle in networks
• On the complexity of algorithms for detecting \(k\)-length negative cost cycles
• On the analysis of optimization problems in arc-dependent networks
• Fast algorithms for the undirected negative cost cycle detection problem
• Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs
• A mechanical verification of the stressing algorithm for negative cost cycle detection in networks
• Computational Science – ICCS 2005
• On approximating optimal weight ``no-certificates in weighted difference constraint systems

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: Empirical analysis of algorithms for the shortest negative cost cycle problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1634773)