File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Algorithms for updating minimal spanning trees

TitleAlgorithms for updating minimal spanning trees
Authors
Issue Date1978
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jcss
Citation
Journal Of Computer And System Sciences, 1978, v. 16 n. 3, p. 333-344 How to Cite?
AbstractThe problem of finding the minimal spanning tree on an undirected weighted graph has been investigated by many people and O(n2) algorithms are well known. P. M. Spira and A. Pan (Siam J. Computing 4 (1975), 375-380) present an O(n) algorithm for updating the minimal spanning tree if a new vertex is inserted into the graph. In this paper, we present another O(n) algorithm simpler than that presented by Spira and Pan for the insertion of a vertex. Spira and Pan further show that the deletion of a vertex requires O(n2) steps. If all the vertices are considered, O(n3) steps may be used. The algorithm which we present here takes only O(n2) steps and labels the vertices of the graph in such a way that any vertex may be deleted from the graph and the minimal spanning tree can be updated in constant time. Similar results are obtained for the insertion and the deletion of an edge. © 1978.
Persistent Identifierhttp://hdl.handle.net/10722/152196
ISSN
2015 Impact Factor: 1.583
2015 SCImago Journal Rankings: 1.334

 

DC FieldValueLanguage
dc.contributor.authorChin, Fen_US
dc.contributor.authorHouck, Den_US
dc.date.accessioned2012-06-26T06:36:26Z-
dc.date.available2012-06-26T06:36:26Z-
dc.date.issued1978en_US
dc.identifier.citationJournal Of Computer And System Sciences, 1978, v. 16 n. 3, p. 333-344en_US
dc.identifier.issn0022-0000en_US
dc.identifier.urihttp://hdl.handle.net/10722/152196-
dc.description.abstractThe problem of finding the minimal spanning tree on an undirected weighted graph has been investigated by many people and O(n2) algorithms are well known. P. M. Spira and A. Pan (Siam J. Computing 4 (1975), 375-380) present an O(n) algorithm for updating the minimal spanning tree if a new vertex is inserted into the graph. In this paper, we present another O(n) algorithm simpler than that presented by Spira and Pan for the insertion of a vertex. Spira and Pan further show that the deletion of a vertex requires O(n2) steps. If all the vertices are considered, O(n3) steps may be used. The algorithm which we present here takes only O(n2) steps and labels the vertices of the graph in such a way that any vertex may be deleted from the graph and the minimal spanning tree can be updated in constant time. Similar results are obtained for the insertion and the deletion of an edge. © 1978.en_US
dc.languageengen_US
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jcssen_US
dc.relation.ispartofJournal of Computer and System Sciencesen_US
dc.titleAlgorithms for updating minimal spanning treesen_US
dc.typeArticleen_US
dc.identifier.emailChin, F:chin@cs.hku.hken_US
dc.identifier.authorityChin, F=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-0010660720en_US
dc.identifier.volume16en_US
dc.identifier.issue3en_US
dc.identifier.spage333en_US
dc.identifier.epage344en_US
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridChin, F=7005101915en_US
dc.identifier.scopusauthoridHouck, D=36783415600en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats