IDEAS home Printed from https://ideas.repec.org/p/ver/wpaper/08-2018.html
   My bibliography  Save this paper

A constrained minimum spanning tree problem

Author

Listed:
  • Alberto Peretti

    (Department of Economics (University of Verona))

Abstract

In the classical general framework of the minimum spanning tree problem for a weighted graph we consider the case in which a predetermined vertex has a certain fixed degree. In other words, given a weighted graph G, one of its vertices v0 and a positive integer k, we consider the problem of finding the minimum spanning tree of G in which the vertex v0 has degree k, that is the number of edges coming out of v0. We recall that among the various methods for the solution of the unconstrained problem an efficient way to find the minimum spanning tree is based on the simple procedure of choosing one after the other an edge of minimum weight that has not be chosen yet and does not create cycles if added to the previously chosen edges. This technique is known as the “greedy algorithm”. There are problems for which the greedy algorithm works and problems for which it does not. We prove that for the solution of the one degree constrained minimum spanning tree problem the classical greedy algorithm finds a right solution.

Suggested Citation

  • Alberto Peretti, 2018. "A constrained minimum spanning tree problem," Working Papers 08/2018, University of Verona, Department of Economics.
    • Handle: RePEc:ver:wpaper:08/2018
    as

    Download full text from publisher

    File URL: http://dse.univr.it/home/workingpapers/wp2018n8.pdf
    File Function: First version
    Download Restriction: no
    ---><---

    More about this item

    Keywords

    Graph theory; Trees; Minimum spanning tree problem; Constrained minimum spanning trees;
    All these keywords.

    JEL classification:

    • C65 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Miscellaneous Mathematical Tools
    • C69 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Other

    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:ver:wpaper:08/2018. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Michael Reiter (email available below). General contact details of provider: https://edirc.repec.org/data/isverit.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.