Finding all the negative cycles in a directed graph

DOI10.1016/S0166-218X(01)00201-3zbMath0999.05057WikidataQ127775912 ScholiaQ127775912MaRDI QIDQ1602697

Takeo Yamada, Harunobu Kinoshita

Publication date: 24 June 2002

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

zbMATH Keywords

algorithmcyclesdigraphssearch strategies

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Related Items

On stability of discrete-time switched systems, A graph theoretic approach to input-to-state stability of switched systems, MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles, Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles, On the shortest path problem with negative cost cycles, Finding a stabilising switching law for switching nonlinear models, Randomized algorithms for stabilizing switching signals

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• A characterization of the minimum cycle mean in a digraph
• A comparison of three algorithms for finding fundamental cycles in a directed graph
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Enumeration of the Elementary Circuits of a Directed Graph
• A Mechanical Analysis of the Cyclic Structure of Undirected Linear Graphs
• An efficient search algorithm to find the elementary circuits of a graph
• A New Search Algorithm for Finding the Simple Cycles of a Finite Directed Graph