The problem of the optimal biobjective spanning tree

Simple item page
dc.contributor.authorRamos Domínguez, Rosa María
dc.contributor.authorAlonso, S.
dc.contributor.authorSicilia, J.
dc.contributor.authorGonzález, C.
dc.date.accessioned2023-06-20T17:06:49Z
dc.date.available2023-06-20T17:06:49Z
dc.date.issued1998-12-16
dc.description.abstractThis paper studies the problem of finding the set of optimal spanning trees of a connected graph, considering two cost functions defined on the set of edges. This problem is NP-hard and the solution is described through an algorithm that builds the family of efficient trees. This algorithm needs two procedures that solve the following uniobjective problems: the construction of all the spanning trees of a connected graph and the construction of the whole set of minimum cost spanning trees. The computational results obtained are shown in Section 5. (C) 1998 Elsevier Science B.V. All rights reserved.
dc.description.departmentDepto. de Estadística e Investigación Operativa
dc.description.facultyFac. de Ciencias Matemáticas
dc.description.refereedTRUE
dc.description.sponsorshipDireccion General de Universidades e Investigación del Gobierno de Canarias.
dc.description.statuspub
dc.eprint.idhttps://eprints.ucm.es/id/eprint/17604
dc.identifier.citationR.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows, Prentice-Hall, Englewood Cliffs, NJ, 1993. P.M. Camerini, G. Galbiati, F. Maffioli, Algorithm for finding optimum trees: Description, use and evaluation,Annals of Operations Research 13 (1988) 265-397. A. Cayley, Collected papers, Quarterly Journal of Mathematics 13 (1987) 26. W.K. Chen, H.C. Li, Computer generation of directed trees and complete trees, International Journal of Electronics 34 (19739 1. H.W. Corley, Efficient spanning trees, Journal of Optimization Theory and Applications 45 (3) (1985) 481-485. R. Fletcher, Practical Methods of Optimization, vols. 1 and 2, Wiley, New York, 1987. H.N. Gabow, E.W. Myers, Finding all spanning trees of directed and undirected graphs, SIAM Journal on Computing 7 (1978) 280-287. R.L. Graham, P. Hell, On the history of the minimum spanning tree problem, Annals of the History of Computing 7 (1) (1985) 43-57. H.W. Hammacker, G. Ruhe, On spanning tree problems with multiple objectives, Annals of Operations Research 52 (1994) 209-230. S. Kapoor, H. Ramesh, Algorithms for enumerating all spanning tree of undirected and weighted graphs, SIAM Journal on Computing 24 (1995) 247-265. G. Kirchhoff, Úber die Auflosung der Gleichungen, anf welche man bei der Untersuchung der Linearen Verteilung Galvanisher Ströme Gefúhrt Wird, Poggendorg's Annalen der Physik and Chemie 72 (1847) 497-508. J.B. Kruskal, On the shortest spanning tree of a graph and the traveling salesman problem, Proceedings of American Mathematical Society 7 (1956) 48-50. W. Mayeda, S.L. Hakimi, W.K. Chen, N. Deo, Generation of complete trees, IEEE Transaction CT 15 (1968). R.C. Prim, Shortest connection networks and some generations, Bell Syst. Tech. J. 36 (1957) 1389-1401. R.C. Read, R.E. Tarjan, Bounds on backtrack algorithms for listing cycles, paths, and spanning trees, Networks 5 (1975) 237-252. A. Shioura, A. Tamura, Efficiently scanning all spanning trees of an undirected graph, Journal of Operations Research Society of Japan 38 (1995) 331-343. A. Shioura, A. Tamura, T. Uno, An optimal algorithm for scanning all spanning trees of undirected graphs, SIAM Journal on Computing 26 (1997) 678-692. R.E. Tarjan, Data structures and networks algorithms, in: CBMS Regional Conference, SIAM, Philadelphia, 1983. J. Ward, The structure of efficients sets for convex objectives, Mathematics of Operations Research 14 (2)(1989) 249-257.
dc.identifier.doi10.1016/S0377-2217
dc.identifier.issn0377-2217
dc.identifier.officialurlhttp://www.sciencedirect.com/science/article/pii/S0377221797003913
dc.identifier.relatedurlhttp://www.sciencedirect.com/
dc.identifier.urihttps://hdl.handle.net/20.500.14352/57791
dc.issue.number3
dc.journal.titleEuropean journal of operational research
dc.language.isoeng
dc.page.final628
dc.page.initial617
dc.publisherElsevier Science
dc.relation.projectIDproject number 93/108
dc.rights.accessRightsrestricted access
dc.subject.cdu519.8
dc.subject.keywordMulti-criteria analysis
dc.subject.keywordSpanning tree
dc.subject.keywordMinimum cost spanning tree
dc.subject.keywordBiobjective optimal cost spanning tree
dc.subject.keywordGraphs
dc.subject.ucmInvestigación operativa (Matemáticas)
dc.subject.unesco1207 Investigación Operativa
dc.titleThe problem of the optimal biobjective spanning tree
dc.typejournal article
dc.volume.number111
dspace.entity.typePublication
relation.isAuthorOfPublicationbf1332c5-1ade-4e50-9bd5-c46a938d2344
relation.isAuthorOfPublication.latestForDiscoverybf1332c5-1ade-4e50-9bd5-c46a938d2344
Download
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
RamosDom02.pdf
Size:
248.41 KB
Format:
Adobe Portable Document Format
Download
Collections
Artículos