1. Research UNE
  2. UNE
  3. Journal Article
Please use this identifier to cite or link to this item: https://hdl.handle.net/1959.11/26781
Full metadata record
DC FieldValueLanguage
dc.contributor.authorEngel, Konraden
dc.contributor.authorKalinowski, Thomasen
dc.contributor.authorSavelsbergh, Martin W Pen
dc.date.accessioned2019-04-24T03:41:25Z-
dc.date.available2019-04-24T03:41:25Z-
dc.date.issued2017-02-
dc.identifier.citationJournal of Graph Algorithms and Applications, 21(4), p. 417-432en
dc.identifier.issn1526-1719en
dc.identifier.urihttps://hdl.handle.net/1959.11/26781-
dc.description.abstractGiven an edge-weighted graph G = (V,E) and a set E<sub>0</sub>⊂E , the incremental network design problem with minimum spanning trees asks for a sequence of edges e′ <sub>1</sub> , … , e ′ <sub>T</sub> ∈ E ∖ E <sub>0 </sub> minimizing ∑ <sup>T</sup> <sub> t = 1</sub> w ( X <sub>t</sub> ) where w(X<sub>t</sub>) is the weight of a minimum spanning tree X<sub>t</sub> for the subgraph (V,E<sub>0</sub>∪ { e ′ <sub>1</sub> , … , e ′ <sub>T</sub> } ) and T=|E∖ E 0 |. We prove that this problem can be solved by a greedy algorithm.en
dc.languageenen
dc.publisherBrown University, Department of Computer Scienceen
dc.relation.ispartofJournal of Graph Algorithms and Applicationsen
dc.titleIncremental Network Design with Minimum Spanning Treesen
dc.typeJournal Articleen
dc.identifier.doi10.7155/jgaa.00423en
dcterms.accessRightsGolden
local.contributor.firstnameKonraden
local.contributor.firstnameThomasen
local.contributor.firstnameMartin W Pen
local.subject.for2008010104 Combinatorics and Discrete Mathematics (excl. Physical Combinatorics)en
local.subject.seo2008970101 Expanding Knowledge in the Mathematical Sciencesen
local.profile.schoolSchool of Science and Technologyen
local.profile.emailtkalinow@une.edu.auen
local.output.categoryC1en
local.record.placeauen
local.record.institutionUniversity of New Englanden
local.publisher.placeUnited States of Americaen
local.format.startpage417en
local.format.endpage432en
local.identifier.scopusid85021667365en
local.peerreviewedYesen
local.identifier.volume21en
local.identifier.issue4en
local.access.fulltextYesen
local.contributor.lastnameEngelen
local.contributor.lastnameKalinowskien
local.contributor.lastnameSavelsberghen
dc.identifier.staffune-id:tkalinowen
local.profile.orcid0000-0002-8444-6848en
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.identifier.unepublicationidune:1959.11/26781en
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
local.title.maintitleIncremental Network Design with Minimum Spanning Treesen
local.output.categorydescriptionC1 Refereed Article in a Scholarly Journalen
local.search.authorEngel, Konraden
local.search.authorKalinowski, Thomasen
local.search.authorSavelsbergh, Martin W Pen
local.uneassociationUnknownen
local.year.published2017en
local.fileurl.closedpublishedhttps://rune.une.edu.au/web/retrieve/a18042f2-d213-4370-add8-e01326813f1fen
local.subject.for2020490404 Combinatorics and discrete mathematics (excl. physical combinatorics)en
local.subject.seo2020280118 Expanding knowledge in the mathematical sciencesen
Appears in Collections:Journal Article
School of Science and Technology
Files in This Item:
2 files
File Description SizeFormat 
Show simple item record
Google Media

Google ScholarTM

Check

Altmetric


Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.