[{"abstract":[{"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.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"original","date_created":"2026-07-27T12:30:23Z","external_id":{"pmid":["41812348"]},"ddc":["550"],"day":"01","publication_identifier":{"issn":["0160-4120"],"eissn":["1873-6750"]},"oa_version":"Published Version","scopus_import":"1","license":"https://creativecommons.org/licenses/by/4.0/","_id":"22480","date_updated":"2026-08-03T14:17:29Z","DOAJ_listed":"1","oa":1,"date_published":"2026-03-01T00:00:00Z","pmid":1,"OA_place":"publisher","type":"journal_article","publication_status":"published","article_number":"110188","publication":"Environment International","intvolume":"       209","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. <i>Environment International</i>. 2026;209. doi:<a href=\"https://doi.org/10.1016/j.envint.2026.110188\">10.1016/j.envint.2026.110188</a>","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).","mla":"Chi, Dengkai, et al. “Tree Canopy Configuration and Swiss Adult Mortality at the Municipal Level: A Nationwide Ecological Study.” <i>Environment International</i>, vol. 209, 110188, Elsevier, 2026, doi:<a href=\"https://doi.org/10.1016/j.envint.2026.110188\">10.1016/j.envint.2026.110188</a>.","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.” <i>Environment International</i>. Elsevier, 2026. <a href=\"https://doi.org/10.1016/j.envint.2026.110188\">https://doi.org/10.1016/j.envint.2026.110188</a>.","ieee":"D. Chi <i>et al.</i>, “Tree canopy configuration and Swiss adult mortality at the municipal level: A nationwide ecological study,” <i>Environment International</i>, 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.","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. <i>Environment International</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.envint.2026.110188\">https://doi.org/10.1016/j.envint.2026.110188</a>"},"tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"quality_controlled":"1","doi":"10.1016/j.envint.2026.110188","main_file_link":[{"url":"https://doi.org/10.1016/j.envint.2026.110188","open_access":"1"}],"status":"public","month":"03","keyword":["Aggregation","Fragmentation","Green space exposure","Green space morphology","Green space structure","Landscape metrics","Shape complexity"],"has_accepted_license":"1","language":[{"iso":"eng"}],"title":"Tree canopy configuration and Swiss adult mortality at the municipal level: A nationwide ecological study","das_tickbox":"1","extern":"1","publisher":"Elsevier","year":"2026","volume":209,"OA_type":"gold","article_processing_charge":"No","author":[{"last_name":"Chi","full_name":"Chi, Dengkai","first_name":"Dengkai"},{"full_name":"Manoli, Gabriele","first_name":"Gabriele","last_name":"Manoli"},{"first_name":"Jun","full_name":"Yang, Jun","last_name":"Yang"},{"last_name":"Richards","first_name":"Daniel","full_name":"Richards, Daniel"},{"full_name":"Hahs, Amy","first_name":"Amy","last_name":"Hahs"},{"last_name":"Lin","full_name":"Lin, Brenda","first_name":"Brenda"},{"last_name":"McDonnell","first_name":"Mark J.","full_name":"McDonnell, Mark J."},{"full_name":"Zhang, Ye","first_name":"Ye","last_name":"Zhang"},{"last_name":"Zhu","first_name":"Yue","full_name":"Zhu, Yue"},{"first_name":"Yeshan","full_name":"Qiu, Yeshan","last_name":"Qiu"},{"first_name":"Jing","full_name":"Wang, Jing","last_name":"Wang"},{"full_name":"Zheng, Xing","first_name":"Xing","last_name":"Zheng"},{"first_name":"Paolo","full_name":"Burlando, Paolo","last_name":"Burlando"},{"first_name":"Simone","id":"cf8e546b-a9b0-11f0-a43b-aa89ed1b56d6","full_name":"Fatichi, Simone","last_name":"Fatichi"},{"last_name":"Tan","full_name":"Tan, Puay Yok","first_name":"Puay Yok"}]},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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."}],"supplementarymaterial":"no","ddc":["000"],"external_id":{"arxiv":["2605.10692"]},"date_created":"2026-07-27T05:53:08Z","day":"01","publication_identifier":{"eissn":["1868-8969","9783959774284"]},"arxiv":1,"oa_version":"Published Version","scopus_import":"1","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","_id":"22405","file_date_updated":"2026-07-27T06:20:41Z","file":[{"file_name":"2026_LIPIcSICALP_Chan.pdf","relation":"main_file","date_created":"2026-07-27T06:20:41Z","access_level":"open_access","checksum":"1e66eba4cfe4e74ab28108b1ca0bb956","creator":"dernst","file_size":1440497,"file_id":"22407","date_updated":"2026-07-27T06:20:41Z","content_type":"application/pdf","success":1}],"date_updated":"2026-08-12T09:03:26Z","date_published":"2026-07-01T00:00:00Z","oa":1,"type":"conference","OA_place":"publisher","publication_status":"published","article_number":"54:1-54:22","publication":"53rd International Colloquium on Automata, Languages, and Programming","intvolume":"       374","citation":{"apa":"Chan, T. M., Chang, H.-C., Gao, J., Kisfaludi-Bak, S., Le, H., &#38; Zheng, D. W. (2026). Charting the landscape of diameter computation on geometric intersection graphs in the plane. In <i>53rd International Colloquium on Automata, Languages, and Programming</i> (Vol. 374). Egham, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ICALP.2026.54\">https://doi.org/10.4230/LIPICS.ICALP.2026.54</a>","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.","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 <i>53rd International Colloquium on Automata, Languages, and Programming</i>, Egham, United Kingdom, 2026, vol. 374.","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 <i>53rd International Colloquium on Automata, Languages, and Programming</i>, Vol. 374. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPICS.ICALP.2026.54\">https://doi.org/10.4230/LIPICS.ICALP.2026.54</a>.","mla":"Chan, Timothy M., et al. “Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane.” <i>53rd International Colloquium on Automata, Languages, and Programming</i>, vol. 374, 54:1-54:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPICS.ICALP.2026.54\">10.4230/LIPICS.ICALP.2026.54</a>.","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.","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: <i>53rd International Colloquium on Automata, Languages, and Programming</i>. Vol 374. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPICS.ICALP.2026.54\">10.4230/LIPICS.ICALP.2026.54</a>"},"corr_author":"1","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"conference":{"end_date":"2026-07-10","location":"Egham, United Kingdom","start_date":"2026-07-07","name":"ICALP: Automata, Languages and Programming"},"quality_controlled":"1","doi":"10.4230/LIPICS.ICALP.2026.54","department":[{"_id":"MoHe"}],"status":"public","month":"07","researchdata_availability":"no","language":[{"iso":"eng"}],"title":"Charting the landscape of diameter computation on geometric intersection graphs in the plane","has_accepted_license":"1","keyword":["String graphs","Fine-grained complexity","Theory of computation → Computational geometry"],"das_tickbox":"0","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2026","project":[{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"}],"volume":374,"OA_type":"gold","article_processing_charge":"No","author":[{"first_name":"Timothy M.","orcid":"0000-0002-8093-0675","full_name":"Chan, Timothy M.","last_name":"Chan"},{"last_name":"Chang","first_name":"Hsien-Chih","orcid":"0000-0001-6714-7988","full_name":"Chang, Hsien-Chih"},{"last_name":"Gao","first_name":"Jie","full_name":"Gao, Jie","orcid":"0000-0001-5083-6082"},{"last_name":"Kisfaludi-Bak","orcid":"0000-0002-6856-2902","full_name":"Kisfaludi-Bak, Sándor","first_name":"Sándor"},{"last_name":"Le","orcid":"0000-0001-8223-9944","full_name":"Le, Hung","first_name":"Hung"},{"last_name":"Zheng","id":"af77956b-e859-11ef-8dc9-d301b898e32f","first_name":"Da Wei","full_name":"Zheng, Da Wei"}]},{"publication":"Mathematical Programming","publication_status":"published","type":"journal_article","page":"279-322","OA_place":"publisher","date_published":"2025-01-01T00:00:00Z","oa":1,"tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"quality_controlled":"1","citation":{"ama":"Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete convexity. <i>Mathematical Programming</i>. 2025;209:279-322. doi:<a href=\"https://doi.org/10.1007/s10107-024-02064-5\">10.1007/s10107-024-02064-5</a>","short":"M. Dvorak, V. Kolmogorov, Mathematical Programming 209 (2025) 279–322.","mla":"Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem and Discrete Convexity.” <i>Mathematical Programming</i>, vol. 209, Springer Nature, 2025, pp. 279–322, doi:<a href=\"https://doi.org/10.1007/s10107-024-02064-5\">10.1007/s10107-024-02064-5</a>.","chicago":"Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem and Discrete Convexity.” <i>Mathematical Programming</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s10107-024-02064-5\">https://doi.org/10.1007/s10107-024-02064-5</a>.","apa":"Dvorak, M., &#38; Kolmogorov, V. (2025). Generalized minimum 0-extension problem and discrete convexity. <i>Mathematical Programming</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10107-024-02064-5\">https://doi.org/10.1007/s10107-024-02064-5</a>","ieee":"M. Dvorak and V. Kolmogorov, “Generalized minimum 0-extension problem and discrete convexity,” <i>Mathematical Programming</i>, 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."},"isi":1,"corr_author":"1","intvolume":"       209","oa_version":"Published Version","arxiv":1,"publication_identifier":{"issn":["0025-5610"],"eissn":["1436-4646"]},"day":"01","ddc":["004"],"external_id":{"isi":["001176563300001"],"arxiv":["2109.10203"]},"date_created":"2021-09-27T10:48:23Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"original","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"}],"file_date_updated":"2025-04-16T09:36:08Z","date_updated":"2025-05-19T13:52:10Z","file":[{"file_id":"19578","success":1,"date_updated":"2025-04-16T09:36:08Z","content_type":"application/pdf","file_size":839510,"creator":"dernst","access_level":"open_access","checksum":"25d9bd490719b45eca84f4d93a06c69f","file_name":"2025_MathProgramming_Dvorak.pdf","relation":"main_file","date_created":"2025-04-16T09:36:08Z"}],"_id":"10045","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).","scopus_import":"1","OA_type":"hybrid","author":[{"last_name":"Dvorak","id":"40ED02A8-C8B4-11E9-A9C0-453BE6697425","first_name":"Martin","full_name":"Dvorak, Martin","orcid":"0000-0001-5293-214X"},{"last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir"}],"article_processing_charge":"Yes (via OA deal)","language":[{"iso":"eng"}],"title":"Generalized minimum 0-extension problem and discrete convexity","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"],"has_accepted_license":"1","month":"01","status":"public","department":[{"_id":"GradSch"},{"_id":"VlKo"}],"doi":"10.1007/s10107-024-02064-5","volume":209,"publisher":"Springer Nature","year":"2025"},{"extern":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2023","volume":251,"doi":"10.4230/LIPICS.ITCS.2023.47","status":"public","month":"02","keyword":["broadcast","cover","k-broadcast","dynamic radius","dynamic graphs","oblivious message adversary","time complexity","Theory of computation → Distributed algorithms","Networks → Network algorithms"],"has_accepted_license":"1","title":"Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks","language":[{"iso":"eng"}],"editor":[{"full_name":"Tauman Kalai, Yael","first_name":"Yael","last_name":"Tauman Kalai"}],"article_processing_charge":"No","author":[{"last_name":"El-Hayek","id":"888a098e-fcac-11ee-aff7-d347be57b725","first_name":"Antoine","orcid":"0000-0003-4268-7368","full_name":"El-Hayek, Antoine"},{"last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Schmid","first_name":"Stefan","orcid":"0000-0002-7798-1711","full_name":"Schmid, Stefan"}],"scopus_import":"1","related_material":{"record":[{"id":"22281","relation":"dissertation_contains","status":"public"}]},"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)","_id":"22373","file":[{"checksum":"d7f45fdcbc5fccd61db69f56d775c636","access_level":"open_access","date_created":"2026-07-22T08:04:03Z","relation":"main_file","file_name":"2023_LIPIcs_El-Hayek.pdf","date_updated":"2026-07-22T08:04:03Z","content_type":"application/pdf","success":1,"file_id":"22383","file_size":1077427,"creator":"cchlebak"}],"date_updated":"2026-07-24T12:48:29Z","file_date_updated":"2026-07-22T08:04:03Z","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."}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","external_id":{"arxiv":["2211.10151"]},"date_created":"2026-07-20T11:45:04Z","ddc":["000"],"day":"01","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772631"]},"oa_version":"Published Version","arxiv":1,"intvolume":"       251","alternative_title":["LIPIcs"],"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. <i>14th Innovations in Theoretical Computer Science Conference</i>. Vol 251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">10.4230/LIPICS.ITCS.2023.47</a>","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.","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 <i>14th Innovations in Theoretical Computer Science Conference</i>, edited by Yael Tauman Kalai, Vol. 251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">https://doi.org/10.4230/LIPICS.ITCS.2023.47</a>.","apa":"El-Hayek, A., Henzinger, M., &#38; Schmid, S. (2023). Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks. In Y. Tauman Kalai (Ed.), <i>14th Innovations in Theoretical Computer Science Conference</i> (Vol. 251). Cambridge, Massachusetts, USA: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">https://doi.org/10.4230/LIPICS.ITCS.2023.47</a>","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 <i>14th Innovations in Theoretical Computer Science Conference</i>, 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.” <i>14th Innovations in Theoretical Computer Science Conference</i>, edited by Yael Tauman Kalai, vol. 251, 47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">10.4230/LIPICS.ITCS.2023.47</a>."},"quality_controlled":"1","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"conference":{"name":"ITCS: Innovations in Theoretical Computer Science","location":"Cambridge, Massachusetts, USA","end_date":"2023-01-13","start_date":"2023-01-10"},"oa":1,"date_published":"2023-02-01T00:00:00Z","type":"conference","publication_status":"published","publication":"14th Innovations in Theoretical Computer Science Conference","article_number":"47"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"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.","lang":"eng"}],"external_id":{"isi":["000947350400036"],"arxiv":["2104.07278"]},"date_created":"2021-09-12T22:01:25Z","day":"07","publication_identifier":{"issn":["1043-6871"],"eisbn":["978-1-6654-4895-6"],"isbn":["978-1-6654-4896-3"]},"oa_version":"Preprint","arxiv":1,"scopus_import":"1","ec_funded":1,"related_material":{"record":[{"id":"18630","relation":"later_version","status":"public"}]},"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).","_id":"10004","date_updated":"2026-08-12T06:39:27Z","date_published":"2021-07-07T00:00:00Z","oa":1,"type":"conference","page":"1-13","publication_status":"published","publication":"Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science","citation":{"ama":"Chatterjee K, Doyen L. Stochastic processes with expected stopping time. In: <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE; 2021:1-13. doi:<a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">10.1109/LICS52264.2021.9470595</a>","short":"K. Chatterjee, L. Doyen, in:, Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2021, pp. 1–13.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected Stopping Time.” In <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 1–13. IEEE, 2021. <a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">https://doi.org/10.1109/LICS52264.2021.9470595</a>.","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.","apa":"Chatterjee, K., &#38; Doyen, L. (2021). Stochastic processes with expected stopping time. In <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i> (pp. 1–13). Rome, Italy: IEEE. <a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">https://doi.org/10.1109/LICS52264.2021.9470595</a>","ieee":"K. Chatterjee and L. Doyen, “Stochastic processes with expected stopping time,” in <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Rome, Italy, 2021, pp. 1–13.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected Stopping Time.” <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, IEEE, 2021, pp. 1–13, doi:<a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">10.1109/LICS52264.2021.9470595</a>."},"isi":1,"conference":{"name":"LICS: Logic in Computer Science","start_date":"2021-06-29","location":"Rome, Italy","end_date":"2021-07-02"},"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2104.07278"}],"department":[{"_id":"KrCh"}],"doi":"10.1109/LICS52264.2021.9470595","status":"public","month":"07","language":[{"iso":"eng"}],"title":"Stochastic processes with expected stopping time","keyword":["Computer science","Heuristic algorithms","Memory management","Automata","Markov processes","Probability distribution","Complexity theory"],"year":"2021","publisher":"IEEE","project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"article_processing_charge":"No","author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"full_name":"Doyen, Laurent","first_name":"Laurent","last_name":"Doyen"}]},{"scopus_import":"1","extern":"1","year":"1988","publist_id":"1736","publisher":"Springer","_id":"4317","date_updated":"2022-02-08T09:19:50Z","doi":"10.1007/978-94-009-0435-4","main_file_link":[{"url":"https://link.springer.com/book/10.1007/978-94-009-0435-4#toc"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","date_created":"2018-12-11T12:08:13Z","publication_identifier":{"isbn":["978-0-412-40050-6"],"eissn":["978-94-009-0435-4"]},"day":"01","month":"01","keyword":["biogeography","biology","complexity","distribution","evolution","geology"],"edition":"1","oa_version":"None","language":[{"iso":"eng"}],"title":"Speciation","editor":[{"last_name":"Myers","first_name":"Alan","full_name":"Myers, Alan"},{"full_name":"Giller, Paul","first_name":"Paul","last_name":"Giller"}],"citation":{"apa":"Barton, N. H. (1988). Speciation. In A. Myers &#38; P. Giller (Eds.), <i>Analytical biogeography: An integrated approach to the study of animal and plant distributions</i> (1st ed., pp. 185–218). Springer. <a href=\"https://doi.org/10.1007/978-94-009-0435-4\">https://doi.org/10.1007/978-94-009-0435-4</a>","ieee":"N. H. Barton, “Speciation,” in <i>Analytical biogeography: An integrated approach to the study of animal and plant distributions</i>, 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.","chicago":"Barton, Nicholas H. “Speciation.” In <i>Analytical Biogeography: An Integrated Approach to the Study of Animal and Plant Distributions</i>, edited by Alan Myers and Paul Giller, 1st ed., 185–218. Springer, 1988. <a href=\"https://doi.org/10.1007/978-94-009-0435-4\">https://doi.org/10.1007/978-94-009-0435-4</a>.","mla":"Barton, Nicholas H. “Speciation.” <i>Analytical Biogeography: An Integrated Approach to the Study of Animal and Plant Distributions</i>, edited by Alan Myers and Paul Giller, 1st ed., Springer, 1988, pp. 185–218, doi:<a href=\"https://doi.org/10.1007/978-94-009-0435-4\">10.1007/978-94-009-0435-4</a>.","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.","ama":"Barton NH. Speciation. In: Myers A, Giller P, eds. <i>Analytical Biogeography: An Integrated Approach to the Study of Animal and Plant Distributions</i>. 1st ed. Springer; 1988:185-218. doi:<a href=\"https://doi.org/10.1007/978-94-009-0435-4\">10.1007/978-94-009-0435-4</a>"},"quality_controlled":"1","article_processing_charge":"No","author":[{"orcid":"0000-0002-8548-5240","full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","first_name":"Nicholas H","last_name":"Barton"}],"date_published":"1988-01-01T00:00:00Z","type":"book_chapter","page":"185 - 218","publication_status":"published","publication":"Analytical biogeography: An integrated approach to the study of animal and plant distributions"}]