---
DOAJ_listed: '1'
OA_place: publisher
OA_type: gold
_id: '22480'
abstract:
- lang: eng
text: "Background:\r\nThe spatial distribution of tree canopies influences ecological
functions and residents’ exposure to green spaces. Although several studies have
examined green space configuration at neighborhood scales, evidence on tree canopy
configuration at the municipal scale, an operational unit for urban planning,
remains limited.\r\nMethods:\r\nWe conducted a nationwide ecological study of
2,136 Swiss municipalities. Tree canopy coverage (PLAND), aggregation (AI, reflecting
how tightly green patches are grouped together), patch density (PD, a measure
of fragmentation), and area-weighted mean shape index (SHAPE_AM, a measure of
shape complexity) were derived from 1-m canopy maps within municipality-specific
populated areas. Natural-cause, cardiovascular, and cancer mortality (2017–2019)
were obtained from the Swiss National Cohort. Fully adjusted negative binomial
regression models estimated associations between canopy metric and mortality for
each IQR increase in the metrics.\r\nResults:\r\nHolding configuration constant,
each IQR increase in canopy coverage (∼18%) was associated with a 3.6% [B: −0.036;
95% CI: −0.078 – 0.005] reduction in cardiovascular mortality. Higher aggregation
corresponded to a 4.3% [B: 0.043; 95% CI: 0.026–0.061], an 8.9% [B: 0.089; 95%
CI: 0.059–0.119], and a 2.1% [B: 0.021; 95% CI: 0–0.042] higher number of natural-cause,
cardiovascular, and cancer deaths respectively. Higher fragmentation was associated
with a 3.3% [B: 0.033; 95% CI: 0.016–0.050], a 4.9% [B: 0.049; 95% CI: 0.020–0.078],
and a 2.2% [B: 0.022; 95% CI: 0.001–0.043] increase in these causes respectively.
No meaningful associations were observed between shape complexity and any mortality
outcomes. Associations for aggregation and fragmentation were generally stronger
in highly urbanized municipalities.\r\nConclusions:\r\nAt the municipal scale,
mortality was lower where tree canopy was distributed across several moderately
sized, spatially balanced patches rather than highly aggregated or highly fragmented
structures. These findings suggest that urban greening strategies should optimize
its spatial configuration to maximize health benefits."
article_number: '110188'
article_processing_charge: No
article_type: original
author:
- first_name: Dengkai
full_name: Chi, Dengkai
last_name: Chi
- first_name: Gabriele
full_name: Manoli, Gabriele
last_name: Manoli
- first_name: Jun
full_name: Yang, Jun
last_name: Yang
- first_name: Daniel
full_name: Richards, Daniel
last_name: Richards
- first_name: Amy
full_name: Hahs, Amy
last_name: Hahs
- first_name: Brenda
full_name: Lin, Brenda
last_name: Lin
- first_name: Mark J.
full_name: McDonnell, Mark J.
last_name: McDonnell
- first_name: Ye
full_name: Zhang, Ye
last_name: Zhang
- first_name: Yue
full_name: Zhu, Yue
last_name: Zhu
- first_name: Yeshan
full_name: Qiu, Yeshan
last_name: Qiu
- first_name: Jing
full_name: Wang, Jing
last_name: Wang
- first_name: Xing
full_name: Zheng, Xing
last_name: Zheng
- first_name: Paolo
full_name: Burlando, Paolo
last_name: Burlando
- first_name: Simone
full_name: Fatichi, Simone
id: cf8e546b-a9b0-11f0-a43b-aa89ed1b56d6
last_name: Fatichi
- first_name: Puay Yok
full_name: Tan, Puay Yok
last_name: Tan
citation:
ama: 'Chi D, Manoli G, Yang J, et al. Tree canopy configuration and Swiss adult
mortality at the municipal level: A nationwide ecological study. Environment
International. 2026;209. doi:10.1016/j.envint.2026.110188'
apa: 'Chi, D., Manoli, G., Yang, J., Richards, D., Hahs, A., Lin, B., … Tan, P.
Y. (2026). Tree canopy configuration and Swiss adult mortality at the municipal
level: A nationwide ecological study. Environment International. Elsevier.
https://doi.org/10.1016/j.envint.2026.110188'
chicago: 'Chi, Dengkai, Gabriele Manoli, Jun Yang, Daniel Richards, Amy Hahs, Brenda
Lin, Mark J. McDonnell, et al. “Tree Canopy Configuration and Swiss Adult Mortality
at the Municipal Level: A Nationwide Ecological Study.” Environment International.
Elsevier, 2026. https://doi.org/10.1016/j.envint.2026.110188.'
ieee: 'D. Chi et al., “Tree canopy configuration and Swiss adult mortality
at the municipal level: A nationwide ecological study,” Environment International,
vol. 209. Elsevier, 2026.'
ista: 'Chi D, Manoli G, Yang J, Richards D, Hahs A, Lin B, McDonnell MJ, Zhang Y,
Zhu Y, Qiu Y, Wang J, Zheng X, Burlando P, Fatichi S, Tan PY. 2026. Tree canopy
configuration and Swiss adult mortality at the municipal level: A nationwide ecological
study. Environment International. 209, 110188.'
mla: 'Chi, Dengkai, et al. “Tree Canopy Configuration and Swiss Adult Mortality
at the Municipal Level: A Nationwide Ecological Study.” Environment International,
vol. 209, 110188, Elsevier, 2026, doi:10.1016/j.envint.2026.110188.'
short: D. Chi, G. Manoli, J. Yang, D. Richards, A. Hahs, B. Lin, M.J. McDonnell,
Y. Zhang, Y. Zhu, Y. Qiu, J. Wang, X. Zheng, P. Burlando, S. Fatichi, P.Y. Tan,
Environment International 209 (2026).
das_tickbox: '1'
date_created: 2026-07-27T12:30:23Z
date_published: 2026-03-01T00:00:00Z
date_updated: 2026-08-03T14:17:29Z
day: '01'
ddc:
- '550'
doi: 10.1016/j.envint.2026.110188
extern: '1'
external_id:
pmid:
- '41812348'
has_accepted_license: '1'
intvolume: ' 209'
keyword:
- Aggregation
- Fragmentation
- Green space exposure
- Green space morphology
- Green space structure
- Landscape metrics
- Shape complexity
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
main_file_link:
- open_access: '1'
url: https://doi.org/10.1016/j.envint.2026.110188
month: '03'
oa: 1
oa_version: Published Version
pmid: 1
publication: Environment International
publication_identifier:
eissn:
- 1873-6750
issn:
- 0160-4120
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Tree canopy configuration and Swiss adult mortality at the municipal level:
A nationwide ecological study'
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: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 209
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22405'
abstract:
- lang: eng
text: "Computing the diameter of the intersection graphs of objects is a basic problem
in computational geometry. Previous works showed that the complexity of computing
the diameter mainly depends on the object types: for unit disks and squares in
2D, the problem is solvable in truly subquadratic time [Chan et al., 2025], while
for other objects, including unit segments and equilateral triangles in 2D or
unit balls and axis-parallel unit cubes in 3D, there is no truly subquadratic
time algorithm under the Orthogonal Vector (OV) hypothesis [Bringmann et al.,
2022]. \r\nWe undertake a comprehensive study of computing the diameter of geometric
intersection graphs for various types of objects. We discover many new irregularities,
showing that the landscape is extremely nuanced: the source of hardness is a combination
of the object type, the true diameter value, and how the objects intersect with
each other. Our highlighted results for the 2D case include: \r\n1) The diameter
of non-degenerate, axis-aligned line segments can be computed in truly subquadratic
time. Previous hardness result [Bringmann et al., 2022] for line segments applies
only to degenerate instances. On the other hand, for the degenerate case, we show
that a truly subquadratic time algorithm exists when the true diameter is constant.
\r\n2) An almost-linear-time algorithm for unit-square graphs of constant diameter.
Previous algorithms [Duraj et al., 2024; Chan et al., 2025] rely on succinct representation
assuming bounded VC-dimension; for such a strategy Ω(n^{7/4}) time is an inherent
barrier. \r\n3) An Õ(n^{4/3})-time algorithm to decide if the diameter of a unit-disk
graph is at most 2. This improves upon the recent algorithm with running time
Õ(n^{2-1/9}) [Chan et al., 2025]. \r\n4) Deciding if the diameter of intersection
graphs of fat triangles or line segments is at most 2 is truly subquadratic-hard
under fine-grained complexity assumptions. Previous lower bounds [Bringmann et
al., 2022] only hold when deciding if diameter is at most 3. Our findings are
presented in a pair of papers. This paper focuses solely on the 2D case, while
the companion paper is devoted to higher-dimensional cases."
acknowledgement: "Timothy M. Chan: Supported by NSF grant CCF-2224271.\r\nHsien-Chih
Chang: Supported by NSF CAREER award CCF-2443017.\r\nJie Gao: Supported by NSF DMS-2220271,
DMS-2311064, IIS-2229876, CCF-2118953, CNS-2515159.\r\nSándor Kisfaludi-Bak: Supported
by the Research Council of Finland, Grant 363444.\r\nHung Le: Supported by an NSF
grant CCF-2517033 and an NSF CAREER Award CCF-2237288.\r\nDa Wei Zheng: This project
has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982.
For open access purposes, the author has applied a CC BY public copyright\r\nlicense
to any author-accepted manuscript version arising from this submission.\r\n"
article_number: 54:1-54:22
article_processing_charge: No
arxiv: 1
author:
- first_name: Timothy M.
full_name: Chan, Timothy M.
last_name: Chan
orcid: 0000-0002-8093-0675
- first_name: Hsien-Chih
full_name: Chang, Hsien-Chih
last_name: Chang
orcid: 0000-0001-6714-7988
- first_name: Jie
full_name: Gao, Jie
last_name: Gao
orcid: 0000-0001-5083-6082
- first_name: Sándor
full_name: Kisfaludi-Bak, Sándor
last_name: Kisfaludi-Bak
orcid: 0000-0002-6856-2902
- first_name: Hung
full_name: Le, Hung
last_name: Le
orcid: 0000-0001-8223-9944
- first_name: Da Wei
full_name: Zheng, Da Wei
id: af77956b-e859-11ef-8dc9-d301b898e32f
last_name: Zheng
citation:
ama: 'Chan TM, Chang H-C, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the landscape
of diameter computation on geometric intersection graphs in the plane. In: 53rd
International Colloquium on Automata, Languages, and Programming. Vol 374.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPICS.ICALP.2026.54'
apa: 'Chan, T. M., Chang, H.-C., Gao, J., Kisfaludi-Bak, S., Le, H., & Zheng,
D. W. (2026). Charting the landscape of diameter computation on geometric intersection
graphs in the plane. In 53rd International Colloquium on Automata, Languages,
and Programming (Vol. 374). Egham, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2026.54'
chicago: Chan, Timothy M., Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung
Le, and Da Wei Zheng. “Charting the Landscape of Diameter Computation on Geometric
Intersection Graphs in the Plane.” In 53rd International Colloquium on Automata,
Languages, and Programming, Vol. 374. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2026. https://doi.org/10.4230/LIPICS.ICALP.2026.54.
ieee: T. M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng,
“Charting the landscape of diameter computation on geometric intersection graphs
in the plane,” in 53rd International Colloquium on Automata, Languages, and
Programming, Egham, United Kingdom, 2026, vol. 374.
ista: 'Chan TM, Chang H-C, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. 2026. Charting
the landscape of diameter computation on geometric intersection graphs in the
plane. 53rd International Colloquium on Automata, Languages, and Programming.
ICALP: Automata, Languages and Programming vol. 374, 54:1-54:22.'
mla: Chan, Timothy M., et al. “Charting the Landscape of Diameter Computation on
Geometric Intersection Graphs in the Plane.” 53rd International Colloquium
on Automata, Languages, and Programming, vol. 374, 54:1-54:22, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPICS.ICALP.2026.54.
short: T.M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, in:,
53rd International Colloquium on Automata, Languages, and Programming, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
conference:
end_date: 2026-07-10
location: Egham, United Kingdom
name: 'ICALP: Automata, Languages and Programming'
start_date: 2026-07-07
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-27T05:53:08Z
date_published: 2026-07-01T00:00:00Z
date_updated: 2026-08-12T09:03:26Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPICS.ICALP.2026.54
external_id:
arxiv:
- '2605.10692'
file:
- access_level: open_access
checksum: 1e66eba4cfe4e74ab28108b1ca0bb956
content_type: application/pdf
creator: dernst
date_created: 2026-07-27T06:20:41Z
date_updated: 2026-07-27T06:20:41Z
file_id: '22407'
file_name: 2026_LIPIcSICALP_Chan.pdf
file_size: 1440497
relation: main_file
success: 1
file_date_updated: 2026-07-27T06:20:41Z
has_accepted_license: '1'
intvolume: ' 374'
keyword:
- String graphs
- Fine-grained complexity
- Theory of computation → Computational geometry
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: 53rd International Colloquium on Automata, Languages, and Programming
publication_identifier:
eissn:
- 1868-8969
- '9783959774284'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Charting the landscape of diameter computation on geometric intersection graphs
in the plane
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 374
year: '2026'
...
---
OA_place: publisher
OA_type: hybrid
_id: '10045'
abstract:
- lang: eng
text: "Given a fixed finite metric space (V,μ), the {\\em minimum 0-extension problem},
denoted as 0-Ext[μ], is equivalent to the following optimization problem: minimize
function of the form minx∈Vn∑ifi(xi)+∑ijcijμ(xi,xj) where cij,cvi are given nonnegative
costs and fi:V→R are functions given by fi(xi)=∑v∈Vcviμ(xi,v). The computational
complexity of 0-Ext[μ] has been recently established by Karzanov and by Hirai:
if metric μ is {\\em orientable modular} then 0-Ext[μ] can be solved in polynomial
time, otherwise 0-Ext[μ] is NP-hard. To prove the tractability part, Hirai developed
a theory of discrete convex functions on orientable modular graphs generalizing
several known classes of functions in discrete convex analysis, such as L♮-convex
functions. We consider a more general version of the problem in which unary functions
fi(xi) can additionally have terms of the form cuv;iμ(xi,{u,v}) for {u,v}∈F, where
set F⊆(V2) is fixed. We extend the complexity classification above by providing
an explicit condition on (μ,F) for the problem to be tractable. In order to prove
the tractability part, we generalize Hirai's theory and define a larger class
of discrete convex functions. It covers, in particular, another well-known class
of functions, namely submodular functions on an integer lattice. Finally, we improve
the complexity of Hirai's algorithm for solving 0-Ext on orientable modular graphs.\r\n"
acknowledgement: We thank the anonymous reviewers for their careful reading of our
manuscript and their many insightful comments and suggestions. Open access funding
provided by Institute of Science and Technology (IST Austria).
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Martin
full_name: Dvorak, Martin
id: 40ED02A8-C8B4-11E9-A9C0-453BE6697425
last_name: Dvorak
orcid: 0000-0001-5293-214X
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete
convexity. Mathematical Programming. 2025;209:279-322. doi:10.1007/s10107-024-02064-5
apa: Dvorak, M., & Kolmogorov, V. (2025). Generalized minimum 0-extension problem
and discrete convexity. Mathematical Programming. Springer Nature. https://doi.org/10.1007/s10107-024-02064-5
chicago: Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension
Problem and Discrete Convexity.” Mathematical Programming. Springer Nature,
2025. https://doi.org/10.1007/s10107-024-02064-5.
ieee: M. Dvorak and V. Kolmogorov, “Generalized minimum 0-extension problem and
discrete convexity,” Mathematical Programming, vol. 209. Springer Nature,
pp. 279–322, 2025.
ista: Dvorak M, Kolmogorov V. 2025. Generalized minimum 0-extension problem and
discrete convexity. Mathematical Programming. 209, 279–322.
mla: Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem
and Discrete Convexity.” Mathematical Programming, vol. 209, Springer Nature,
2025, pp. 279–322, doi:10.1007/s10107-024-02064-5.
short: M. Dvorak, V. Kolmogorov, Mathematical Programming 209 (2025) 279–322.
corr_author: '1'
date_created: 2021-09-27T10:48:23Z
date_published: 2025-01-01T00:00:00Z
date_updated: 2025-05-19T13:52:10Z
day: '01'
ddc:
- '004'
department:
- _id: GradSch
- _id: VlKo
doi: 10.1007/s10107-024-02064-5
external_id:
arxiv:
- '2109.10203'
isi:
- '001176563300001'
file:
- access_level: open_access
checksum: 25d9bd490719b45eca84f4d93a06c69f
content_type: application/pdf
creator: dernst
date_created: 2025-04-16T09:36:08Z
date_updated: 2025-04-16T09:36:08Z
file_id: '19578'
file_name: 2025_MathProgramming_Dvorak.pdf
file_size: 839510
relation: main_file
success: 1
file_date_updated: 2025-04-16T09:36:08Z
has_accepted_license: '1'
intvolume: ' 209'
isi: 1
keyword:
- minimum 0-extension problem
- metric labeling problem
- discrete metric spaces
- metric extensions
- computational complexity
- valued constraint satisfaction problems
- discrete convex analysis
- L-convex functions
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 279-322
publication: Mathematical Programming
publication_identifier:
eissn:
- 1436-4646
issn:
- 0025-5610
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Generalized minimum 0-extension problem and discrete convexity
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: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 209
year: '2025'
...
---
_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
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'
...
---
_id: '10004'
abstract:
- lang: eng
text: 'Markov chains are the de facto finite-state model for stochastic dynamical
systems, and Markov decision processes (MDPs) extend Markov chains by incorporating
non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization
criterion is the maximal expected total reward where the MDP stops after T steps,
which can be computed by a simple dynamic programming algorithm. We consider a
natural generalization of the problem where the stopping times can be chosen according
to a probability distribution, such that the expected stopping time is T, to optimize
the expected total reward. Quite surprisingly we establish inter-reducibility
of the expected stopping-time problem for Markov chains with the Positivity problem
(which is related to the well-known Skolem problem), for which establishing either
decidability or undecidability would be a major breakthrough. Given the hardness
of the exact problem, we consider the approximate version of the problem: we show
that it can be solved in exponential time for Markov chains and in exponential
space for MDPs.'
acknowledgement: We are grateful to the anonymous reviewers of LICS 2021 and of a
previous version of this paper for insightful comments that helped improving the
presentation. This research was partially supported by the grant ERC CoG 863818
(ForM-SMArt).
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
citation:
ama: 'Chatterjee K, Doyen L. Stochastic processes with expected stopping time. In:
Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science.
IEEE; 2021:1-13. doi:10.1109/LICS52264.2021.9470595'
apa: 'Chatterjee, K., & Doyen, L. (2021). Stochastic processes with expected
stopping time. In Proceedings of the 36th Annual ACM/IEEE Symposium on Logic
in Computer Science (pp. 1–13). Rome, Italy: IEEE. https://doi.org/10.1109/LICS52264.2021.9470595'
chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected
Stopping Time.” In Proceedings of the 36th Annual ACM/IEEE Symposium on Logic
in Computer Science, 1–13. IEEE, 2021. https://doi.org/10.1109/LICS52264.2021.9470595.
ieee: K. Chatterjee and L. Doyen, “Stochastic processes with expected stopping time,”
in Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science,
Rome, Italy, 2021, pp. 1–13.
ista: 'Chatterjee K, Doyen L. 2021. Stochastic processes with expected stopping
time. Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science.
LICS: Logic in Computer Science, 1–13.'
mla: Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected
Stopping Time.” Proceedings of the 36th Annual ACM/IEEE Symposium on Logic
in Computer Science, IEEE, 2021, pp. 1–13, doi:10.1109/LICS52264.2021.9470595.
short: K. Chatterjee, L. Doyen, in:, Proceedings of the 36th Annual ACM/IEEE Symposium
on Logic in Computer Science, IEEE, 2021, pp. 1–13.
conference:
end_date: 2021-07-02
location: Rome, Italy
name: 'LICS: Logic in Computer Science'
start_date: 2021-06-29
date_created: 2021-09-12T22:01:25Z
date_published: 2021-07-07T00:00:00Z
date_updated: 2026-08-12T06:39:27Z
day: '07'
department:
- _id: KrCh
doi: 10.1109/LICS52264.2021.9470595
ec_funded: 1
external_id:
arxiv:
- '2104.07278'
isi:
- '000947350400036'
isi: 1
keyword:
- Computer science
- Heuristic algorithms
- Memory management
- Automata
- Markov processes
- Probability distribution
- Complexity theory
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2104.07278
month: '07'
oa: 1
oa_version: Preprint
page: 1-13
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer
Science
publication_identifier:
eisbn:
- 978-1-6654-4895-6
isbn:
- 978-1-6654-4896-3
issn:
- 1043-6871
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '18630'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Stochastic processes with expected stopping time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '4317'
article_processing_charge: No
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: 'Barton NH. Speciation. In: Myers A, Giller P, eds. Analytical Biogeography:
An Integrated Approach to the Study of Animal and Plant Distributions. 1st
ed. Springer; 1988:185-218. doi:10.1007/978-94-009-0435-4'
apa: 'Barton, N. H. (1988). Speciation. In A. Myers & P. Giller (Eds.), Analytical
biogeography: An integrated approach to the study of animal and plant distributions
(1st ed., pp. 185–218). Springer. https://doi.org/10.1007/978-94-009-0435-4'
chicago: 'Barton, Nicholas H. “Speciation.” In Analytical Biogeography: An Integrated
Approach to the Study of Animal and Plant Distributions, edited by Alan Myers
and Paul Giller, 1st ed., 185–218. Springer, 1988. https://doi.org/10.1007/978-94-009-0435-4.'
ieee: 'N. H. Barton, “Speciation,” in Analytical biogeography: An integrated
approach to the study of animal and plant distributions, 1st ed., A. Myers
and P. Giller, Eds. Springer, 1988, pp. 185–218.'
ista: 'Barton NH. 1988.Speciation. In: Analytical biogeography: An integrated approach
to the study of animal and plant distributions. , 185–218.'
mla: 'Barton, Nicholas H. “Speciation.” Analytical Biogeography: An Integrated
Approach to the Study of Animal and Plant Distributions, edited by Alan Myers
and Paul Giller, 1st ed., Springer, 1988, pp. 185–218, doi:10.1007/978-94-009-0435-4.'
short: 'N.H. Barton, in:, A. Myers, P. Giller (Eds.), Analytical Biogeography: An
Integrated Approach to the Study of Animal and Plant Distributions, 1st ed., Springer,
1988, pp. 185–218.'
date_created: 2018-12-11T12:08:13Z
date_published: 1988-01-01T00:00:00Z
date_updated: 2022-02-08T09:19:50Z
day: '01'
doi: 10.1007/978-94-009-0435-4
edition: '1'
editor:
- first_name: Alan
full_name: Myers, Alan
last_name: Myers
- first_name: Paul
full_name: Giller, Paul
last_name: Giller
extern: '1'
keyword:
- biogeography
- biology
- complexity
- distribution
- evolution
- geology
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/book/10.1007/978-94-009-0435-4#toc
month: '01'
oa_version: None
page: 185 - 218
publication: 'Analytical biogeography: An integrated approach to the study of animal
and plant distributions'
publication_identifier:
eissn:
- 978-94-009-0435-4
isbn:
- 978-0-412-40050-6
publication_status: published
publisher: Springer
publist_id: '1736'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Speciation
type: book_chapter
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1988'
...