Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/7397
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | JANSSENS, Gerrit K. | - |
dc.contributor.author | Sörensen, K. | - |
dc.date.accessioned | 2007-12-20T16:15:48Z | - |
dc.date.available | 2007-12-20T16:15:48Z | - |
dc.date.issued | 2005 | - |
dc.identifier.citation | Pesquisa operacional, 25(2). p. 219-229 | - |
dc.identifier.issn | 0101-7438 | - |
dc.identifier.uri | http://hdl.handle.net/1942/7397 | - |
dc.description.abstract | A minimum spanning tree of an undirected graph can be easily obtained using classical algorithms by Prim or Kruskal. A number of algorithms have been proposed to enumerate all spanning trees of an undirected graph. Good time and space complexities are the major concerns of these algorithms. Most algorithms generate spanning trees using some fundamental cut or circuit. In the generation process, the cost of the tree is not taken into consideration. This paper presents an algorithm to generate spanning trees of a graph in order of increasing cost. By generating spanning trees in order of increasing cost, new opportunities appear. In this way, it is possible to determine the second smallest or, in general, the k-th smallest spanning tree. The smallest spanning tree satisfying some additional constraints can be found by checking at each generation whether these constraints are satisfied. Our algorithm is based on an algorithm by Murty (1967), which enumerates all solutions of an assignment problem in order of increasing cost. Both time and space complexities are discussed. | - |
dc.format.extent | 207022 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.title | An algorithm for generating all spanning trees of a graph in order of inceasing cost | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 229 | - |
dc.identifier.issue | 2 | - |
dc.identifier.spage | 219 | - |
dc.identifier.volume | 25 | - |
local.bibliographicCitation.jcat | A1 | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.bibliographicCitation.oldjcat | A1 | - |
local.identifier.vabb | c:vabb:145259 | - |
dc.identifier.doi | 10.1590/S0101-74382005000200004 | - |
item.fullcitation | JANSSENS, Gerrit K. & Sörensen, K. (2005) An algorithm for generating all spanning trees of a graph in order of inceasing cost. In: Pesquisa operacional, 25(2). p. 219-229. | - |
item.fulltext | With Fulltext | - |
item.validation | vabb 2010 | - |
item.contributor | JANSSENS, Gerrit K. | - |
item.contributor | Sörensen, K. | - |
item.accessRights | Open Access | - |
crisitem.journal.issn | 0101-7438 | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
janssens.pdf | Published version | 202.17 kB | Adobe PDF | View/Open |
Page view(s)
12
checked on Sep 7, 2022
Download(s)
12
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.