Finding all the negative cycles in a directed graph
type: Item
instance of: scholarly article
title: Finding all the negative cycles in a directed graph
zbMATH Open document ID: 0999.05057
DOI: 10.1016/S0166-218X(01)00201-3
author: Takeo Yamada
author: Harunobu Kinoshita
published in: Discrete Applied Mathematics
publication date: 2002-06-24T00:00:00Z
review text: The authors study weighted directed graphs, where the edges can have negative weights. They give an algorithm to find all the elementary cycles with negative total weights. This algorithm is constructed in the divide-and-conquer paradigm and some recursive procedure. The algorithm is tested in three series of examples.
reviewed by: Ferdinand Gliviak
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1758382
zbMATH Keywords: digraphs
zbMATH Keywords: search strategies
zbMATH Keywords: algorithm
zbMATH Keywords: cycles
MaRDI profile type: Publication
cites work: Q3056948
cites work: Q5523467
cites work: A comparison of three algorithms for finding fundamental cycles in a directed graph
cites work: A note on two problems in connexion with graphs
cites work: Q4198056
cites work: A characterization of the minimum cycle mean in a digraph
cites work: Q4130999
cites work: Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
cites work: Q4344098
cites work: Enumeration of the Elementary Circuits of a Directed Graph
cites work: An efficient search algorithm to find the elementary circuits of a graph
cites work: A New Search Algorithm for Finding the Simple Cycles of a Finite Directed Graph
cites work: A Mechanical Analysis of the Cyclic Structure of Undirected Linear Graphs
Wikidata QID: Q127775912
description: scientific article; zbMATH DE number 1758382