---
_id: '22373'
abstract:
- lang: eng
text: "Data dissemination is a fundamental task in distributed computing. This paper
studies broadcast problems in various innovative models where the communication
network connecting n processes is dynamic (e.g., due to mobility or failures)
and controlled by an adversary. \r\nIn the first model, the processes transitively
communicate their ids in synchronous rounds along a rooted tree given in each
round by the adversary whose goal is to maximize the number of rounds until at
least one id is known by all processes. Previous research has shown a ⌈(3n-1)/2⌉-2
lower bound and an O(nlog log n) upper bound. We show the first linear upper bound
for this problem, namely ⌈(1+√2) n-1⌉ ≈ 2.4n.\r\nWe extend these results to the
setting where the adversary gives in each round k-disjoint forests and their goal
is to maximize the number of rounds until there is a set of k ids such that each
process knows of at least one of them. We give a ⌈3(n-k)/2⌉-1 lower bound and
a (π²+6)/6 n+1 ≈ 2.6n upper bound for this problem.\r\nFinally, we study the setting
where the adversary gives in each round a directed graph with k roots and their
goal is to maximize the number of rounds until there exist k ids that are known
by all processes. We give a ⌈3(n-3k)/2⌉+2 lower bound and a ⌈(1+√2)n⌉+k-1 ≈ 2.4n+k
upper bound for this problem.\r\nFor the two latter problems no upper or lower
bounds were previously known."
acknowledgement: " This project has received funding from the European Research Council
(ERC) under\r\nthe European Union’s Horizon 2020 research and innovation programme
(grant agreement No.\r\n101019564). This work was further supported by the Austrian
Science Fund (FWF) and netIDEE\r\nSCIENCE project P 33775-N, as well as the FWF
project I 4800-N (ADVISE)"
alternative_title:
- LIPIcs
article_number: '47'
article_processing_charge: No
arxiv: 1
author:
- first_name: Antoine
full_name: El-Hayek, Antoine
id: 888a098e-fcac-11ee-aff7-d347be57b725
last_name: El-Hayek
orcid: 0000-0003-4268-7368
- 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: Stefan
full_name: Schmid, Stefan
last_name: Schmid
orcid: 0000-0002-7798-1711
citation:
ama: 'El-Hayek A, Henzinger M, Schmid S. Asymptotically tight bounds on the time
complexity of broadcast and its variants in dynamic networks. In: Tauman Kalai
Y, ed. 14th Innovations in Theoretical Computer Science Conference. Vol
251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPICS.ITCS.2023.47'
apa: 'El-Hayek, A., Henzinger, M., & Schmid, S. (2023). Asymptotically tight
bounds on the time complexity of broadcast and its variants in dynamic networks.
In Y. Tauman Kalai (Ed.), 14th Innovations in Theoretical Computer Science
Conference (Vol. 251). Cambridge, Massachusetts, USA: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2023.47'
chicago: El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Asymptotically
Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks.”
In 14th Innovations in Theoretical Computer Science Conference, edited
by Yael Tauman Kalai, Vol. 251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023. https://doi.org/10.4230/LIPICS.ITCS.2023.47.
ieee: A. El-Hayek, M. Henzinger, and S. Schmid, “Asymptotically tight bounds on
the time complexity of broadcast and its variants in dynamic networks,” in 14th
Innovations in Theoretical Computer Science Conference, Cambridge, Massachusetts,
USA, 2023, vol. 251.
ista: 'El-Hayek A, Henzinger M, Schmid S. 2023. Asymptotically tight bounds on the
time complexity of broadcast and its variants in dynamic networks. 14th Innovations
in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer
Science, LIPIcs, vol. 251, 47.'
mla: El-Hayek, Antoine, et al. “Asymptotically Tight Bounds on the Time Complexity
of Broadcast and Its Variants in Dynamic Networks.” 14th Innovations in Theoretical
Computer Science Conference, edited by Yael Tauman Kalai, vol. 251, 47, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPICS.ITCS.2023.47.
short: A. El-Hayek, M. Henzinger, S. Schmid, in:, Y. Tauman Kalai (Ed.), 14th Innovations
in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023.
conference:
end_date: 2023-01-13
location: Cambridge, Massachusetts, USA
name: 'ITCS: Innovations in Theoretical Computer Science'
start_date: 2023-01-10
date_created: 2026-07-20T11:45:04Z
date_published: 2023-02-01T00:00:00Z
date_updated: 2026-07-24T12:48:29Z
day: '01'
ddc:
- '000'
doi: 10.4230/LIPICS.ITCS.2023.47
editor:
- first_name: Yael
full_name: Tauman Kalai, Yael
last_name: Tauman Kalai
extern: '1'
external_id:
arxiv:
- '2211.10151'
file:
- access_level: open_access
checksum: d7f45fdcbc5fccd61db69f56d775c636
content_type: application/pdf
creator: cchlebak
date_created: 2026-07-22T08:04:03Z
date_updated: 2026-07-22T08:04:03Z
file_id: '22383'
file_name: 2023_LIPIcs_El-Hayek.pdf
file_size: 1077427
relation: main_file
success: 1
file_date_updated: 2026-07-22T08:04:03Z
fulldoi: https://doi.org/10.4230/LIPICS.ITCS.2023.47
has_accepted_license: '1'
intvolume: ' 251'
keyword:
- broadcast
- cover
- k-broadcast
- dynamic radius
- dynamic graphs
- oblivious message adversary
- time complexity
- Theory of computation → Distributed algorithms
- Networks → Network algorithms
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
publication: 14th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- '9783959772631'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '22281'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Asymptotically tight bounds on the time complexity of broadcast and its variants
in dynamic networks
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 251
year: '2023'
...
---
OA_type: closed access
_id: '22534'
abstract:
- lang: eng
text: Tree planting is a prevalent strategy to mitigate urban heat. Tree cooling
efficiency(TCE), defined as the temperature reduction for a 1% tree cover increase,
plays animportant role in urban climate as it regulates the capacity of trees
to alter the sur-face energy and water budget. However, the spatial variation
and more importantly,temporal heterogeneity of TCE in global cities are not fully
explored. Here, we usedLandsat-based tree cover and land surface temperature (LST)
to compare TCEs at areference air temperature and tree cover level across 806
global cities and to exploretheir potential drivers with a boosted regression
tree (BRT) machine learning model.From the results, we found that TCE is spatially
regulated by not only leaf area index(LAI) but climate variables and anthropogenic
factors especially city albedo, withouta specific variable dominating the others.
However, such spatial difference is attenu-ated by the decrease of TCE with tree
cover, most pronounced in midlatitude cities.During the period 2000–2015, more
than 90% of analyzed cities showed an increas-ing trend in TCE, which is likely
explained by a combined result of the increase in LAI,intensified solar radiation
due to decreased aerosol content, increase in urban vaporpressure deficit (VPD)
and decrease of city albedo. Concurrently, significant urbanafforestation occurred
across many cities showing a global city-scale mean tree coverincrease of 5.3
± 3.8% from 2000 to 2015. Over the growing season, such increasescombined with
an increasing TCE were estimated to on average yield a midday sur-face cooling
of 1.5 ± 1.3°C in tree-covered urban areas. These results are offeringnew insights
into the use of urban afforestation as an adaptation to global warmingand urban
planners may leverage them to provide more cooling benefits if trees areprimarily
planted for this purpose.
article_processing_charge: No
article_type: original
author:
- first_name: Jiacheng
full_name: Zhao, Jiacheng
last_name: Zhao
- first_name: Xiang
full_name: Zhao, Xiang
last_name: Zhao
- first_name: Donghai
full_name: Wu, Donghai
last_name: Wu
- first_name: Naika
full_name: Meili, Naika
last_name: Meili
- first_name: Simone
full_name: Fatichi, Simone
id: cf8e546b-a9b0-11f0-a43b-aa89ed1b56d6
last_name: Fatichi
citation:
ama: Zhao J, Zhao X, Wu D, Meili N, Fatichi S. Satellite‐based evidence highlights
a considerable increase of urban tree cooling benefits from 2000 to 2015. Global
Change Biology. 2023;29(11):3085-3097. doi:10.1111/gcb.16667
apa: Zhao, J., Zhao, X., Wu, D., Meili, N., & Fatichi, S. (2023). Satellite‐based
evidence highlights a considerable increase of urban tree cooling benefits from
2000 to 2015. Global Change Biology. Wiley. https://doi.org/10.1111/gcb.16667
chicago: Zhao, Jiacheng, Xiang Zhao, Donghai Wu, Naika Meili, and Simone Fatichi.
“Satellite‐based Evidence Highlights a Considerable Increase of Urban Tree Cooling
Benefits from 2000 to 2015.” Global Change Biology. Wiley, 2023. https://doi.org/10.1111/gcb.16667.
ieee: J. Zhao, X. Zhao, D. Wu, N. Meili, and S. Fatichi, “Satellite‐based evidence
highlights a considerable increase of urban tree cooling benefits from 2000 to
2015,” Global Change Biology, vol. 29, no. 11. Wiley, pp. 3085–3097, 2023.
ista: Zhao J, Zhao X, Wu D, Meili N, Fatichi S. 2023. Satellite‐based evidence highlights
a considerable increase of urban tree cooling benefits from 2000 to 2015. Global
Change Biology. 29(11), 3085–3097.
mla: Zhao, Jiacheng, et al. “Satellite‐based Evidence Highlights a Considerable
Increase of Urban Tree Cooling Benefits from 2000 to 2015.” Global Change Biology,
vol. 29, no. 11, Wiley, 2023, pp. 3085–97, doi:10.1111/gcb.16667.
short: J. Zhao, X. Zhao, D. Wu, N. Meili, S. Fatichi, Global Change Biology 29 (2023)
3085–3097.
das_tickbox: '1'
date_created: 2026-07-27T12:30:24Z
date_published: 2023-06-01T00:00:00Z
date_updated: 2026-08-12T08:28:41Z
day: '01'
doi: 10.1111/gcb.16667
extern: '1'
external_id:
pmid:
- '36876991 '
fulldoi: https://doi.org/10.1111/gcb.16667
intvolume: ' 29'
issue: '11'
keyword:
- Climate change
- Remote sensing
- Tree cooling efficiency
- Tree cover
- Urban afforestation
language:
- iso: eng
month: '06'
oa_version: None
page: 3085-3097
pmid: 1
publication: Global Change Biology
publication_identifier:
eissn:
- 1365-2486
issn:
- 1354-1013
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Satellite‐based evidence highlights a considerable increase of urban tree cooling
benefits from 2000 to 2015
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 29
year: '2023'
...
---
_id: '11675'
abstract:
- lang: eng
text: 'We consider the problems of maintaining an approximate maximum matching and
an approximate minimum vertex cover in a dynamic graph undergoing a sequence of
edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld
(in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this
problem has received significant attention in recent years. Very recently, extending
the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations
of computer science (FOCS), 2011) , Solomon (in: Proceedings of the IEEE symposium
on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm
for this problem that has an approximation ratio of 2 and an amortized update
time of O(1) with high probability. This algorithm requires the assumption of
an oblivious adversary, meaning that the future sequence of edge insertions/deletions
in the graph cannot depend in any way on the algorithm’s past output. A natural
way to remove the assumption on oblivious adversary is to give a deterministic
dynamic algorithm for the same problem in O(1) update time. In this paper, we
resolve this question. We present a new deterministic fully dynamic algorithm
that maintains a O(1)-approximate minimum vertex cover and maximum fractional
matching, with an amortized update time of O(1). Previously, the best deterministic
algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of
the ACM-SIAM symposium on discrete algorithms (SODA), 2015); it had an approximation
ratio of (2+ε) and an amortized update time of O(logn/ε2). Our result can be generalized
to give a fully dynamic O(f3)-approximate algorithm with O(f2) amortized update
time for the hypergraph vertex cover and fractional hypergraph matching problem,
where every hyperedge has at most f vertices.'
article_processing_charge: No
article_type: original
author:
- first_name: Sayan
full_name: Bhattacharya, Sayan
last_name: Bhattacharya
- first_name: Deeparnab
full_name: Chakrabarty, Deeparnab
last_name: Chakrabarty
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: Bhattacharya S, Chakrabarty D, Henzinger M. Deterministic dynamic matching
in O(1) update time. Algorithmica. 2020;82(4):1057-1080. doi:10.1007/s00453-019-00630-4
apa: Bhattacharya, S., Chakrabarty, D., & Henzinger, M. (2020). Deterministic
dynamic matching in O(1) update time. Algorithmica. Springer Nature. https://doi.org/10.1007/s00453-019-00630-4
chicago: Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika Henzinger. “Deterministic
Dynamic Matching in O(1) Update Time.” Algorithmica. Springer Nature, 2020.
https://doi.org/10.1007/s00453-019-00630-4.
ieee: S. Bhattacharya, D. Chakrabarty, and M. Henzinger, “Deterministic dynamic
matching in O(1) update time,” Algorithmica, vol. 82, no. 4. Springer Nature,
pp. 1057–1080, 2020.
ista: Bhattacharya S, Chakrabarty D, Henzinger M. 2020. Deterministic dynamic matching
in O(1) update time. Algorithmica. 82(4), 1057–1080.
mla: Bhattacharya, Sayan, et al. “Deterministic Dynamic Matching in O(1) Update
Time.” Algorithmica, vol. 82, no. 4, Springer Nature, 2020, pp. 1057–80,
doi:10.1007/s00453-019-00630-4.
short: S. Bhattacharya, D. Chakrabarty, M. Henzinger, Algorithmica 82 (2020) 1057–1080.
date_created: 2022-07-27T14:31:06Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2024-11-06T12:07:43Z
day: '01'
doi: 10.1007/s00453-019-00630-4
extern: '1'
fulldoi: https://doi.org/10.1007/s00453-019-00630-4
intvolume: ' 82'
issue: '4'
keyword:
- Dynamic algorithms
- Data structures
- Graph algorithms
- Matching
- Vertex cover
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/s00453-019-00630-4
month: '04'
oa: 1
oa_version: Published Version
page: 1057-1080
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deterministic dynamic matching in O(1) update time
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 82
year: '2020'
...