---
res:
  bibo_abstract:
  - 'While operating communication networks adaptively may improve utilization and
    performance, frequent adjustments also introduce an algorithmic challenge: the
    re-optimization of traffic engineering solutions is time-consuming and may limit
    the granularity at which a network can be adjusted. This paper is motivated by
    question whether the reactivity of a network can be improved by re-optimizing
    solutions dynamically rather than from scratch, especially if inputs such as link
    weights do not change significantly. This paper explores to what extent dynamic
    algorithms can be used to speed up fundamental tasks in network operations. We
    specifically investigate optimizations related to traffic engineering (namely
    shortest paths and maximum flow computations), but also consider spanning tree
    and matching applications. While prior work on dynamic graph algorithms focusses
    on link insertions and deletions, we are interested in the practical problem of
    link weight changes. We revisit existing upper bounds in the weight-dynamic model,
    and present several novel lower bounds on the amortized runtime for recomputing
    solutions. In general, we find that the potential performance gains depend on
    the application, and there are also strict limitations on what can be achieved,
    even if link weights change only slightly.@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Monika H
      foaf_name: Henzinger, Monika H
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
    orcid: 0000-0002-5008-6530
  - foaf_Person:
      foaf_givenName: Ami
      foaf_name: Paz, Ami
      foaf_surname: Paz
  - foaf_Person:
      foaf_givenName: Stefan
      foaf_name: Schmid, Stefan
      foaf_surname: Schmid
  bibo_doi: 10.23919/ifipnetworking52078.2021.9472803
  dct_date: 2021^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1861-2288
  dct_language: eng
  dct_publisher: Institute of Electrical and Electronics Engineers@
  dct_title: On the complexity of weight-dynamic network algorithms@
...