---
res:
bibo_abstract:
- "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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Surender
foaf_name: Baswana, Surender
foaf_surname: Baswana
- foaf_Person:
foaf_givenName: Shiv
foaf_name: Gupta, Shiv
foaf_surname: Gupta
- foaf_Person:
foaf_givenName: Till
foaf_name: Knollmann, Till
foaf_surname: Knollmann
foaf_workInfoHomepage: http://www.librecat.org/personId=39241
orcid: 0000-0003-2014-4696
bibo_doi: 10.4230/LIPIcs.ESA.2020.12
bibo_volume: 173
dct_date: 2020^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/1868-8969
- http://id.crossref.org/issn/978-3-95977-162-7
dct_language: eng
dct_publisher: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik@
dct_subject:
- Mincut
- Sensitivity
- Data Structure
dct_title: Mincut Sensitivity Data Structures for the Insertion of an Edge@
...