[{"quality_controlled":"1","project":[{"grant_number":"101034413","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"isi":1,"date_created":"2025-04-20T22:01:28Z","OA_place":"publisher","language":[{"iso":"eng"}],"file_date_updated":"2026-01-05T13:45:57Z","article_type":"original","_id":"19603","oa_version":"Published Version","scopus_import":"1","doi":"10.1007/s00453-025-01306-y","article_processing_charge":"Yes (via OA deal)","title":"Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound","license":"https://creativecommons.org/licenses/by/4.0/","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"MaKw"}],"publication_status":"published","OA_type":"hybrid","year":"2025","publisher":"Springer Nature","external_id":{"isi":["001463103800001"]},"day":"01","oa":1,"type":"journal_article","intvolume":"        87","date_updated":"2026-01-05T13:46:08Z","date_published":"2025-07-01T00:00:00Z","related_material":{"record":[{"id":"18758","status":"public","relation":"earlier_version"}]},"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"citation":{"chicago":"Lill, Jonas, Kalina H Petrova, and Simon Weber. “Linear-Time MaxCut in Multigraphs Parameterized above the Poljak-Turzík Bound.” <i>Algorithmica</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s00453-025-01306-y\">https://doi.org/10.1007/s00453-025-01306-y</a>.","ama":"Lill J, Petrova KH, Weber S. Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. <i>Algorithmica</i>. 2025;87:983-1007. doi:<a href=\"https://doi.org/10.1007/s00453-025-01306-y\">10.1007/s00453-025-01306-y</a>","apa":"Lill, J., Petrova, K. H., &#38; Weber, S. (2025). Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00453-025-01306-y\">https://doi.org/10.1007/s00453-025-01306-y</a>","ieee":"J. Lill, K. H. Petrova, and S. Weber, “Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound,” <i>Algorithmica</i>, vol. 87. Springer Nature, pp. 983–1007, 2025.","mla":"Lill, Jonas, et al. “Linear-Time MaxCut in Multigraphs Parameterized above the Poljak-Turzík Bound.” <i>Algorithmica</i>, vol. 87, Springer Nature, 2025, pp. 983–1007, doi:<a href=\"https://doi.org/10.1007/s00453-025-01306-y\">10.1007/s00453-025-01306-y</a>.","short":"J. Lill, K.H. Petrova, S. Weber, Algorithmica 87 (2025) 983–1007.","ista":"Lill J, Petrova KH, Weber S. 2025. Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. Algorithmica. 87, 983–1007."},"abstract":[{"lang":"eng","text":"MaxCut is a classical NP-complete problem and a crucial building block in many\r\ncombinatorial algorithms. The famousEdwards-Erdös bound states that any connected\r\ngraph on n vertices with m edges contains a cut of size at least m/2 + n−1/4 . Crowston,\r\nJones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple\r\nconnected graphs admits an FPT algorithm, where the parameter k is the difference\r\nbetween the desired cut size c and the lower bound given by the Edwards-Erdös\r\nbound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run\r\nin parameterized linear time, i.e., f (k) · O(m). We improve upon this result in two\r\nways: Firstly, we extend the algorithm to work also for multigraphs (alternatively,\r\ngraphs with positive integer weights). Secondly, we change the parameter; instead of\r\nthe difference to the Edwards-Erdös bound, we use the difference to the Poljak-Turzík\r\nbound. The Poljak-Turzík bound states that any weighted graph G has a cut of weight\r\nat least w(G)/2 + wMSF (G)/4 , where w(G) denotes the total weight of G, and wMSF (G)\r\ndenotes the weight of its minimum spanning forest. In connected simple graphs the\r\ntwo bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger\r\nand thus yield a smaller parameter k. Our algorithm also runs in parameterized linear\r\ntime, i.e., f (k) · O(m + n)."}],"has_accepted_license":"1","month":"07","ec_funded":1,"volume":87,"acknowledgement":"Kalina Petrova is supported by the Swiss National Science Foundation, grant no. CRSII5 173721, and also receives funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413. Simon Weber is supported by the Swiss National Science Foundation under project no. 204320.\r\nOpen access funding provided by Swiss Federal Institute of Technology Zurich.","ddc":["510"],"file":[{"file_size":448554,"content_type":"application/pdf","success":1,"file_name":"2025_Algorithmica_Lill.pdf","file_id":"20957","relation":"main_file","checksum":"eab3f1834b0ba347b05ae9897729c0ad","creator":"dernst","date_updated":"2026-01-05T13:45:57Z","access_level":"open_access","date_created":"2026-01-05T13:45:57Z"}],"page":"983-1007","status":"public","author":[{"full_name":"Lill, Jonas","last_name":"Lill","first_name":"Jonas"},{"first_name":"Kalina H","last_name":"Petrova","full_name":"Petrova, Kalina H","id":"554ff4e4-f325-11ee-b0c4-a10dbd523381"},{"full_name":"Weber, Simon","first_name":"Simon","last_name":"Weber"}],"publication":"Algorithmica"},{"doi":"10.1007/s00453-022-01027-6","scopus_import":"1","oa_version":"Published Version","_id":"12086","article_type":"original","file_date_updated":"2023-01-20T10:02:48Z","language":[{"iso":"eng"}],"date_created":"2022-09-11T22:01:57Z","isi":1,"project":[{"name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"788183"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"Mathematics, Computer Science","call_identifier":"FWF","grant_number":"Z00342"},{"grant_number":"I02979-N35","call_identifier":"FWF","name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","type":"journal_article","oa":1,"pmid":1,"external_id":{"pmid":["36687803"],"isi":["000846967100001"]},"day":"01","publisher":"Springer Nature","publication_status":"published","year":"2023","department":[{"_id":"HeEd"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"title":"A simple algorithm for higher-order Delaunay mosaics and alpha shapes","article_processing_charge":"Yes (via OA deal)","corr_author":"1","has_accepted_license":"1","abstract":[{"text":"We present a simple algorithm for computing higher-order Delaunay mosaics that works in Euclidean spaces of any finite dimensions. The algorithm selects the vertices of the order-k mosaic from incrementally constructed lower-order mosaics and uses an algorithm for weighted first-order Delaunay mosaics as a black-box to construct the order-k mosaic from its vertices. Beyond this black-box, the algorithm uses only combinatorial operations, thus facilitating easy implementation. We extend this algorithm to compute higher-order α-shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets.","lang":"eng"}],"citation":{"chicago":"Edelsbrunner, Herbert, and Georg F Osang. “A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes.” <i>Algorithmica</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00453-022-01027-6\">https://doi.org/10.1007/s00453-022-01027-6</a>.","ama":"Edelsbrunner H, Osang GF. A simple algorithm for higher-order Delaunay mosaics and alpha shapes. <i>Algorithmica</i>. 2023;85:277-295. doi:<a href=\"https://doi.org/10.1007/s00453-022-01027-6\">10.1007/s00453-022-01027-6</a>","apa":"Edelsbrunner, H., &#38; Osang, G. F. (2023). A simple algorithm for higher-order Delaunay mosaics and alpha shapes. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00453-022-01027-6\">https://doi.org/10.1007/s00453-022-01027-6</a>","mla":"Edelsbrunner, Herbert, and Georg F. Osang. “A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes.” <i>Algorithmica</i>, vol. 85, Springer Nature, 2023, pp. 277–95, doi:<a href=\"https://doi.org/10.1007/s00453-022-01027-6\">10.1007/s00453-022-01027-6</a>.","ieee":"H. Edelsbrunner and G. F. Osang, “A simple algorithm for higher-order Delaunay mosaics and alpha shapes,” <i>Algorithmica</i>, vol. 85. Springer Nature, pp. 277–295, 2023.","short":"H. Edelsbrunner, G.F. Osang, Algorithmica 85 (2023) 277–295.","ista":"Edelsbrunner H, Osang GF. 2023. A simple algorithm for higher-order Delaunay mosaics and alpha shapes. Algorithmica. 85, 277–295."},"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2023-01-01T00:00:00Z","date_updated":"2025-04-23T08:46:48Z","intvolume":"        85","publication":"Algorithmica","author":[{"first_name":"Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"id":"464B40D6-F248-11E8-B48F-1D18A9856A87","full_name":"Osang, Georg F","orcid":"0000-0002-8882-5116","last_name":"Osang","first_name":"Georg F"}],"status":"public","page":"277-295","file":[{"relation":"main_file","checksum":"71685ca5121f4c837f40c3f8eb50c915","creator":"dernst","date_updated":"2023-01-20T10:02:48Z","access_level":"open_access","date_created":"2023-01-20T10:02:48Z","file_size":911017,"content_type":"application/pdf","success":1,"file_name":"2023_Algorithmica_Edelsbrunner.pdf","file_id":"12322"}],"ddc":["510"],"ec_funded":1,"volume":85,"acknowledgement":"Open access funding provided by Austrian Science Fund (FWF). This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, Grant No. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), Grant No. I 02979-N35.","month":"01"},{"oa_version":"Preprint","scopus_import":"1","_id":"14043","doi":"10.1007/s00453-023-01154-8","language":[{"iso":"eng"}],"article_type":"original","isi":1,"date_created":"2023-08-13T22:01:13Z","quality_controlled":"1","project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"}],"oa":1,"external_id":{"isi":["001041254900002"],"arxiv":["2010.16316"]},"day":"01","type":"journal_article","department":[{"_id":"MoHe"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2010.16316"}],"publisher":"Springer Nature","publication_status":"published","year":"2023","arxiv":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"title":"A combinatorial cut-toggling algorithm for solving Laplacian linear systems","article_processing_charge":"No","citation":{"chicago":"Henzinger, Monika, Billy Jin, Richard Peng, and David P. Williamson. “A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems.” <i>Algorithmica</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00453-023-01154-8\">https://doi.org/10.1007/s00453-023-01154-8</a>.","ama":"Henzinger M, Jin B, Peng R, Williamson DP. A combinatorial cut-toggling algorithm for solving Laplacian linear systems. <i>Algorithmica</i>. 2023;85:2680-3716. doi:<a href=\"https://doi.org/10.1007/s00453-023-01154-8\">10.1007/s00453-023-01154-8</a>","apa":"Henzinger, M., Jin, B., Peng, R., &#38; Williamson, D. P. (2023). A combinatorial cut-toggling algorithm for solving Laplacian linear systems. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00453-023-01154-8\">https://doi.org/10.1007/s00453-023-01154-8</a>","mla":"Henzinger, Monika, et al. “A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems.” <i>Algorithmica</i>, vol. 85, Springer Nature, 2023, pp. 2680–3716, doi:<a href=\"https://doi.org/10.1007/s00453-023-01154-8\">10.1007/s00453-023-01154-8</a>.","short":"M. Henzinger, B. Jin, R. Peng, D.P. Williamson, Algorithmica 85 (2023) 2680–3716.","ieee":"M. Henzinger, B. Jin, R. Peng, and D. P. Williamson, “A combinatorial cut-toggling algorithm for solving Laplacian linear systems,” <i>Algorithmica</i>, vol. 85. Springer Nature, pp. 2680–3716, 2023.","ista":"Henzinger M, Jin B, Peng R, Williamson DP. 2023. A combinatorial cut-toggling algorithm for solving Laplacian linear systems. Algorithmica. 85, 2680–3716."},"abstract":[{"lang":"eng","text":"Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems of the form Lx=b, where L is the Laplacian matrix of a weighted graph with weights w(i,j)>0 on the edges. The solution x of the linear system can be interpreted as the potentials of an electrical flow in which the resistance on edge (i, j) is 1/w(i, j). Kelner et al. (in: Proceedings of the 45th Annual ACM Symposium on the Theory of Computing, pp 911–920, 2013. https://doi.org/10.1145/2488608.2488724) give a combinatorial, near-linear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law by updating flows around cycles (cycle toggling). In this paper, we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling: each iteration updates all potentials on one side of a fundamental cut of a spanning tree by the same amount. We prove that this dual algorithm also runs in a near-linear number of iterations. We show, however, that if we abstract cut toggling as a natural data structure problem, this problem can be reduced to the online vector–matrix-vector problem, which has been conjectured to be difficult for dynamic algorithms (Henzinger et al., in: Proceedings of the 47th Annual ACM Symposium on the Theory of Computing, pp 21–30, 2015. https://doi.org/10.1145/2746539.2746609). The conjecture implies that the data structure does not have an O(n1−ϵ) time algorithm for any ϵ>0, and thus a straightforward implementation of the cut-toggling algorithm requires essentially linear time per iteration. To circumvent the lower bound, we batch update steps, and perform them simultaneously instead of sequentially. An appropriate choice of batching leads to an O˜(m1.5) time cut-toggling algorithm for solving Laplacian systems. Furthermore, we show that if we sparsify the graph and call our algorithm recursively on the Laplacian system implied by batching and sparsifying, we can reduce the running time to O(m1+ϵ) for any ϵ>0. Thus, the dual cut-toggling algorithm can achieve (almost) the same running time as its primal cycle-toggling counterpart."}],"date_published":"2023-12-01T00:00:00Z","date_updated":"2025-04-15T06:24:05Z","intvolume":"        85","publication":"Algorithmica","author":[{"first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"last_name":"Jin","first_name":"Billy","full_name":"Jin, Billy"},{"full_name":"Peng, Richard","first_name":"Richard","last_name":"Peng"},{"last_name":"Williamson","first_name":"David P.","full_name":"Williamson, David P."}],"status":"public","page":"2680-3716","month":"12","ec_funded":1,"acknowledgement":"Monika Henzinger was supported by funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant agreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024. Billy Jin was Supported in part by NSERC fellowship PGSD3-532673-2019 and NSF grant CCF-2007009. Richard Peng was supported in part by an NSERC Discovery Grant and NSF grant CCF-1846218. David P. Williamson was supported in part by NSF grant CCF-2007009.","volume":85},{"ddc":["000"],"acknowledgement":"The authors sincerely thank Thomas Sauerwald and George Giakkoupis for insightful discussions, and Mohsen Ghaffari, Yuval Peres, and Udi Wieder for feedback on earlier versions of this draft. We also thank the ICALP anonymous reviewers for their very useful comments. Open access funding provided by Institute of Science and Technology (IST Austria). Funding was provided by European Research Council (Grant No. PR1042ERC01).","ec_funded":1,"volume":84,"month":"04","page":"1007-1029","file":[{"content_type":"application/pdf","file_size":525950,"file_id":"10577","file_name":"2021_Algorithmica_Alistarh.pdf","success":1,"checksum":"21169b25b0c8e17b21e12af22bff9870","relation":"main_file","access_level":"open_access","date_created":"2021-12-27T10:36:40Z","date_updated":"2021-12-27T10:36:40Z","creator":"cchlebak"}],"author":[{"first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian"},{"full_name":"Nadiradze, Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","first_name":"Giorgi","orcid":"0000-0001-5634-0731","last_name":"Nadiradze"},{"id":"bcc145fd-e77f-11ea-ae8b-80d661dbff67","full_name":"Sabour, Amirmojtaba","first_name":"Amirmojtaba","last_name":"Sabour"}],"status":"public","issue":"4","publication":"Algorithmica","intvolume":"        84","date_updated":"2025-07-10T11:55:11Z","related_material":{"record":[{"id":"15077","relation":"earlier_version","status":"public"}],"link":[{"url":"https://doi.org/10.4230/LIPIcs.ICALP.2020.7","relation":"earlier_version"}]},"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2022-04-01T00:00:00Z","has_accepted_license":"1","conference":{"end_date":"2020-07-11","start_date":"2020-07-08","name":"ICALP: Automata, Languages and Programming","location":"Virtual, Online; Germany"},"abstract":[{"lang":"eng","text":"We consider the following dynamic load-balancing process: given an underlying graph G with n nodes, in each step t≥ 0, one unit of load is created, and placed at a randomly chosen graph node. In the same step, the chosen node picks a random neighbor, and the two nodes balance their loads by averaging them. We are interested in the expected gap between the minimum and maximum loads at nodes as the process progresses, and its dependence on n and on the graph structure. Variants of the above graphical balanced allocation process have been studied previously by Peres, Talwar, and Wieder [Peres et al., 2015], and by Sauerwald and Sun [Sauerwald and Sun, 2015]. These authors left as open the question of characterizing the gap in the case of cycle graphs in the dynamic case, where weights are created during the algorithm’s execution. For this case, the only known upper bound is of 𝒪(n log n), following from a majorization argument due to [Peres et al., 2015], which analyzes a related graphical allocation process. In this paper, we provide an upper bound of 𝒪 (√n log n) on the expected gap of the above process for cycles of length n. We introduce a new potential analysis technique, which enables us to bound the difference in load between k-hop neighbors on the cycle, for any k ≤ n/2. We complement this with a \"gap covering\" argument, which bounds the maximum value of the gap by bounding its value across all possible subsets of a certain structure, and recursively bounding the gaps within each subset. We provide analytical and experimental evidence that our upper bound on the gap is tight up to a logarithmic factor. "}],"citation":{"ista":"Alistarh D-A, Nadiradze G, Sabour A. 2022. Dynamic averaging load balancing on cycles. Algorithmica. 84(4), 1007–1029.","apa":"Alistarh, D.-A., Nadiradze, G., &#38; Sabour, A. (2022). Dynamic averaging load balancing on cycles. <i>Algorithmica</i>. Virtual, Online; Germany: Springer Nature. <a href=\"https://doi.org/10.1007/s00453-021-00905-9\">https://doi.org/10.1007/s00453-021-00905-9</a>","mla":"Alistarh, Dan-Adrian, et al. “Dynamic Averaging Load Balancing on Cycles.” <i>Algorithmica</i>, vol. 84, no. 4, Springer Nature, 2022, pp. 1007–29, doi:<a href=\"https://doi.org/10.1007/s00453-021-00905-9\">10.1007/s00453-021-00905-9</a>.","ieee":"D.-A. Alistarh, G. Nadiradze, and A. Sabour, “Dynamic averaging load balancing on cycles,” <i>Algorithmica</i>, vol. 84, no. 4. Springer Nature, pp. 1007–1029, 2022.","short":"D.-A. Alistarh, G. Nadiradze, A. Sabour, Algorithmica 84 (2022) 1007–1029.","chicago":"Alistarh, Dan-Adrian, Giorgi Nadiradze, and Amirmojtaba Sabour. “Dynamic Averaging Load Balancing on Cycles.” <i>Algorithmica</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s00453-021-00905-9\">https://doi.org/10.1007/s00453-021-00905-9</a>.","ama":"Alistarh D-A, Nadiradze G, Sabour A. Dynamic averaging load balancing on cycles. <i>Algorithmica</i>. 2022;84(4):1007-1029. doi:<a href=\"https://doi.org/10.1007/s00453-021-00905-9\">10.1007/s00453-021-00905-9</a>"},"title":"Dynamic averaging load balancing on cycles","article_processing_charge":"Yes (via OA deal)","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"arxiv":1,"publisher":"Springer Nature","year":"2022","publication_status":"published","department":[{"_id":"DaAl"}],"type":"journal_article","oa":1,"external_id":{"arxiv":["2003.09297"],"isi":["000734004600001"]},"day":"01","project":[{"call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"},{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"quality_controlled":"1","date_created":"2020-08-24T06:24:04Z","isi":1,"article_type":"original","language":[{"iso":"eng"}],"file_date_updated":"2021-12-27T10:36:40Z","doi":"10.1007/s00453-021-00905-9","oa_version":"Published Version","scopus_import":"1","_id":"8286"},{"abstract":[{"lang":"eng","text":"In this paper, we study the problem of opening centers to cluster a set of clients in a metric space so as to minimize the sum of the costs of the centers and of the cluster radii, in a dynamic environment where clients arrive and depart, and the solution must be updated efficiently while remaining competitive with respect to the current optimal solution. We call this dynamic sum-of-radii clustering problem. We present a data structure that maintains a solution whose cost is within a constant factor of the cost of an optimal solution in metric spaces with bounded doubling dimension and whose worst-case update time is logarithmic in the parameters of the problem."}],"citation":{"ama":"Henzinger M, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum of radii. <i>Algorithmica</i>. 2020;82(11):3183-3194. doi:<a href=\"https://doi.org/10.1007/s00453-020-00721-7\">10.1007/s00453-020-00721-7</a>","chicago":"Henzinger, Monika, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering to Minimize the Sum of Radii.” <i>Algorithmica</i>. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/s00453-020-00721-7\">https://doi.org/10.1007/s00453-020-00721-7</a>.","short":"M. Henzinger, D. Leniowski, C. Mathieu, Algorithmica 82 (2020) 3183–3194.","ieee":"M. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize the sum of radii,” <i>Algorithmica</i>, vol. 82, no. 11. Springer Nature, pp. 3183–3194, 2020.","mla":"Henzinger, Monika, et al. “Dynamic Clustering to Minimize the Sum of Radii.” <i>Algorithmica</i>, vol. 82, no. 11, Springer Nature, 2020, pp. 3183–94, doi:<a href=\"https://doi.org/10.1007/s00453-020-00721-7\">10.1007/s00453-020-00721-7</a>.","apa":"Henzinger, M., Leniowski, D., &#38; Mathieu, C. (2020). Dynamic clustering to minimize the sum of radii. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00453-020-00721-7\">https://doi.org/10.1007/s00453-020-00721-7</a>","ista":"Henzinger M, Leniowski D, Mathieu C. 2020. Dynamic clustering to minimize the sum of radii. Algorithmica. 82(11), 3183–3194."},"date_published":"2020-11-01T00:00:00Z","date_updated":"2024-11-04T11:41:57Z","extern":"1","intvolume":"        82","issue":"11","publication":"Algorithmica","author":[{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"first_name":"Dariusz","last_name":"Leniowski","full_name":"Leniowski, Dariusz"},{"first_name":"Claire","last_name":"Mathieu","full_name":"Mathieu, Claire"}],"status":"public","page":"3183-3194","volume":82,"month":"11","doi":"10.1007/s00453-020-00721-7","oa_version":"Preprint","scopus_import":"1","_id":"11674","article_type":"original","language":[{"iso":"eng"}],"date_created":"2022-07-27T13:58:58Z","quality_controlled":"1","type":"journal_article","oa":1,"external_id":{"arxiv":["1707.02577"]},"day":"01","publisher":"Springer Nature","publication_status":"published","year":"2020","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1707.02577"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"arxiv":1,"title":"Dynamic clustering to minimize the sum of radii","article_processing_charge":"No"},{"intvolume":"        82","keyword":["Dynamic algorithms","Data structures","Graph algorithms","Matching","Vertex cover"],"date_updated":"2024-11-06T12:07:43Z","extern":"1","date_published":"2020-04-01T00:00:00Z","citation":{"ama":"Bhattacharya S, Chakrabarty D, Henzinger M. Deterministic dynamic matching in O(1) update time. <i>Algorithmica</i>. 2020;82(4):1057-1080. doi:<a href=\"https://doi.org/10.1007/s00453-019-00630-4\">10.1007/s00453-019-00630-4</a>","chicago":"Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika Henzinger. “Deterministic Dynamic Matching in O(1) Update Time.” <i>Algorithmica</i>. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/s00453-019-00630-4\">https://doi.org/10.1007/s00453-019-00630-4</a>.","short":"S. Bhattacharya, D. Chakrabarty, M. Henzinger, Algorithmica 82 (2020) 1057–1080.","ieee":"S. Bhattacharya, D. Chakrabarty, and M. Henzinger, “Deterministic dynamic matching in O(1) update time,” <i>Algorithmica</i>, vol. 82, no. 4. Springer Nature, pp. 1057–1080, 2020.","mla":"Bhattacharya, Sayan, et al. “Deterministic Dynamic Matching in O(1) Update Time.” <i>Algorithmica</i>, vol. 82, no. 4, Springer Nature, 2020, pp. 1057–80, doi:<a href=\"https://doi.org/10.1007/s00453-019-00630-4\">10.1007/s00453-019-00630-4</a>.","apa":"Bhattacharya, S., Chakrabarty, D., &#38; Henzinger, M. (2020). Deterministic dynamic matching in O(1) update time. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00453-019-00630-4\">https://doi.org/10.1007/s00453-019-00630-4</a>","ista":"Bhattacharya S, Chakrabarty D, Henzinger M. 2020. Deterministic dynamic matching in O(1) update time. Algorithmica. 82(4), 1057–1080."},"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."}],"month":"04","volume":82,"page":"1057-1080","status":"public","author":[{"first_name":"Sayan","last_name":"Bhattacharya","full_name":"Bhattacharya, Sayan"},{"full_name":"Chakrabarty, Deeparnab","first_name":"Deeparnab","last_name":"Chakrabarty"},{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"}],"issue":"4","publication":"Algorithmica","quality_controlled":"1","date_created":"2022-07-27T14:31:06Z","language":[{"iso":"eng"}],"article_type":"original","_id":"11675","oa_version":"Published Version","scopus_import":"1","doi":"10.1007/s00453-019-00630-4","article_processing_charge":"No","title":"Deterministic dynamic matching in O(1) update time","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://doi.org/10.1007/s00453-019-00630-4","open_access":"1"}],"year":"2020","publication_status":"published","publisher":"Springer Nature","day":"01","oa":1,"type":"journal_article"},{"intvolume":"        77","keyword":["Approximation algorithms","Submodular functions","Phylogenetic diversity","Viability constraints"],"date_updated":"2024-11-06T12:07:55Z","extern":"1","date_published":"2017-01-01T00:00:00Z","citation":{"ista":"Dvořák W, Henzinger M, Williamson DP. 2017. Maximizing a submodular function with viability constraints. Algorithmica. 77(1), 152–172.","chicago":"Dvořák, Wolfgang, Monika Henzinger, and David P. Williamson. “Maximizing a Submodular Function with Viability Constraints.” <i>Algorithmica</i>. Springer Nature, 2017. <a href=\"https://doi.org/10.1007/s00453-015-0066-y\">https://doi.org/10.1007/s00453-015-0066-y</a>.","ama":"Dvořák W, Henzinger M, Williamson DP. Maximizing a submodular function with viability constraints. <i>Algorithmica</i>. 2017;77(1):152-172. doi:<a href=\"https://doi.org/10.1007/s00453-015-0066-y\">10.1007/s00453-015-0066-y</a>","apa":"Dvořák, W., Henzinger, M., &#38; Williamson, D. P. (2017). Maximizing a submodular function with viability constraints. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00453-015-0066-y\">https://doi.org/10.1007/s00453-015-0066-y</a>","ieee":"W. Dvořák, M. Henzinger, and D. P. Williamson, “Maximizing a submodular function with viability constraints,” <i>Algorithmica</i>, vol. 77, no. 1. Springer Nature, pp. 152–172, 2017.","mla":"Dvořák, Wolfgang, et al. “Maximizing a Submodular Function with Viability Constraints.” <i>Algorithmica</i>, vol. 77, no. 1, Springer Nature, 2017, pp. 152–72, doi:<a href=\"https://doi.org/10.1007/s00453-015-0066-y\">10.1007/s00453-015-0066-y</a>.","short":"W. Dvořák, M. Henzinger, D.P. Williamson, Algorithmica 77 (2017) 152–172."},"abstract":[{"lang":"eng","text":"We study the problem of maximizing a monotone submodular function with viability constraints. This problem originates from computational biology, where we are given a phylogenetic tree over a set of species and a directed graph, the so-called food web, encoding viability constraints between these species. These food webs usually have constant depth. The goal is to select a subset of k species that satisfies the viability constraints and has maximal phylogenetic diversity. As this problem is known to be NP-hard, we investigate approximation algorithms. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is (1−1e√). This algorithm not only applies to phylogenetic trees with viability constraints but for arbitrary monotone submodular set functions with viability constraints. Second, we show that there is no (1−1/e+ϵ)-approximation algorithm for our problem setting (even for additive functions) and that there is no approximation algorithm for a slight extension of this setting."}],"month":"01","volume":77,"acknowledgement":"The research leading to these results has received funding from the European Research\r\nCouncil under the European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement No. 340506.","page":"152-172","status":"public","author":[{"full_name":"Dvořák, Wolfgang","first_name":"Wolfgang","last_name":"Dvořák"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger"},{"first_name":"David P.","last_name":"Williamson","full_name":"Williamson, David P."}],"publication":"Algorithmica","issue":"1","quality_controlled":"1","date_created":"2022-07-27T14:37:24Z","language":[{"iso":"eng"}],"article_type":"original","_id":"11676","oa_version":"Preprint","scopus_import":"1","doi":"10.1007/s00453-015-0066-y","article_processing_charge":"No","title":"Maximizing a submodular function with viability constraints","arxiv":1,"publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://arxiv.org/abs/1611.05753","open_access":"1"}],"year":"2017","publication_status":"published","publisher":"Springer Nature","external_id":{"arxiv":["1611.05753"]},"day":"01","oa":1,"type":"journal_article"},{"page":"681 - 713","file":[{"checksum":"7873f665a0c598ac747c908f34cb14b9","relation":"main_file","access_level":"open_access","date_created":"2018-12-12T10:10:19Z","date_updated":"2020-07-14T12:44:44Z","creator":"system","content_type":"application/pdf","file_size":710206,"file_id":"4805","file_name":"IST-2016-658-v1+1_s00453-016-0212-1.pdf"}],"ec_funded":1,"volume":78,"ddc":["576"],"month":"06","publication":"Algorithmica","issue":"2","status":"public","author":[{"full_name":"Paixao, Tiago","id":"2C5658E6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2361-3953","last_name":"Paixao","first_name":"Tiago"},{"first_name":"Jorge","last_name":"Pérez Heredia","full_name":"Pérez Heredia, Jorge"},{"full_name":"Sudholt, Dirk","first_name":"Dirk","last_name":"Sudholt"},{"orcid":"0000-0002-6873-2967","last_name":"Trubenova","first_name":"Barbora","id":"42302D54-F248-11E8-B48F-1D18A9856A87","full_name":"Trubenova, Barbora"}],"publist_id":"5931","date_updated":"2026-04-16T09:55:33Z","intvolume":"        78","pubrep_id":"658","has_accepted_license":"1","citation":{"apa":"Paixao, T., Pérez Heredia, J., Sudholt, D., &#38; Trubenova, B. (2017). Towards a runtime comparison of natural and artificial evolution. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/s00453-016-0212-1\">https://doi.org/10.1007/s00453-016-0212-1</a>","ieee":"T. Paixao, J. Pérez Heredia, D. Sudholt, and B. Trubenova, “Towards a runtime comparison of natural and artificial evolution,” <i>Algorithmica</i>, vol. 78, no. 2. Springer, pp. 681–713, 2017.","short":"T. Paixao, J. Pérez Heredia, D. Sudholt, B. Trubenova, Algorithmica 78 (2017) 681–713.","mla":"Paixao, Tiago, et al. “Towards a Runtime Comparison of Natural and Artificial Evolution.” <i>Algorithmica</i>, vol. 78, no. 2, Springer, 2017, pp. 681–713, doi:<a href=\"https://doi.org/10.1007/s00453-016-0212-1\">10.1007/s00453-016-0212-1</a>.","chicago":"Paixao, Tiago, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenova. “Towards a Runtime Comparison of Natural and Artificial Evolution.” <i>Algorithmica</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s00453-016-0212-1\">https://doi.org/10.1007/s00453-016-0212-1</a>.","ama":"Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. Towards a runtime comparison of natural and artificial evolution. <i>Algorithmica</i>. 2017;78(2):681-713. doi:<a href=\"https://doi.org/10.1007/s00453-016-0212-1\">10.1007/s00453-016-0212-1</a>","ista":"Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. 2017. Towards a runtime comparison of natural and artificial evolution. Algorithmica. 78(2), 681–713."},"abstract":[{"lang":"eng","text":"Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrences of new mutations is much longer than the time it takes for a mutated genotype to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a stochastic process evolving one genotype by means of mutation and selection between the resident and the mutated genotype. The probability of accepting the mutated genotype then depends on the change in fitness. We study this process, SSWM, from an algorithmic perspective, quantifying its expected optimisation time for various parameters and investigating differences to a similar evolutionary algorithm, the well-known (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient."}],"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2017-06-01T00:00:00Z","publication_identifier":{"issn":["0178-4617"]},"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","article_processing_charge":"No","title":"Towards a runtime comparison of natural and artificial evolution","type":"journal_article","day":"01","external_id":{"isi":["000400379500013"]},"oa":1,"publication_status":"published","year":"2017","publisher":"Springer","department":[{"_id":"NiBa"},{"_id":"CaGu"}],"date_created":"2018-12-11T11:51:27Z","isi":1,"project":[{"grant_number":"618091","_id":"25B1EC9E-B435-11E9-9278-68D0E5697425","name":"Speed of Adaptation in Population Genetics and Evolutionary Computation","call_identifier":"FP7"}],"quality_controlled":"1","doi":"10.1007/s00453-016-0212-1","_id":"1336","scopus_import":"1","oa_version":"Published Version","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:44:44Z"},{"month":"05","volume":24,"page":"1-13","status":"public","author":[{"first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"King, V.","last_name":"King","first_name":"V."},{"full_name":"Warnow, T.","first_name":"T.","last_name":"Warnow"}],"publication":"Algorithmica","intvolume":"        24","keyword":["Algorithms","Data structures","Evolutionary biology","Theory of databases"],"date_updated":"2024-11-04T11:41:23Z","extern":"1","date_published":"1999-05-01T00:00:00Z","related_material":{"record":[{"id":"11927","status":"public","relation":"earlier_version"}]},"citation":{"ista":"Henzinger M, King V, Warnow T. 1999. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica. 24, 1–13.","short":"M. Henzinger, V. King, T. Warnow, Algorithmica 24 (1999) 1–13.","mla":"Henzinger, Monika, et al. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” <i>Algorithmica</i>, vol. 24, Springer Nature, 1999, pp. 1–13, doi:<a href=\"https://doi.org/10.1007/pl00009268\">10.1007/pl00009268</a>.","ieee":"M. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology,” <i>Algorithmica</i>, vol. 24. Springer Nature, pp. 1–13, 1999.","apa":"Henzinger, M., King, V., &#38; Warnow, T. (1999). Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/pl00009268\">https://doi.org/10.1007/pl00009268</a>","ama":"Henzinger M, King V, Warnow T. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. <i>Algorithmica</i>. 1999;24:1-13. doi:<a href=\"https://doi.org/10.1007/pl00009268\">10.1007/pl00009268</a>","chicago":"Henzinger, Monika, V. King, and T. Warnow. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” <i>Algorithmica</i>. Springer Nature, 1999. <a href=\"https://doi.org/10.1007/pl00009268\">https://doi.org/10.1007/pl00009268</a>."},"abstract":[{"lang":"eng","text":"We are given a set T = {T 1 ,T 2 , . . .,T k } of rooted binary trees, each T i leaf-labeled by a subset L(Ti)⊂{1,2,...,n} . If T is a tree on {1,2, . . .,n }, we let T|L denote the minimal subtree of T induced by the nodes of L and all their ancestors. The consensus tree problem asks whether there exists a tree T * such that, for every i , T∗|L(Ti) is homeomorphic to T i .\r\n\r\nWe present algorithms which test if a given set of trees has a consensus tree and if so, construct one. The deterministic algorithm takes time min{O(N n 1/2 ), O(N+ n 2 log n )}, where N=∑i|Ti| , and uses linear space. The randomized algorithm takes time O(N log3 n) and uses linear space. The previous best for this problem was a 1981 O(Nn) algorithm by Aho et al. Our faster deterministic algorithm uses a new efficient algorithm for the following interesting dynamic graph problem: Given a graph G with n nodes and m edges and a sequence of b batches of one or more edge deletions, then, after each batch, either find a new component that has just been created or determine that there is no such component. For this problem, we have a simple algorithm with running time O(n 2 log n + b 0 min{n 2 , m log n }), where b 0 is the number of batches which do not result in a new component. For our particular application, b0≤1 . If all edges are deleted, then the best previously known deterministic algorithm requires time O(mn−−√) to solve this problem. We also present two applications of these consensus tree algorithms which solve other problems in computational evolutionary biology."}],"article_processing_charge":"No","title":"Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology","publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"1999","publication_status":"published","publisher":"Springer Nature","day":"01","type":"journal_article","quality_controlled":"1","date_created":"2022-07-27T15:02:28Z","language":[{"iso":"eng"}],"article_type":"original","_id":"11679","oa_version":"None","scopus_import":"1","doi":"10.1007/pl00009268"},{"month":"01","acknowledgement":"The authors would like to thank Emo Welzl for helpful discussions.","volume":20,"page":"31-60","status":"public","author":[{"full_name":"Alberts, D.","first_name":"D.","last_name":"Alberts"},{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"}],"publication":"Algorithmica","intvolume":"        20","keyword":["Dynamic graph algorithm","Average-case analysis","Minimum spanning forest","Connectivity","Bipartiteness","Maximum matching."],"date_updated":"2024-11-06T12:26:40Z","extern":"1","date_published":"1998-01-01T00:00:00Z","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"11928"}]},"abstract":[{"lang":"eng","text":"We present a model for edge updates with restricted randomness in dynamic graph algorithms and a general technique for analyzing the expected running time of an update operation. This model is able to capture the average case in many applications, since (1) it allows restrictions on the set of edges which can be used for insertions and (2) the type (insertion or deletion) of each update operation is arbitrary, i.e., not random. We use our technique to analyze existing and new dynamic algorithms for the following problems: maximum cardinality matching, minimum spanning forest, connectivity, 2-edge connectivity, k -edge connectivity, k -vertex connectivity, and bipartiteness. Given a random graph G with m 0 edges and n vertices and a sequence of l update operations such that the graph contains m i edges after operation i , the expected time for performing the updates for any l is O(llogn+∑li=1n/m−−√i) in the case of minimum spanning forests, connectivity, 2-edge connectivity, and bipartiteness. The expected time per update operation is O(n) in the case of maximum matching. We also give improved bounds for k -edge and k -vertex connectivity. Additionally we give an insertions-only algorithm for maximum cardinality matching with worst-case O(n) amortized time per insertion."}],"citation":{"apa":"Alberts, D., &#38; Henzinger, M. (1998). Average-case analysis of dynamic graph algorithms. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/pl00009186\">https://doi.org/10.1007/pl00009186</a>","short":"D. Alberts, M. Henzinger, Algorithmica 20 (1998) 31–60.","mla":"Alberts, D., and Monika Henzinger. “Average-Case Analysis of Dynamic Graph Algorithms.” <i>Algorithmica</i>, vol. 20, Springer Nature, 1998, pp. 31–60, doi:<a href=\"https://doi.org/10.1007/pl00009186\">10.1007/pl00009186</a>.","ieee":"D. Alberts and M. Henzinger, “Average-case analysis of dynamic graph algorithms,” <i>Algorithmica</i>, vol. 20. Springer Nature, pp. 31–60, 1998.","chicago":"Alberts, D., and Monika Henzinger. “Average-Case Analysis of Dynamic Graph Algorithms.” <i>Algorithmica</i>. Springer Nature, 1998. <a href=\"https://doi.org/10.1007/pl00009186\">https://doi.org/10.1007/pl00009186</a>.","ama":"Alberts D, Henzinger M. Average-case analysis of dynamic graph algorithms. <i>Algorithmica</i>. 1998;20:31-60. doi:<a href=\"https://doi.org/10.1007/pl00009186\">10.1007/pl00009186</a>","ista":"Alberts D, Henzinger M. 1998. Average-case analysis of dynamic graph algorithms. Algorithmica. 20, 31–60."},"article_processing_charge":"No","title":"Average-case analysis of dynamic graph algorithms","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"1998","publication_status":"published","publisher":"Springer Nature","day":"01","type":"journal_article","quality_controlled":"1","date_created":"2022-07-28T06:50:51Z","language":[{"iso":"eng"}],"article_type":"original","_id":"11680","oa_version":"None","scopus_import":"1","doi":"10.1007/pl00009186"},{"month":"11","acknowledgement":".","volume":22,"page":"351-362","author":[{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Fredman, M. L.","first_name":"M. L.","last_name":"Fredman"}],"status":"public","issue":"3","publication":"Algorithmica","intvolume":"        22","keyword":["Dynamic planarity testing","Dynamic connectivity testing","Lower bounds","Cell probe model"],"date_updated":"2024-11-06T12:08:20Z","extern":"1","date_published":"1998-11-01T00:00:00Z","abstract":[{"text":"We prove lower bounds on the complexity of maintaining fully dynamic k -edge or k -vertex connectivity in plane graphs and in (k-1) -vertex connected graphs. We show an amortized lower bound of Ω (log n / {k (log log n} + log b)) per edge insertion, deletion, or query operation in the cell probe model, where b is the word size of the machine and n is the number of vertices in G . We also show an amortized lower bound of Ω (log n /(log log n + log b)) per operation for fully dynamic planarity testing in embedded graphs. These are the first lower bounds for fully dynamic connectivity problems.","lang":"eng"}],"citation":{"ista":"Henzinger M, Fredman ML. 1998. Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica. 22(3), 351–362.","chicago":"Henzinger, Monika, and M. L. Fredman. “Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.” <i>Algorithmica</i>. Springer Nature, 1998. <a href=\"https://doi.org/10.1007/pl00009228\">https://doi.org/10.1007/pl00009228</a>.","ama":"Henzinger M, Fredman ML. Lower bounds for fully dynamic connectivity problems in graphs. <i>Algorithmica</i>. 1998;22(3):351-362. doi:<a href=\"https://doi.org/10.1007/pl00009228\">10.1007/pl00009228</a>","apa":"Henzinger, M., &#38; Fredman, M. L. (1998). Lower bounds for fully dynamic connectivity problems in graphs. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/pl00009228\">https://doi.org/10.1007/pl00009228</a>","short":"M. Henzinger, M.L. Fredman, Algorithmica 22 (1998) 351–362.","mla":"Henzinger, Monika, and M. L. Fredman. “Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.” <i>Algorithmica</i>, vol. 22, no. 3, Springer Nature, 1998, pp. 351–62, doi:<a href=\"https://doi.org/10.1007/pl00009228\">10.1007/pl00009228</a>.","ieee":"M. Henzinger and M. L. Fredman, “Lower bounds for fully dynamic connectivity problems in graphs,” <i>Algorithmica</i>, vol. 22, no. 3. Springer Nature, pp. 351–362, 1998."},"title":"Lower bounds for fully dynamic connectivity problems in graphs","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"publisher":"Springer Nature","year":"1998","publication_status":"published","day":"01","type":"journal_article","quality_controlled":"1","date_created":"2022-07-28T06:58:36Z","language":[{"iso":"eng"}],"article_type":"original","scopus_import":"1","oa_version":"None","_id":"11681","doi":"10.1007/pl00009228"},{"date_published":"1996-03-01T00:00:00Z","citation":{"ista":"Edelsbrunner H, Shah N. 1996. Incremental topological flipping works for regular triangulations. Algorithmica. 15(3), 223–241.","mla":"Edelsbrunner, Herbert, and Nimish Shah. “Incremental Topological Flipping Works for Regular Triangulations.” <i>Algorithmica</i>, vol. 15, no. 3, Springer, 1996, pp. 223–41, doi:<a href=\"https://doi.org/10.1007/BF01975867\">10.1007/BF01975867</a>.","ieee":"H. Edelsbrunner and N. Shah, “Incremental topological flipping works for regular triangulations,” <i>Algorithmica</i>, vol. 15, no. 3. Springer, pp. 223–241, 1996.","short":"H. Edelsbrunner, N. Shah, Algorithmica 15 (1996) 223–241.","apa":"Edelsbrunner, H., &#38; Shah, N. (1996). Incremental topological flipping works for regular triangulations. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/BF01975867\">https://doi.org/10.1007/BF01975867</a>","ama":"Edelsbrunner H, Shah N. Incremental topological flipping works for regular triangulations. <i>Algorithmica</i>. 1996;15(3):223-241. doi:<a href=\"https://doi.org/10.1007/BF01975867\">10.1007/BF01975867</a>","chicago":"Edelsbrunner, Herbert, and Nimish Shah. “Incremental Topological Flipping Works for Regular Triangulations.” <i>Algorithmica</i>. Springer, 1996. <a href=\"https://doi.org/10.1007/BF01975867\">https://doi.org/10.1007/BF01975867</a>."},"abstract":[{"text":"A set of n weighted points in general position in R(d) defines a unique regular triangulation. This paper proves that if the points are added one by one, then flipping in a topological order will succeed in constructing this triangulation. If, in addition, the points are added in a random sequence and the history of the flips is used for locating the next point, then the algorithm takes expected time at most O(n log n + n(inverted left perpendicular d/2 inverted right perpendicular)). Under the assumption that the points and weights are independently and identically distributed, the expected running time is between proportional to and a factor log n more than the expected size of the regular triangulation. The expectation is over choosing the points and over independent coin-flips performed by the algorithm.","lang":"eng"}],"intvolume":"        15","date_updated":"2022-08-09T09:46:07Z","extern":"1","publist_id":"2099","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner"},{"last_name":"Shah","first_name":"Nimish","full_name":"Shah, Nimish"}],"status":"public","publication":"Algorithmica","issue":"3","month":"03","acknowledgement":"National Science Foundation under Grant CCR-8921421, Alan T. Waterman award, Grant CCR-9118874.","volume":15,"page":"223 - 241","language":[{"iso":"eng"}],"article_type":"original","oa_version":"None","scopus_import":"1","_id":"4026","doi":"10.1007/BF01975867","quality_controlled":"1","date_created":"2018-12-11T12:06:31Z","publisher":"Springer","publication_status":"published","year":"1996","day":"01","type":"journal_article","title":"Incremental topological flipping works for regular triangulations","article_processing_charge":"No","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"issn":["0178-4617"]}},{"abstract":[{"lang":"eng","text":"Questions about lines in space arise frequently as subproblems in three-dimensional computational geometry. In this paper we study a number of fundamental combinatorial and algorithmic problems involving arrangements of n lines in three-dimensional space. Our main results include: 1. A tight Θ(n2) bound on the maximum combinatorial description complexity of the set of all oriented lines that have specified orientations relative to the n given lines. 2. A similar bound of Θ(n3) for the complexity of the set of all lines passing above the n given lines. 3. A preprocessing procedure using O(n2+ε) time and storage, for any ε &gt; 0, that builds a structure supporting O(logn)-time queries for testing if a line lies above all the given lines. 4. An algorithm that tests the &quot;towering property&quot; in O(n4/3+ε) time, for any ε &gt; 0: do n given red lines lie all above n given blue lines? The tools used to obtain these and other results include Plücker coordinates for lines in space and ε-nets for various geometric range spaces."}],"citation":{"ista":"Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Stolfi J. 1996. Lines in space: Combinatorics and algorithms. Algorithmica. 15(5), 428–447.","ama":"Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Stolfi J. Lines in space: Combinatorics and algorithms. <i>Algorithmica</i>. 1996;15(5):428-447. doi:<a href=\"https://doi.org/10.1007/BF01955043\">10.1007/BF01955043</a>","chicago":"Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Jorge Stolfi. “Lines in Space: Combinatorics and Algorithms.” <i>Algorithmica</i>. Springer, 1996. <a href=\"https://doi.org/10.1007/BF01955043\">https://doi.org/10.1007/BF01955043</a>.","ieee":"B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Stolfi, “Lines in space: Combinatorics and algorithms,” <i>Algorithmica</i>, vol. 15, no. 5. Springer, pp. 428–447, 1996.","mla":"Chazelle, Bernard, et al. “Lines in Space: Combinatorics and Algorithms.” <i>Algorithmica</i>, vol. 15, no. 5, Springer, 1996, pp. 428–47, doi:<a href=\"https://doi.org/10.1007/BF01955043\">10.1007/BF01955043</a>.","short":"B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, J. Stolfi, Algorithmica 15 (1996) 428–447.","apa":"Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., &#38; Stolfi, J. (1996). Lines in space: Combinatorics and algorithms. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/BF01955043\">https://doi.org/10.1007/BF01955043</a>"},"date_published":"1996-05-01T00:00:00Z","publist_id":"2100","extern":"1","date_updated":"2022-08-09T09:55:46Z","intvolume":"        15","issue":"5","publication":"Algorithmica","status":"public","author":[{"full_name":"Chazelle, Bernard","last_name":"Chazelle","first_name":"Bernard"},{"first_name":"Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"last_name":"Guibas","first_name":"Leonidas","full_name":"Guibas, Leonidas"},{"first_name":"Micha","last_name":"Sharir","full_name":"Sharir, Micha"},{"last_name":"Stolfi","first_name":"Jorge","full_name":"Stolfi, Jorge"}],"page":"428 - 447","acknowledgement":"Work on this paper by Bernard Chazelle has been supported by NSF Grant CCR-87-00917. Work on this paper by Herbert Edelsbrunner has been supported by NSF Grant CCR-87-14565. Work on this paper by Leonidas Guibas has been supported by grants from the Mitsubishi and Toshiba Corporations. Work on this paper by Micha Sharir has been supported by ONR Grant N00014-87-K-0129, by NSF Grants DCR-83-20085 and CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the NCRD — the Israeli National Council for Research and Development, and the EMET Fund of the Israeli Academy of Sciences.","volume":15,"month":"05","doi":"10.1007/BF01955043","_id":"4027","scopus_import":"1","oa_version":"None","article_type":"original","language":[{"iso":"eng"}],"date_created":"2018-12-11T12:06:31Z","quality_controlled":"1","type":"journal_article","day":"01","publication_status":"published","year":"1996","publisher":"Springer","publication_identifier":{"issn":["0178-4617"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","article_processing_charge":"No","title":"Lines in space: Combinatorics and algorithms"},{"intvolume":"        13","quality_controlled":"1","extern":"1","date_updated":"2024-11-06T08:12:13Z","date_created":"2022-07-27T14:50:46Z","date_published":"1995-06-01T00:00:00Z","language":[{"iso":"eng"}],"article_type":"original","_id":"11677","abstract":[{"lang":"eng","text":"We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m 2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently.\r\n\r\nIf the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log2 n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n 2/3 ) per update or query."}],"citation":{"chicago":"Henzinger, Monika. “Fully Dynamic Biconnectivity in Graphs.” <i>Algorithmica</i>. Springer Nature, 1995. <a href=\"https://doi.org/10.1007/bf01189067\">https://doi.org/10.1007/bf01189067</a>.","ama":"Henzinger M. Fully dynamic biconnectivity in graphs. <i>Algorithmica</i>. 1995;13(6):503-538. doi:<a href=\"https://doi.org/10.1007/bf01189067\">10.1007/bf01189067</a>","apa":"Henzinger, M. (1995). Fully dynamic biconnectivity in graphs. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/bf01189067\">https://doi.org/10.1007/bf01189067</a>","ieee":"M. Henzinger, “Fully dynamic biconnectivity in graphs,” <i>Algorithmica</i>, vol. 13, no. 6. Springer Nature, pp. 503–538, 1995.","mla":"Henzinger, Monika. “Fully Dynamic Biconnectivity in Graphs.” <i>Algorithmica</i>, vol. 13, no. 6, Springer Nature, 1995, pp. 503–38, doi:<a href=\"https://doi.org/10.1007/bf01189067\">10.1007/bf01189067</a>.","short":"M. Henzinger, Algorithmica 13 (1995) 503–538.","ista":"Henzinger M. 1995. Fully dynamic biconnectivity in graphs. Algorithmica. 13(6), 503–538."},"oa_version":"None","scopus_import":"1","doi":"10.1007/bf01189067","month":"06","article_processing_charge":"No","volume":13,"title":"Fully dynamic biconnectivity in graphs","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"page":"503-538","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","author":[{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530"}],"publication_status":"published","year":"1995","publisher":"Springer Nature","day":"01","issue":"6","publication":"Algorithmica","type":"journal_article"},{"issue":"2","publication":"Algorithmica","status":"public","author":[{"last_name":"Chazelle","first_name":"Bernard","full_name":"Chazelle, Bernard"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"}],"page":"116 - 132","month":"02","volume":11,"acknowledgement":"Supported in part by the National Science Foundation under Grant CCR-8714565.","abstract":[{"lang":"eng","text":"We consider a variety of problems on the interaction between two sets of line segments in two and three dimensions. These problems range from counting the number of intersecting pairs between m blue segments and n red segments in the plane (assuming that two line segments are disjoint if they have the same color) to finding the smallest vertical distance between two nonintersecting polyhedral terrains in three-dimensional space. We solve these problems efficiently by using a variant of the segment tree. For the three-dimensional problems we also apply a variety of recent combinatorial and algorithmic techniques involving arrangements of lines in three-dimensional space, as developed in a companion paper."}],"citation":{"ama":"Chazelle B, Edelsbrunner H, Guibas L, Sharir M. Algorithms for bichromatic line-segment problems and polyhedral terrains. <i>Algorithmica</i>. 1994;11(2):116-132. doi:<a href=\"https://doi.org/10.1007/BF01182771\">10.1007/BF01182771</a>","chicago":"Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir. “Algorithms for Bichromatic Line-Segment Problems and Polyhedral Terrains.” <i>Algorithmica</i>. Springer, 1994. <a href=\"https://doi.org/10.1007/BF01182771\">https://doi.org/10.1007/BF01182771</a>.","short":"B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, Algorithmica 11 (1994) 116–132.","ieee":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, “Algorithms for bichromatic line-segment problems and polyhedral terrains,” <i>Algorithmica</i>, vol. 11, no. 2. Springer, pp. 116–132, 1994.","mla":"Chazelle, Bernard, et al. “Algorithms for Bichromatic Line-Segment Problems and Polyhedral Terrains.” <i>Algorithmica</i>, vol. 11, no. 2, Springer, 1994, pp. 116–32, doi:<a href=\"https://doi.org/10.1007/BF01182771\">10.1007/BF01182771</a>.","apa":"Chazelle, B., Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1994). Algorithms for bichromatic line-segment problems and polyhedral terrains. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/BF01182771\">https://doi.org/10.1007/BF01182771</a>","ista":"Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1994. Algorithms for bichromatic line-segment problems and polyhedral terrains. Algorithmica. 11(2), 116–132."},"date_published":"1994-02-01T00:00:00Z","extern":"1","date_updated":"2022-06-02T12:25:29Z","publist_id":"2089","intvolume":"        11","day":"01","type":"journal_article","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF01182771"}],"publication_status":"published","year":"1994","publisher":"Springer","publication_identifier":{"issn":["0178-4617"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","article_processing_charge":"No","title":"Algorithms for bichromatic line-segment problems and polyhedral terrains","_id":"4038","oa_version":"None","scopus_import":"1","doi":"10.1007/BF01182771","language":[{"iso":"eng"}],"article_type":"original","date_created":"2018-12-11T12:06:34Z","quality_controlled":"1"},{"intvolume":"        12","publist_id":"2090","extern":"1","date_updated":"2022-06-02T12:41:07Z","date_published":"1994-07-01T00:00:00Z","citation":{"ama":"Chazelle B, Edelsbrunner H, Grigni M, et al. Ray shooting in polygons using geodesic triangulations. <i>Algorithmica</i>. 1994;12(1):54-68. doi:<a href=\"https://doi.org/10.1007/BF01377183\">10.1007/BF01377183</a>","chicago":"Chazelle, Bernard, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, John Hershberger, Micha Sharir, and Jack Snoeyink. “Ray Shooting in Polygons Using Geodesic Triangulations.” <i>Algorithmica</i>. Springer, 1994. <a href=\"https://doi.org/10.1007/BF01377183\">https://doi.org/10.1007/BF01377183</a>.","ieee":"B. Chazelle <i>et al.</i>, “Ray shooting in polygons using geodesic triangulations,” <i>Algorithmica</i>, vol. 12, no. 1. Springer, pp. 54–68, 1994.","mla":"Chazelle, Bernard, et al. “Ray Shooting in Polygons Using Geodesic Triangulations.” <i>Algorithmica</i>, vol. 12, no. 1, Springer, 1994, pp. 54–68, doi:<a href=\"https://doi.org/10.1007/BF01377183\">10.1007/BF01377183</a>.","short":"B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir, J. Snoeyink, Algorithmica 12 (1994) 54–68.","apa":"Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Hershberger, J., Sharir, M., &#38; Snoeyink, J. (1994). Ray shooting in polygons using geodesic triangulations. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/BF01377183\">https://doi.org/10.1007/BF01377183</a>","ista":"Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Hershberger J, Sharir M, Snoeyink J. 1994. Ray shooting in polygons using geodesic triangulations. Algorithmica. 12(1), 54–68."},"abstract":[{"text":"Let P be a simple polygon with n vertices. We present a simple decomposition scheme that partitions the interior of P into O(n) so-called geodesic triangles, so that any line segment interior to P crosses at most 2 log n of these triangles. This decomposition can be used to preprocess P in a very simple manner, so that any ray-shooting query can be answered in time O(log n). The data structure requires O(n) storage and O(n log n) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time to O(n). We also extend our general technique to the case of ray shooting amidst k polygonal obstacles with a total of n edges, so that a query can be answered in O(√ log n) time.","lang":"eng"}],"acknowledgement":"Work by Bernard Chazelle has been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrunner has been supported by NSF Grant CCR-89-21421. Work by Micha Sharir has been supported by ONR Grants N00014-89-J-3042 and N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.","volume":12,"month":"07","page":"54 - 68","status":"public","author":[{"full_name":"Chazelle, Bernard","first_name":"Bernard","last_name":"Chazelle"},{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"last_name":"Grigni","first_name":"Michelangelo","full_name":"Grigni, Michelangelo"},{"full_name":"Guibas, Leonidas","first_name":"Leonidas","last_name":"Guibas"},{"first_name":"John","last_name":"Hershberger","full_name":"Hershberger, John"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"},{"last_name":"Snoeyink","first_name":"Jack","full_name":"Snoeyink, Jack"}],"issue":"1","publication":"Algorithmica","quality_controlled":"1","date_created":"2018-12-11T12:06:35Z","article_type":"original","language":[{"iso":"eng"}],"doi":"10.1007/BF01377183","_id":"4039","oa_version":"None","scopus_import":"1","article_processing_charge":"No","title":"Ray shooting in polygons using geodesic triangulations","publication_identifier":{"issn":["0178-4617"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","year":"1994","publication_status":"published","publisher":"Springer","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF01377183"}],"type":"journal_article","day":"01"},{"doi":"10.1007/BF01840404","scopus_import":"1","oa_version":"None","_id":"4075","article_type":"original","language":[{"iso":"eng"}],"date_created":"2018-12-11T12:06:47Z","quality_controlled":"1","type":"journal_article","day":"01","publisher":"Springer","publication_status":"published","year":"1990","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF01840404"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"title":"Searching for empty convex polygons","article_processing_charge":"No","citation":{"ista":"Dobkin D, Edelsbrunner H, Overmars M. 1990. Searching for empty convex polygons. Algorithmica. 5(4), 561–571.","ieee":"D. Dobkin, H. Edelsbrunner, and M. Overmars, “Searching for empty convex polygons,” <i>Algorithmica</i>, vol. 5, no. 4. Springer, pp. 561–571, 1990.","short":"D. Dobkin, H. Edelsbrunner, M. Overmars, Algorithmica 5 (1990) 561–571.","mla":"Dobkin, David, et al. “Searching for Empty Convex Polygons.” <i>Algorithmica</i>, vol. 5, no. 4, Springer, 1990, pp. 561–71, doi:<a href=\"https://doi.org/10.1007/BF01840404\">10.1007/BF01840404</a>.","apa":"Dobkin, D., Edelsbrunner, H., &#38; Overmars, M. (1990). Searching for empty convex polygons. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/BF01840404\">https://doi.org/10.1007/BF01840404</a>","ama":"Dobkin D, Edelsbrunner H, Overmars M. Searching for empty convex polygons. <i>Algorithmica</i>. 1990;5(4):561-571. doi:<a href=\"https://doi.org/10.1007/BF01840404\">10.1007/BF01840404</a>","chicago":"Dobkin, David, Herbert Edelsbrunner, and Mark Overmars. “Searching for Empty Convex Polygons.” <i>Algorithmica</i>. Springer, 1990. <a href=\"https://doi.org/10.1007/BF01840404\">https://doi.org/10.1007/BF01840404</a>."},"abstract":[{"lang":"eng","text":"A key problem in computational geometry is the identification of subsets of a point set having particular properties. We study this problem for the properties of convexity and emptiness. We show that finding empty triangles is related to the problem of determining pairs of vertices that see each other in a star-shaped polygon. A linear-time algorithm for this problem which is of independent interest yields an optimal algorithm for finding all empty triangles. This result is then extended to an algorithm for finding empty convex r-gons (r&gt; 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned."}],"date_published":"1990-06-01T00:00:00Z","publist_id":"2049","extern":"1","date_updated":"2022-02-21T10:55:13Z","intvolume":"         5","publication":"Algorithmica","issue":"4","author":[{"full_name":"Dobkin, David","last_name":"Dobkin","first_name":"David"},{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"last_name":"Overmars","first_name":"Mark","full_name":"Overmars, Mark"}],"status":"public","page":"561 - 571","acknowledgement":"The first author is pleased to acknowledge support by the National Science Foundation under Grant CCR-8700917. The research of the second author was supported by Amoco Foundation Faculty Development Grant CS 1-6-44862 and by the National Science Foundatio","volume":5,"month":"06"},{"title":"Edge-skeletons in arrangements with applications","article_processing_charge":"No","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"publisher":"Springer","year":"1986","publication_status":"published","day":"01","type":"journal_article","quality_controlled":"1","date_created":"2018-12-11T12:04:04Z","language":[{"iso":"eng"}],"article_type":"original","scopus_import":"1","oa_version":"None","_id":"3580","doi":"10.1007/BF01840438","month":"11","volume":1,"page":"93 - 109","author":[{"last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"}],"status":"public","publication":"Algorithmica","issue":"1-4","intvolume":"         1","date_updated":"2022-02-02T09:36:32Z","extern":"1","publist_id":"2805","date_published":"1986-11-01T00:00:00Z","abstract":[{"text":"An edge-skeleton in an arrangementA(H) of a finite set of planes inE 3 is a connected collection of edges inA(H). We give a method that constructs a skeleton inO(√n logn) time per edge. This method implies new and more efficient algorithms for a number of structures in computational geometry including order-k power diagrams inE 2 and space cutting trees inE 3.\r\nWe also give a novel method for handling special cases which has the potential to substantially decrease the amount of effort needed to implement geometric algorithms.","lang":"eng"}],"citation":{"mla":"Edelsbrunner, Herbert. “Edge-Skeletons in Arrangements with Applications.” <i>Algorithmica</i>, vol. 1, no. 1–4, Springer, 1986, pp. 93–109, doi:<a href=\"https://doi.org/10.1007/BF01840438\">10.1007/BF01840438</a>.","ieee":"H. Edelsbrunner, “Edge-skeletons in arrangements with applications,” <i>Algorithmica</i>, vol. 1, no. 1–4. Springer, pp. 93–109, 1986.","short":"H. Edelsbrunner, Algorithmica 1 (1986) 93–109.","apa":"Edelsbrunner, H. (1986). Edge-skeletons in arrangements with applications. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/BF01840438\">https://doi.org/10.1007/BF01840438</a>","ama":"Edelsbrunner H. Edge-skeletons in arrangements with applications. <i>Algorithmica</i>. 1986;1(1-4):93-109. doi:<a href=\"https://doi.org/10.1007/BF01840438\">10.1007/BF01840438</a>","chicago":"Edelsbrunner, Herbert. “Edge-Skeletons in Arrangements with Applications.” <i>Algorithmica</i>. Springer, 1986. <a href=\"https://doi.org/10.1007/BF01840438\">https://doi.org/10.1007/BF01840438</a>.","ista":"Edelsbrunner H. 1986. Edge-skeletons in arrangements with applications. Algorithmica. 1(1–4), 93–109."}}]