An efficient method for detecting redundant feedback vertices

Berend Hasselman

No 29, CPB Discussion Paper from CPB Netherlands Bureau for Economic Policy Analysis

Abstract: A feedback vertex set of a directed graph cuts all cycles in a directed graph. Such a set can be obtained with the Levy–Low contraction algorithm, which generates a small feedback vertex set but not always a minimum size feedback set since it sometimes needs a heuristic contraction rule in order to reduce a graph completely. This may lead to members in a feedback vertex set being redundant in the sense that they do not cut a cycle of the original directed graph. In this paper we develop two algorithms for detecting such redundant feedback vertices efficiently. The algorithms are applied to analysing large nonlinear normalised systems of equations and to the feedback sets of a series of random directed graphs used by other authors. Computational experiments show that the algorithms developed in this paper significantly improve on the brute force algorithm.

JEL-codes: J51 (search for similar items in EconPapers)
Date: 2004-04
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.cpb.nl/sites/default/files/publicaties ... eedback-vertices.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cpb:discus:29

Access Statistics for this paper

More papers in CPB Discussion Paper from CPB Netherlands Bureau for Economic Policy Analysis Contact information at EDIRC.
Bibliographic data for series maintained by ().