---
_id: '20159'
abstract:
- lang: eng
  text: "Let G = (V,E) be an undirected graph on n vertices with non-negative capacities
    on its edges. The mincut sensitivity problem for the insertion of an edge is defined
    as follows. Build a compact data structure for G and a given set S ⊆ V of vertices
    that, on receiving any edge (x,y) ∈ S×S of positive capacity as query input, can
    efficiently report the set of all pairs from S× S whose mincut value increases
    upon insertion of the edge (x,y) to G. The only result that exists for this problem
    is for a single pair of vertices (Picard and Queyranne, Mathematical Programming
    Study, 13 (1980), 8-16). We present the following results for the single source
    and the all-pairs versions of this problem. \r\n1) Single source: Given any designated
    source vertex s, there exists a data structure of size \U0001D4AA(|S|) that can
    output all those vertices from S whose mincut value to s increases upon insertion
    of any given edge. The time taken by the data structure to answer any query is
    \U0001D4AA(|S|). \r\n2) All-pairs: There exists an \U0001D4AA(|S|²) size data
    structure that can output all those pairs of vertices from S× S whose mincut value
    gets increased upon insertion of any given edge. The time taken by the data structure
    to answer any query is \U0001D4AA(k), where k is the number of pairs of vertices
    whose mincut increases. \r\nFor both these versions, we also address the problem
    of reporting the values of the mincuts upon insertion of any given edge. To derive
    our results, we use interesting insights into the nearest and the farthest mincuts
    for a pair of vertices. In addition, a crucial result, that we establish and use
    in our data structures, is that there exists a directed acyclic graph of \U0001D4AA(n)
    size that compactly stores the farthest mincuts from all vertices of V to a designated
    vertex s in the graph. We believe that this result is of independent interest,
    especially, because it also complements a previously existing result by Hariharan
    et al. (STOC 2007) that the nearest mincuts from all vertices of V to s is a laminar
    family, and hence, can be stored compactly in a tree of \U0001D4AA(n) size."
author:
- first_name: Surender
  full_name: Baswana, Surender
  last_name: Baswana
- first_name: Shiv
  full_name: Gupta, Shiv
  last_name: Gupta
- first_name: Till
  full_name: Knollmann, Till
  id: '39241'
  last_name: Knollmann
  orcid: 0000-0003-2014-4696
citation:
  ama: 'Baswana S, Gupta S, Knollmann T. Mincut Sensitivity Data Structures for the
    Insertion of an Edge. In: Grandoni F, Herman G, Sanders P, eds. <i>28th Annual
    European Symposium on Algorithms (ESA 2020)</i>. Vol 173. Leibniz International
    Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum
    für Informatik; 2020:12:1-12:14. doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2020.12">10.4230/LIPIcs.ESA.2020.12</a>'
  apa: 'Baswana, S., Gupta, S., &#38; Knollmann, T. (2020). Mincut Sensitivity Data
    Structures for the Insertion of an Edge. In F. Grandoni, G. Herman, &#38; P. Sanders
    (Eds.), <i>28th Annual European Symposium on Algorithms (ESA 2020)</i> (Vol. 173,
    pp. 12:1-12:14). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.ESA.2020.12">https://doi.org/10.4230/LIPIcs.ESA.2020.12</a>'
  bibtex: '@inproceedings{Baswana_Gupta_Knollmann_2020, place={Dagstuhl, Germany},
    series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Mincut
    Sensitivity Data Structures for the Insertion of an Edge}, volume={173}, DOI={<a
    href="https://doi.org/10.4230/LIPIcs.ESA.2020.12">10.4230/LIPIcs.ESA.2020.12</a>},
    booktitle={28th Annual European Symposium on Algorithms (ESA 2020)}, publisher={Schloss
    Dagstuhl -- Leibniz-Zentrum für Informatik}, author={Baswana, Surender and Gupta,
    Shiv and Knollmann, Till}, editor={Grandoni, Fabrizio and Herman, Grzegorz and
    Sanders, PeterEditors}, year={2020}, pages={12:1-12:14}, collection={Leibniz International
    Proceedings in Informatics (LIPIcs)} }'
  chicago: 'Baswana, Surender, Shiv Gupta, and Till Knollmann. “Mincut Sensitivity
    Data Structures for the Insertion of an Edge.” In <i>28th Annual European Symposium
    on Algorithms (ESA 2020)</i>, edited by Fabrizio Grandoni, Grzegorz Herman, and
    Peter Sanders, 173:12:1-12:14. Leibniz International Proceedings in Informatics
    (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik,
    2020. <a href="https://doi.org/10.4230/LIPIcs.ESA.2020.12">https://doi.org/10.4230/LIPIcs.ESA.2020.12</a>.'
  ieee: S. Baswana, S. Gupta, and T. Knollmann, “Mincut Sensitivity Data Structures
    for the Insertion of an Edge,” in <i>28th Annual European Symposium on Algorithms
    (ESA 2020)</i>, 2020, vol. 173, pp. 12:1-12:14.
  mla: Baswana, Surender, et al. “Mincut Sensitivity Data Structures for the Insertion
    of an Edge.” <i>28th Annual European Symposium on Algorithms (ESA 2020)</i>, edited
    by Fabrizio Grandoni et al., vol. 173, Schloss Dagstuhl -- Leibniz-Zentrum für
    Informatik, 2020, pp. 12:1-12:14, doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2020.12">10.4230/LIPIcs.ESA.2020.12</a>.
  short: 'S. Baswana, S. Gupta, T. Knollmann, in: F. Grandoni, G. Herman, P. Sanders
    (Eds.), 28th Annual European Symposium on Algorithms (ESA 2020), Schloss Dagstuhl
    -- Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2020, pp. 12:1-12:14.'
date_created: 2020-10-21T12:00:20Z
date_updated: 2022-01-06T06:54:20Z
department:
- _id: '63'
doi: 10.4230/LIPIcs.ESA.2020.12
editor:
- first_name: Fabrizio
  full_name: Grandoni, Fabrizio
  last_name: Grandoni
- first_name: Grzegorz
  full_name: Herman, Grzegorz
  last_name: Herman
- first_name: Peter
  full_name: Sanders, Peter
  last_name: Sanders
intvolume: '       173'
keyword:
- Mincut
- Sensitivity
- Data Structure
language:
- iso: eng
page: 12:1-12:14
place: Dagstuhl, Germany
publication: 28th Annual European Symposium on Algorithms (ESA 2020)
publication_identifier:
  isbn:
  - 978-3-95977-162-7
  issn:
  - 1868-8969
publisher: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Mincut Sensitivity Data Structures for the Insertion of an Edge
type: conference
user_id: '39241'
volume: 173
year: '2020'
...
---
_id: '4411'
abstract:
- lang: eng
  text: "While a lot of research in distributed computing has covered solutions for
    self-stabilizing computing and topologies, there is far less work on self-stabilization
    for distributed data structures.\r\nConsidering crashing peers in peer-to-peer
    networks, it should not be taken for granted that a distributed data structure
    remains intact.\r\nIn this work, we present a self-stabilizing protocol for a
    distributed data structure called the hashed Patricia Trie (Kniesburges and Scheideler
    WALCOM'11) that enables efficient prefix search on a set of keys.\r\nThe data
    structure has a wide area of applications including string matching problems while
    offering low overhead and efficient operations when embedded on top of a distributed
    hash table.\r\nEspecially, longest prefix matching for $x$ can be done in $\\mathcal{O}(\\log
    |x|)$ hash table read accesses.\r\nWe show how to maintain the structure in a
    self-stabilizing way.\r\nOur protocol assures low overhead in a legal state and
    a total (asymptotically optimal) memory demand of $\\Theta(d)$ bits, where $d$
    is the number of bits needed for storing all keys."
author:
- first_name: Till
  full_name: Knollmann, Till
  id: '39241'
  last_name: Knollmann
  orcid: 0000-0003-2014-4696
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  ama: 'Knollmann T, Scheideler C. A Self-Stabilizing Hashed Patricia Trie. In: Izumi
    T, Kuznetsov P, eds. <i>Proceedings of the 20th International Symposium on Stabilization,
    Safety, and Security of Distributed Systems (SSS)</i>. Vol 11201. Lecture Notes
    of Computer Science. Springer, Cham; 2018. doi:<a href="https://doi.org/10.1007/978-3-030-03232-6_1">10.1007/978-3-030-03232-6_1</a>'
  apa: 'Knollmann, T., &#38; Scheideler, C. (2018). A Self-Stabilizing Hashed Patricia
    Trie. In T. Izumi &#38; P. Kuznetsov (Eds.), <i>Proceedings of the 20th International
    Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>
    (Vol. 11201). Tokyo: Springer, Cham. <a href="https://doi.org/10.1007/978-3-030-03232-6_1">https://doi.org/10.1007/978-3-030-03232-6_1</a>'
  bibtex: '@inproceedings{Knollmann_Scheideler_2018, series={Lecture Notes of Computer
    Science}, title={A Self-Stabilizing Hashed Patricia Trie}, volume={11201}, DOI={<a
    href="https://doi.org/10.1007/978-3-030-03232-6_1">10.1007/978-3-030-03232-6_1</a>},
    booktitle={Proceedings of the 20th International Symposium on Stabilization, Safety,
    and Security of Distributed Systems (SSS)}, publisher={Springer, Cham}, author={Knollmann,
    Till and Scheideler, Christian}, editor={Izumi, Taisuke and Kuznetsov, PetrEditors},
    year={2018}, collection={Lecture Notes of Computer Science} }'
  chicago: Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia
    Trie.” In <i>Proceedings of the 20th International Symposium on Stabilization,
    Safety, and Security of Distributed Systems (SSS)</i>, edited by Taisuke Izumi
    and Petr Kuznetsov, Vol. 11201. Lecture Notes of Computer Science. Springer, Cham,
    2018. <a href="https://doi.org/10.1007/978-3-030-03232-6_1">https://doi.org/10.1007/978-3-030-03232-6_1</a>.
  ieee: T. Knollmann and C. Scheideler, “A Self-Stabilizing Hashed Patricia Trie,”
    in <i>Proceedings of the 20th International Symposium on Stabilization, Safety,
    and Security of Distributed Systems (SSS)</i>, Tokyo, 2018, vol. 11201.
  mla: Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia
    Trie.” <i>Proceedings of the 20th International Symposium on Stabilization, Safety,
    and Security of Distributed Systems (SSS)</i>, edited by Taisuke Izumi and Petr
    Kuznetsov, vol. 11201, Springer, Cham, 2018, doi:<a href="https://doi.org/10.1007/978-3-030-03232-6_1">10.1007/978-3-030-03232-6_1</a>.
  short: 'T. Knollmann, C. Scheideler, in: T. Izumi, P. Kuznetsov (Eds.), Proceedings
    of the 20th International Symposium on Stabilization, Safety, and Security of
    Distributed Systems (SSS), Springer, Cham, 2018.'
conference:
  end_date: 2018-11-07
  location: Tokyo
  name: 20th International Symposium on Stabilization, Safety, and Security of Distributed
    Systems (SSS)
  start_date: 2018-11-04
date_created: 2018-09-17T13:12:18Z
date_updated: 2022-01-06T07:01:02Z
ddc:
- '000'
department:
- _id: '63'
- _id: '79'
doi: 10.1007/978-3-030-03232-6_1
editor:
- first_name: Taisuke
  full_name: Izumi, Taisuke
  last_name: Izumi
- first_name: Petr
  full_name: Kuznetsov, Petr
  last_name: Kuznetsov
external_id:
  arxiv:
  - '1809.04923'
file:
- access_level: closed
  content_type: application/pdf
  creator: ups
  date_created: 2018-11-02T14:38:37Z
  date_updated: 2018-11-02T14:38:37Z
  file_id: '5277'
  file_name: ASelf-stabilizingHashedPatrici.pdf
  file_size: 500005
  relation: main_file
  success: 1
file_date_updated: 2018-11-02T14:38:37Z
has_accepted_license: '1'
intvolume: '     11201'
keyword:
- Self-Stabilizing
- Prefix Search
- Distributed Data Structure
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
publication: Proceedings of the 20th International Symposium on Stabilization, Safety,
  and Security of Distributed Systems (SSS)
publisher: Springer, Cham
series_title: Lecture Notes of Computer Science
status: public
title: A Self-Stabilizing Hashed Patricia Trie
type: conference
user_id: '39241'
volume: 11201
year: '2018'
...