---
_id: '11793'
abstract:
- lang: eng
  text: "We study the problem of maintaining a breadth-first spanning tree (BFS tree)
    in partially dynamic distributed networks modeling a sequence of either failures
    or additions of communication links (but not both). We show (1 + ε)-approximation
    algorithms whose amortized time (over some number of link changes) is sublinear
    in D, the maximum diameter of the network. This breaks the Θ(D) time bound of
    recomputing “from scratch”.\r\n\r\nOur technique also leads to a (1 + ε)-approximate
    incremental algorithm for single-source shortest paths (SSSP) in the sequential
    (usual RAM) model. Prior to our work, the state of the art was the classic exact
    algorithm of [9] that is optimal under some assumptions [27]. Our result is the
    first to show that, in the incremental setting, this bound can be beaten in certain
    cases if a small approximation is allowed."
alternative_title:
- LNCS
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: Sebastian
  full_name: Krinninger, Sebastian
  last_name: Krinninger
- first_name: Danupon
  full_name: Nanongkai, Danupon
  last_name: Nanongkai
citation:
  ama: 'Henzinger MH, Krinninger S, Nanongkai D. Sublinear-time maintenance of breadth-first
    spanning tree in partially dynamic networks. In: <i>40th International Colloquium
    on Automata, Languages, and Programming</i>. Vol 7966. Springer Nature; 2013:607–619.
    doi:<a href="https://doi.org/10.1007/978-3-642-39212-2_53">10.1007/978-3-642-39212-2_53</a>'
  apa: 'Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2013). Sublinear-time
    maintenance of breadth-first spanning tree in partially dynamic networks. In <i>40th
    International Colloquium on Automata, Languages, and Programming</i> (Vol. 7966,
    pp. 607–619). Riga, Latvia: Springer Nature. <a href="https://doi.org/10.1007/978-3-642-39212-2_53">https://doi.org/10.1007/978-3-642-39212-2_53</a>'
  chicago: Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time
    Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks.” In
    <i>40th International Colloquium on Automata, Languages, and Programming</i>,
    7966:607–619. Springer Nature, 2013. <a href="https://doi.org/10.1007/978-3-642-39212-2_53">https://doi.org/10.1007/978-3-642-39212-2_53</a>.
  ieee: M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time maintenance
    of breadth-first spanning tree in partially dynamic networks,” in <i>40th International
    Colloquium on Automata, Languages, and Programming</i>, Riga, Latvia, 2013, vol.
    7966, pp. 607–619.
  ista: 'Henzinger MH, Krinninger S, Nanongkai D. 2013. Sublinear-time maintenance
    of breadth-first spanning tree in partially dynamic networks. 40th International
    Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium
    on Automata, Languages, and Programming, LNCS, vol. 7966, 607–619.'
  mla: Henzinger, Monika H., et al. “Sublinear-Time Maintenance of Breadth-First Spanning
    Tree in Partially Dynamic Networks.” <i>40th International Colloquium on Automata,
    Languages, and Programming</i>, vol. 7966, Springer Nature, 2013, pp. 607–619,
    doi:<a href="https://doi.org/10.1007/978-3-642-39212-2_53">10.1007/978-3-642-39212-2_53</a>.
  short: M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, 40th International Colloquium
    on Automata, Languages, and Programming, Springer Nature, 2013, pp. 607–619.
conference:
  end_date: 2013-07-12
  location: Riga, Latvia
  name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
  start_date: 2013-07-08
date_created: 2022-08-11T11:25:13Z
date_published: 2013-07-01T00:00:00Z
date_updated: 2023-02-21T16:28:26Z
day: '01'
doi: 10.1007/978-3-642-39212-2_53
extern: '1'
external_id:
  arxiv:
  - '1512.08147'
intvolume: '      7966'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1512.08147
month: '07'
oa: 1
oa_version: Preprint
page: 607–619
publication: 40th International Colloquium on Automata, Languages, and Programming
publication_identifier:
  isbn:
  - '9783642392115'
  issn:
  - 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '11793'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Sublinear-time maintenance of breadth-first spanning tree in partially dynamic
  networks
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7966
year: '2013'
...