---
_id: '11649'
abstract:
- lang: eng
  text: '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.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Ami
  full_name: Paz, Ami
  last_name: Paz
- first_name: Stefan
  full_name: Schmid, Stefan
  last_name: Schmid
citation:
  ama: 'Henzinger M, Paz A, Schmid S. On the complexity of weight-dynamic network
    algorithms. In: <i>IFIP Networking Conference</i>. Institute of Electrical and
    Electronics Engineers; 2021. doi:<a href="https://doi.org/10.23919/ifipnetworking52078.2021.9472803">10.23919/ifipnetworking52078.2021.9472803</a>'
  apa: 'Henzinger, M., Paz, A., &#38; Schmid, S. (2021). On the complexity of weight-dynamic
    network algorithms. In <i>IFIP Networking Conference</i>.  Espoo and Helsinki,
    Finland: Institute of Electrical and Electronics Engineers. <a href="https://doi.org/10.23919/ifipnetworking52078.2021.9472803">https://doi.org/10.23919/ifipnetworking52078.2021.9472803</a>'
  chicago: Henzinger, Monika, Ami Paz, and Stefan Schmid. “On the Complexity of Weight-Dynamic
    Network Algorithms.” In <i>IFIP Networking Conference</i>. Institute of Electrical
    and Electronics Engineers, 2021. <a href="https://doi.org/10.23919/ifipnetworking52078.2021.9472803">https://doi.org/10.23919/ifipnetworking52078.2021.9472803</a>.
  ieee: M. Henzinger, A. Paz, and S. Schmid, “On the complexity of weight-dynamic
    network algorithms,” in <i>IFIP Networking Conference</i>,  Espoo and Helsinki,
    Finland, 2021.
  ista: 'Henzinger M, Paz A, Schmid S. 2021. On the complexity of weight-dynamic network
    algorithms. IFIP Networking Conference. IFIP: Networking.'
  mla: Henzinger, Monika, et al. “On the Complexity of Weight-Dynamic Network Algorithms.”
    <i>IFIP Networking Conference</i>, Institute of Electrical and Electronics Engineers,
    2021, doi:<a href="https://doi.org/10.23919/ifipnetworking52078.2021.9472803">10.23919/ifipnetworking52078.2021.9472803</a>.
  short: M. Henzinger, A. Paz, S. Schmid, in:, IFIP Networking Conference, Institute
    of Electrical and Electronics Engineers, 2021.
conference:
  end_date: 2021-06-24
  location: ' Espoo and Helsinki, Finland'
  name: 'IFIP: Networking'
  start_date: 2021-06-21
date_created: 2022-07-25T11:13:06Z
date_published: 2021-06-21T00:00:00Z
date_updated: 2024-11-06T12:04:45Z
day: '21'
doi: 10.23919/ifipnetworking52078.2021.9472803
extern: '1'
external_id:
  arxiv:
  - '2105.13172'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.2105.13172'
month: '06'
oa: 1
oa_version: Preprint
publication: IFIP Networking Conference
publication_identifier:
  eissn:
  - 1861-2288
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the complexity of weight-dynamic network algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...