IDEAS home Printed from https://ideas.repec.org/p/cpb/discus/29.html
   My bibliography  Save this paper

An efficient method for detecting redundant feedback vertices

Author

Listed:
  • Berend Hasselman

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.

Suggested Citation

  • Berend Hasselman, 2004. "An efficient method for detecting redundant feedback vertices," CPB Discussion Paper 29, CPB Netherlands Bureau for Economic Policy Analysis.
    • Handle: RePEc:cpb:discus:29
    as

    Download full text from publisher

    File URL: http://www.cpb.nl/system/files/cpbmedia/publicaties/download/efficient-method-detecting-redundant-feedback-vertices.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Mr. Hamid Faruqee & Mr. Douglas Laxton & Mr. Bart Turtelboom & Mr. Peter Isard & Mr. Eswar S Prasad, 1998. "Multimod Mark III: The Core Dynamic and Steady State Model," IMF Occasional Papers 1998/010, International Monetary Fund.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Olaf van 't Veer, 2006. "Solving large scale normalised rational expectations models," CPB Discussion Paper 54, CPB Netherlands Bureau for Economic Policy Analysis.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Berger, Johannes & Strohner, Ludwig, 2020. "Documentation of the PUblic Policy Model for Austria and other European countries (PUMA)," Research Papers 11, EcoAustria – Institute for Economic Research.
    2. Alistair Dieppe & Jerome Henry & Peter Mc Adam, "undated". "Labour market dynamics in the euro area: A model-based sensitivity analysis," Modeling, Computing, and Mastering Complexity 2003 09, Society for Computational Economics.
    3. Ngah Ntiga, Louis Henri, 2022. "Estimation Bayésienne d’un modèle DSGE des effets de la politique budgétaire sur l’économie camerounaise," Dynare Working Papers 76, CEPREMAP.
    4. Camille Logeay & Silke Tober, 2006. "Hysteresis And The Nairu In The Euro Area," Scottish Journal of Political Economy, Scottish Economic Society, vol. 53(4), pages 409-429, September.
    5. Ngah Ntiga, Louis Henri, 2022. "Estimation Bayésienne d’un modèle DSGE des effets de la politique budgétaire sur l’économie camerounaise [Bayesian estimation of a DSGE model of the effects of fiscal policy on the Cameroonian econ," MPRA Paper 113929, University Library of Munich, Germany, revised Aug 2022.
    6. Fofana, Ismaél & Chitiga, Margaret & Mabugu, Ramos, 2009. "Oil prices and the South African economy: A macro-meso-micro analysis," Energy Policy, Elsevier, vol. 37(12), pages 5509-5518, December.
    7. Denise Côté & John Kuszczak & Jean‐Paul Lam & Ying Liu & Pierre St‐Amant, 2004. "The performance and robustness of simple monetary policy rules in models of the Canadian economy," Canadian Journal of Economics/Revue canadienne d'économique, John Wiley & Sons, vol. 37(4), pages 978-998, November.
    8. Dieppe, Alistair & Henry, Jerome, 2004. "The euro area viewed as a single economy: how does it respond to shocks?," Economic Modelling, Elsevier, vol. 21(5), pages 833-875, September.
    9. Hwee Kwan Chow, 2004. "A VAR Analysis of Singapore’s Monetary Transmission Mechanism," Working Papers 19-2004, Singapore Management University, School of Economics.
    10. Olaf van 't Veer, 2006. "Solving large scale normalised rational expectations models," CPB Discussion Paper 54, CPB Netherlands Bureau for Economic Policy Analysis.
    11. Aye, Goodness C. & Dadam, Vincent & Gupta, Rangan & Mamba, Bonginkosi, 2014. "Oil price uncertainty and manufacturing production," Energy Economics, Elsevier, vol. 43(C), pages 41-47.

    More about this item

    JEL classification:

    • J51 - Labor and Demographic Economics - - Labor-Management Relations, Trade Unions, and Collective Bargaining - - - Trade Unions: Objectives, Structure, and Effects

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cpb:discus:29. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: the person in charge (email available below). General contact details of provider: https://edirc.repec.org/data/cpbgvnl.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.