[{"_id":"12432","date_updated":"2025-07-10T11:50:26Z","article_processing_charge":"No","publication_identifier":{"issn":["0272-5428"],"isbn":["9781665455190"]},"citation":{"ama":"Anastos M. Solving the Hamilton cycle problem fast on average. In: <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i>. Vol 2022-October. Institute of Electrical and Electronics Engineers; 2022:919-930. doi:<a href=\"https://doi.org/10.1109/FOCS54457.2022.00091\">10.1109/FOCS54457.2022.00091</a>","mla":"Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i>, vol. 2022–October, Institute of Electrical and Electronics Engineers, 2022, pp. 919–30, doi:<a href=\"https://doi.org/10.1109/FOCS54457.2022.00091\">10.1109/FOCS54457.2022.00091</a>.","short":"M. Anastos, in:, 63rd Annual IEEE Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2022, pp. 919–930.","ista":"Anastos M. 2022. Solving the Hamilton cycle problem fast on average. 63rd Annual IEEE Symposium on Foundations of Computer Science. FOCS: Foundations of Computer Science vol. 2022–October, 919–930.","apa":"Anastos, M. (2022). Solving the Hamilton cycle problem fast on average. In <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i> (Vol. 2022–October, pp. 919–930). Denver, CO, United States: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/FOCS54457.2022.00091\">https://doi.org/10.1109/FOCS54457.2022.00091</a>","chicago":"Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” In <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i>, 2022–October:919–30. Institute of Electrical and Electronics Engineers, 2022. <a href=\"https://doi.org/10.1109/FOCS54457.2022.00091\">https://doi.org/10.1109/FOCS54457.2022.00091</a>.","ieee":"M. Anastos, “Solving the Hamilton cycle problem fast on average,” in <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i>, Denver, CO, United States, 2022, vol. 2022–October, pp. 919–930."},"department":[{"_id":"MaKw"}],"external_id":{"isi":["000909382900084"]},"language":[{"iso":"eng"}],"publication_status":"published","publisher":"Institute of Electrical and Electronics Engineers","date_published":"2022-12-01T00:00:00Z","volume":"2022-October","ec_funded":1,"oa_version":"None","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"63rd Annual IEEE Symposium on Foundations of Computer Science","acknowledgement":"This project has received funding from the European Union’s Horizon 2020\r\nresearch and innovation programme under the Marie Skłodowska-Curie grant\r\nagreement No 101034413","isi":1,"conference":{"end_date":"2022-11-03","start_date":"2022-10-31","name":"FOCS: Foundations of Computer Science","location":"Denver, CO, United States"},"title":"Solving the Hamilton cycle problem fast on average","month":"12","day":"01","page":"919-930","scopus_import":"1","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael","first_name":"Michael","last_name":"Anastos"}],"project":[{"name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"year":"2022","doi":"10.1109/FOCS54457.2022.00091","corr_author":"1","status":"public","quality_controlled":"1","date_created":"2023-01-29T23:00:59Z","abstract":[{"text":"We present CertifyHAM, a deterministic algorithm that takes a graph G as input and either finds a Hamilton cycle of G or outputs that such a cycle does not exist. If G ∼ G(n, p) and p ≥\r\n100 log n/n then the expected running time of CertifyHAM is O(n/p) which is best possible. This improves upon previous results due to Gurevich and Shelah, Thomason and Alon, and\r\nKrivelevich, who proved analogous results for p being constant, p ≥ 12n −1/3 and p ≥ 70n\r\n−1/2 respectively.","lang":"eng"}],"type":"conference"},{"day":"01","scopus_import":"1","page":"720-726","author":[{"last_name":"Ferber","first_name":"Asaf","full_name":"Ferber, Asaf"},{"first_name":"Matthew Alan","last_name":"Kwan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"},{"full_name":"Sauermann, Lisa","first_name":"Lisa","last_name":"Sauermann"}],"doi":"10.1109/FOCS52979.2021.00075","year":"2022","title":"List-decodability with large radius for Reed-Solomon codes","month":"02","related_material":{"record":[{"status":"public","relation":"later_version","id":"10775"}]},"type":"conference","oa":1,"date_created":"2022-04-10T22:01:40Z","abstract":[{"lang":"eng","text":"List-decodability of Reed-Solomon codes has re-ceived a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form r=1−ε for ε tending to zero. Our main result states that there exist Reed-Solomon codes with rate Ω(ε) which are (1−ε,O(1/ε) -list-decodable, meaning that any Hamming ball of radius 1−ε contains at most O(1/ε) codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance."}],"main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2012.10584","open_access":"1"}],"status":"public","arxiv":1,"quality_controlled":"1","language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781665420556"],"issn":["0272-5428"]},"citation":{"chicago":"Ferber, Asaf, Matthew Alan Kwan, and Lisa Sauermann. “List-Decodability with Large Radius for Reed-Solomon Codes.” In <i>62nd Annual IEEE Symposium on Foundations of Computer Science</i>, 2022:720–26. IEEE, 2022. <a href=\"https://doi.org/10.1109/FOCS52979.2021.00075\">https://doi.org/10.1109/FOCS52979.2021.00075</a>.","ieee":"A. Ferber, M. A. Kwan, and L. Sauermann, “List-decodability with large radius for Reed-Solomon codes,” in <i>62nd Annual IEEE Symposium on Foundations of Computer Science</i>, Denver, CO, United States, 2022, vol. 2022, pp. 720–726.","apa":"Ferber, A., Kwan, M. A., &#38; Sauermann, L. (2022). List-decodability with large radius for Reed-Solomon codes. In <i>62nd Annual IEEE Symposium on Foundations of Computer Science</i> (Vol. 2022, pp. 720–726). Denver, CO, United States: IEEE. <a href=\"https://doi.org/10.1109/FOCS52979.2021.00075\">https://doi.org/10.1109/FOCS52979.2021.00075</a>","ama":"Ferber A, Kwan MA, Sauermann L. List-decodability with large radius for Reed-Solomon codes. In: <i>62nd Annual IEEE Symposium on Foundations of Computer Science</i>. Vol 2022. IEEE; 2022:720-726. doi:<a href=\"https://doi.org/10.1109/FOCS52979.2021.00075\">10.1109/FOCS52979.2021.00075</a>","mla":"Ferber, Asaf, et al. “List-Decodability with Large Radius for Reed-Solomon Codes.” <i>62nd Annual IEEE Symposium on Foundations of Computer Science</i>, vol. 2022, IEEE, 2022, pp. 720–26, doi:<a href=\"https://doi.org/10.1109/FOCS52979.2021.00075\">10.1109/FOCS52979.2021.00075</a>.","short":"A. Ferber, M.A. Kwan, L. Sauermann, in:, 62nd Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2022, pp. 720–726.","ista":"Ferber A, Kwan MA, Sauermann L. 2022. List-decodability with large radius for Reed-Solomon codes. 62nd Annual IEEE Symposium on Foundations of Computer Science. FOCS: Foundations of Computer Science vol. 2022, 720–726."},"department":[{"_id":"MaKw"}],"external_id":{"arxiv":["2012.10584"],"isi":["000802209600065"]},"_id":"11145","date_updated":"2025-07-10T11:50:08Z","article_processing_charge":"No","isi":1,"conference":{"end_date":"2022-02-10","location":"Denver, CO, United States","name":"FOCS: Foundations of Computer Science","start_date":"2022-02-07"},"intvolume":"      2022","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"62nd Annual IEEE Symposium on Foundations of Computer Science","date_published":"2022-02-01T00:00:00Z","volume":2022,"oa_version":"Preprint","publication_status":"published","publisher":"IEEE"},{"status":"public","arxiv":1,"quality_controlled":"1","type":"conference","oa":1,"date_created":"2022-08-16T08:14:33Z","abstract":[{"lang":"eng","text":"The decremental single-source shortest paths (SSSP) problem concerns maintaining the distances between a given source node s to every node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be easily solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach (JACM 1981) has been the fastest known algorithm for three decades. With the loss of a (1 + ε)-approximation factor, the running time was recently improved to O(n 2+o(1) ) by Bernstein and Roditty (SODA 2011), and more recently to O(n 1.8+o(1) + m 1+o(1) ) by Henzinger, Krinninger, and Nanongkai (SODA 2014). In this paper, we finally bring the running time of this case down to near-linear: We give a (1 + ε)-approximation algorithm with O(m 1+o(1) ) total update time, thus obtaining near-linear time. Moreover, we obtain O(m 1+o(1) log W) time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn log W) time is the O(mn 0.986 log W)-time algorithm by Henzinger, Krinninger, and Nanongkai (STOC 2014) which works for the general weighted directed case. In contrast to the previous results which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (d, ε)-hop set introduced by Cohen (JACM 2000) in the PRAM literature. A (d, ε)-hop set of a graph G = (V, E) is a set E' of weighted edges such that the distance between any pair of nodes in G can be (1 + ε)-approximated by their d-hop distance (given by a path containing at most d edges) on G'=(V, E∪E'). Our algorithm can maintain an (n o(1) , ε)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain the distances on this hop set, we develop a monotone bounded-hop Even-Shiloach tree. It results from extending and combining the monotone Even-Shiloach tree of Henzinger, Krinninger, and Nanongkai (FOCS 2013) with the bounded-hop SSSP technique of Bernstein (STOC 2013). These two new tools might be of independent interest."}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1402.0054"}],"title":"Decremental single-source shortest paths on undirected graphs in near-linear total update time","month":"10","related_material":{"record":[{"id":"11768","relation":"later_version","status":"public"}]},"day":"01","scopus_import":"1","page":"146-155","author":[{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530"},{"first_name":"Sebastian","last_name":"Krinninger","full_name":"Krinninger, Sebastian"},{"first_name":"Danupon","last_name":"Nanongkai","full_name":"Nanongkai, Danupon"}],"doi":"10.1109/focs.2014.24","year":"2014","date_published":"2014-10-01T00:00:00Z","oa_version":"Preprint","publication_status":"published","publisher":"Institute of Electrical and Electronics Engineers","conference":{"name":"FOCS: Annual Symposium on Foundations of Computer Science","location":"Philadelphia, PA, United States","start_date":"2014-10-18","end_date":"2014-10-21"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"55th Annual Symposium on Foundations of Computer Science","_id":"11855","date_updated":"2024-11-06T12:18:18Z","article_processing_charge":"No","extern":"1","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0272-5428"],"eisbn":["978-1-4799-6517-5"]},"citation":{"short":"M. Henzinger, S. Krinninger, D. Nanongkai, in:, 55th Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2014, pp. 146–155.","ista":"Henzinger M, Krinninger S, Nanongkai D. 2014. Decremental single-source shortest paths on undirected graphs in near-linear total update time. 55th Annual Symposium on Foundations of Computer Science. FOCS: Annual Symposium on Foundations of Computer Science, 146–155.","ama":"Henzinger M, Krinninger S, Nanongkai D. Decremental single-source shortest paths on undirected graphs in near-linear total update time. In: <i>55th Annual Symposium on Foundations of Computer Science</i>. Institute of Electrical and Electronics Engineers; 2014:146-155. doi:<a href=\"https://doi.org/10.1109/focs.2014.24\">10.1109/focs.2014.24</a>","mla":"Henzinger, Monika, et al. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” <i>55th Annual Symposium on Foundations of Computer Science</i>, Institute of Electrical and Electronics Engineers, 2014, pp. 146–55, doi:<a href=\"https://doi.org/10.1109/focs.2014.24\">10.1109/focs.2014.24</a>.","apa":"Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2014). Decremental single-source shortest paths on undirected graphs in near-linear total update time. In <i>55th Annual Symposium on Foundations of Computer Science</i> (pp. 146–155). Philadelphia, PA, United States: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/focs.2014.24\">https://doi.org/10.1109/focs.2014.24</a>","ieee":"M. Henzinger, S. Krinninger, and D. Nanongkai, “Decremental single-source shortest paths on undirected graphs in near-linear total update time,” in <i>55th Annual Symposium on Foundations of Computer Science</i>, Philadelphia, PA, United States, 2014, pp. 146–155.","chicago":"Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” In <i>55th Annual Symposium on Foundations of Computer Science</i>, 146–55. Institute of Electrical and Electronics Engineers, 2014. <a href=\"https://doi.org/10.1109/focs.2014.24\">https://doi.org/10.1109/focs.2014.24</a>."},"external_id":{"arxiv":["1402.0054"]}},{"extern":"1","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0272-5428"],"eisbn":["978-0-7695-5135-7"]},"citation":{"ama":"Henzinger M, Krinninger S, Nanongkai D. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. In: <i>54th Annual Symposium on Foundations of Computer Science</i>. Institute of Electrical and Electronics Engineers; 2013:538-547. doi:<a href=\"https://doi.org/10.1109/focs.2013.64\">10.1109/focs.2013.64</a>","mla":"Henzinger, Monika, et al. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.” <i>54th Annual Symposium on Foundations of Computer Science</i>, Institute of Electrical and Electronics Engineers, 2013, pp. 538–47, doi:<a href=\"https://doi.org/10.1109/focs.2013.64\">10.1109/focs.2013.64</a>.","ista":"Henzinger M, Krinninger S, Nanongkai D. 2013. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. 54th Annual Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science, 538–547.","short":"M. Henzinger, S. Krinninger, D. Nanongkai, in:, 54th Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2013, pp. 538–547.","apa":"Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2013). Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. In <i>54th Annual Symposium on Foundations of Computer Science</i> (pp. 538–547). Berkeley, CA, United States: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/focs.2013.64\">https://doi.org/10.1109/focs.2013.64</a>","chicago":"Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.” In <i>54th Annual Symposium on Foundations of Computer Science</i>, 538–47. Institute of Electrical and Electronics Engineers, 2013. <a href=\"https://doi.org/10.1109/focs.2013.64\">https://doi.org/10.1109/focs.2013.64</a>.","ieee":"M. Henzinger, S. Krinninger, and D. Nanongkai, “Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization,” in <i>54th Annual Symposium on Foundations of Computer Science</i>, Berkeley, CA, United States, 2013, pp. 538–547."},"external_id":{"arxiv":["1308.0776"]},"_id":"11856","article_processing_charge":"No","date_updated":"2024-11-06T12:18:28Z","conference":{"end_date":"2013-10-29","start_date":"2013-10-26","location":"Berkeley, CA, United States","name":"FOCS: Symposium on Foundations of Computer Science"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"54th Annual Symposium on Foundations of Computer Science","date_published":"2013-10-01T00:00:00Z","oa_version":"Preprint","publisher":"Institute of Electrical and Electronics Engineers","publication_status":"published","scopus_import":"1","page":"538-547","day":"01","doi":"10.1109/focs.2013.64","year":"2013","author":[{"orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Krinninger","first_name":"Sebastian","full_name":"Krinninger, Sebastian"},{"full_name":"Nanongkai, Danupon","last_name":"Nanongkai","first_name":"Danupon"}],"title":"Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization","month":"10","type":"conference","oa":1,"date_created":"2022-08-16T08:22:37Z","main_file_link":[{"url":"https://arxiv.org/abs/1308.0776","open_access":"1"}],"abstract":[{"text":"We study dynamic (1 + ϵ)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of Ȏ(mn) and constant query time by Roditty and Zwick (FOCS 2004). The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach (JACM 1981); it has a total update time of O(mn 2 ) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of Ȏ(n 5/2 ) and constant query time that has an additive error of two in addition to the 1 + ϵ multiplicative error. This beats the previous Ȏ(mn) time when m = Ω(n 3/2 ). Note that the additive error is unavoidable since, even in the static case, an O(n 3-δ )-time (a so-called truly sub cubic) combinatorial algorithm with 1 + ϵ multiplicative error cannot have an additive error less than 2 - ϵ, unless we make a major breakthrough for Boolean matrix multiplication (Dor, Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska Williams and Williams FOCS 2010). The algorithm can also be turned into a (2 + ϵ)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3 + ϵ)-approximation algorithm with Ȏ(n 5/2+O(1√(log n)) ) running time of Bernstein and Roditty (SODA 2011) in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of Ȏ(mn) and a query time of O(log log n). The algorithm has a multiplicative error of 1 + ϵ and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in his STOC 2013 paper. In order to achieve our results, we introduce two new techniques: (1) A lazy Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called locally persevering emulator. (2) A derandomization technique based on moving Even-Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest.","lang":"eng"}],"status":"public","quality_controlled":"1","arxiv":1},{"_id":"11682","title":"Parametric and kinetic minimum spanning trees","date_updated":"2024-11-06T12:08:31Z","article_processing_charge":"No","month":"09","extern":"1","language":[{"iso":"eng"}],"day":"01","citation":{"chicago":"Agarwal, P. K., D. EppsteinL. J. Guibas, and Monika Henzinger. “Parametric and Kinetic Minimum Spanning Trees.” In <i>Proceedings of the 39th Annual Symposium on Foundations of Computer Science</i>, 596–605, 1998. <a href=\"https://doi.org/10.1109/SFCS.1998.743510\">https://doi.org/10.1109/SFCS.1998.743510</a>.","ieee":"P. K. Agarwal, D. EppsteinL. J. Guibas, and M. Henzinger, “Parametric and kinetic minimum spanning trees,” in <i>Proceedings of the 39th Annual Symposium on Foundations of Computer Science</i>, Palo Alto, CA, United States, 1998, pp. 596–605.","apa":"Agarwal, P. K., EppsteinL. J. Guibas, D., &#38; Henzinger, M. (1998). Parametric and kinetic minimum spanning trees. In <i>Proceedings of the 39th Annual Symposium on Foundations of Computer Science</i> (pp. 596–605). Palo Alto, CA, United States. <a href=\"https://doi.org/10.1109/SFCS.1998.743510\">https://doi.org/10.1109/SFCS.1998.743510</a>","mla":"Agarwal, P. K., et al. “Parametric and Kinetic Minimum Spanning Trees.” <i>Proceedings of the 39th Annual Symposium on Foundations of Computer Science</i>, 1998, pp. 596–605, doi:<a href=\"https://doi.org/10.1109/SFCS.1998.743510\">10.1109/SFCS.1998.743510</a>.","ama":"Agarwal PK, EppsteinL. J. Guibas D, Henzinger M. Parametric and kinetic minimum spanning trees. In: <i>Proceedings of the 39th Annual Symposium on Foundations of Computer Science</i>. ; 1998:596-605. doi:<a href=\"https://doi.org/10.1109/SFCS.1998.743510\">10.1109/SFCS.1998.743510</a>","ista":"Agarwal PK, EppsteinL. J. Guibas D, Henzinger M. 1998. Parametric and kinetic minimum spanning trees. Proceedings of the 39th Annual Symposium on Foundations of Computer Science. Annual IEEE Symposium on Foundations of Computer Science, 596–605.","short":"P.K. Agarwal, D. EppsteinL. J. Guibas, M. Henzinger, in:, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 596–605."},"publication_identifier":{"issn":["0272-5428"],"isbn":["0-8186-9172-7"]},"page":"596-605","scopus_import":"1","author":[{"last_name":"Agarwal","first_name":"P. K.","full_name":"Agarwal, P. K."},{"last_name":"EppsteinL. J. Guibas","first_name":"D.","full_name":"EppsteinL. J. Guibas, D."},{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"}],"year":"1998","doi":"10.1109/SFCS.1998.743510","date_published":"1998-09-01T00:00:00Z","status":"public","quality_controlled":"1","oa_version":"None","publication_status":"published","type":"conference","conference":{"end_date":"1998-11-11","start_date":"1998-11-08","location":"Palo Alto, CA, United States","name":"Annual IEEE Symposium on Foundations of Computer Science"},"date_created":"2022-07-28T07:21:34Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science","abstract":[{"text":"We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter /spl lambda/ and wish to compute the sequence of minimum spanning trees generated as /spl lambda/ varies. We also consider the kinetic minimum spanning tree problem, in which /spl lambda/ represents time and the graph is subject in addition to changes such as edge insertions, deletions, and modifications of the weight functions as time progresses. We solve both problems in time O(n/sup 2/3/log/sup 4/3/) per combinatorial change in the tree (or randomized O(n/sup 2/3/log/sup 4/3/ n) per change). Our time bounds reduce to O(n/sup 1/2/log/sup 3/2/ n) per change (O(n/sup 1/2/log n) randomized) for planar graphs or other minor-closed families of graphs, and O(n/sup 1/4/log/sup 3/2/ n) per change (O(n/sup 1/4/ log n) randomized) for planar graphs with weight changes but no insertions or deletions.","lang":"eng"}]},{"author":[{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"full_name":"King, V.","first_name":"V.","last_name":"King"}],"year":"1995","doi":"10.1109/SFCS.1995.492668","citation":{"apa":"Henzinger, M., &#38; King, V. (1995). Fully dynamic biconnectivity and transitive closure. In <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i> (pp. 664–672). Milwaukee, WI, United States: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/SFCS.1995.492668\">https://doi.org/10.1109/SFCS.1995.492668</a>","ista":"Henzinger M, King V. 1995. Fully dynamic biconnectivity and transitive closure. Proceedings of IEEE 36th Annual Foundations of Computer Science. Foundations of Computer Science, 664–672.","short":"M. Henzinger, V. King, in:, Proceedings of IEEE 36th Annual Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 1995, pp. 664–672.","ama":"Henzinger M, King V. Fully dynamic biconnectivity and transitive closure. In: <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>. Institute of Electrical and Electronics Engineers; 1995:664-672. doi:<a href=\"https://doi.org/10.1109/SFCS.1995.492668\">10.1109/SFCS.1995.492668</a>","mla":"Henzinger, Monika, and V. King. “Fully Dynamic Biconnectivity and Transitive Closure.” <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, Institute of Electrical and Electronics Engineers, 1995, pp. 664–72, doi:<a href=\"https://doi.org/10.1109/SFCS.1995.492668\">10.1109/SFCS.1995.492668</a>.","ieee":"M. Henzinger and V. King, “Fully dynamic biconnectivity and transitive closure,” in <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, Milwaukee, WI, United States, 1995, pp. 664–672.","chicago":"Henzinger, Monika, and V. King. “Fully Dynamic Biconnectivity and Transitive Closure.” In <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, 664–72. Institute of Electrical and Electronics Engineers, 1995. <a href=\"https://doi.org/10.1109/SFCS.1995.492668\">https://doi.org/10.1109/SFCS.1995.492668</a>."},"publication_identifier":{"issn":["0272-5428"],"isbn":["0-8186-7183-1"]},"day":"01","page":"664-672","scopus_import":"1","language":[{"iso":"eng"}],"extern":"1","date_updated":"2024-11-04T11:41:41Z","article_processing_charge":"No","month":"11","_id":"11684","title":"Fully dynamic biconnectivity and transitive closure","abstract":[{"lang":"eng","text":"This paper presents an algorithm for the fully dynamic biconnectivity problem whose running time is exponentially faster than all previously known solutions. It is the first dynamic algorithm that answers biconnectivity queries in time O(log/sup 2/n) in a n-node graph and can be updated after an edge insertion or deletion in polylogarithmic time. Our algorithm is a Las-Vegas style randomized algorithm with the update time amortized update time O(log/sup 4/n). Only recently the best deterministic result for this problem was improved to O(/spl radic/nlog/sup 2/n). We also give the first fully dynamic and a novel deletions-only transitive closure (i.e. directed connectivity) algorithms. These are randomized Monte Carlo algorithms. Let n be the number of nodes in the graph and let m/spl circ/ be the average number of edges in the graph during the whole update sequence: The fully dynamic algorithms achieve (1) query time O(n/logn) and update time O(m/spl circ//spl radic/nlog/sup 2/n+n); or (2) query time O(n/logn) and update time O(nm/spl circ//sup /spl mu/-1/)log/sup 2/n=O(nm/spl circ//sup 0.58/log/sup 2/n), where /spl mu/ is the exponent for boolean matrix multiplication (currently /spl mu/=2.38). The deletions-only algorithm answers queries in time O(n/logn). Its amortized update time is O(nlog/sup 2/n)."}],"publication":"Proceedings of IEEE 36th Annual Foundations of Computer Science","date_created":"2022-07-28T11:28:13Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"1995-10-23","name":"Foundations of Computer Science","location":"Milwaukee, WI, United States","end_date":"1995-10-25"},"type":"conference","publication_status":"published","publisher":"Institute of Electrical and Electronics Engineers","quality_controlled":"1","oa_version":"None","date_published":"1995-11-01T00:00:00Z","status":"public"},{"day":"01","citation":{"ieee":"H. Edelsbrunner, “Algebraic decomposition of non-convex polyhedra,” in <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, Milwaukee, WI, United States of America, 1995, pp. 248–257.","chicago":"Edelsbrunner, Herbert. “Algebraic Decomposition of Non-Convex Polyhedra.” In <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, 248–57. IEEE, 1995.","ista":"Edelsbrunner H. 1995. Algebraic decomposition of non-convex polyhedra. Proceedings of IEEE 36th Annual Foundations of Computer Science. FOCS: Foundations of Computer Science, 248–257.","short":"H. Edelsbrunner, in:, Proceedings of IEEE 36th Annual Foundations of Computer Science, IEEE, 1995, pp. 248–257.","mla":"Edelsbrunner, Herbert. “Algebraic Decomposition of Non-Convex Polyhedra.” <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, IEEE, 1995, pp. 248–57.","ama":"Edelsbrunner H. Algebraic decomposition of non-convex polyhedra. In: <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>. IEEE; 1995:248-257.","apa":"Edelsbrunner, H. (1995). Algebraic decomposition of non-convex polyhedra. In <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i> (pp. 248–257). Milwaukee, WI, United States of America: IEEE."},"publication_identifier":{"issn":["0272-5428"]},"page":"248 - 257","author":[{"orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"}],"year":"1995","publist_id":"2093","extern":"1","language":[{"iso":"eng"}],"_id":"4034","title":"Algebraic decomposition of non-convex polyhedra","date_updated":"2022-06-13T12:27:11Z","article_processing_charge":"No","month":"10","date_created":"2018-12-11T12:06:33Z","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication":"Proceedings of IEEE 36th Annual Foundations of Computer Science","abstract":[{"lang":"eng","text":"Any arbitrary polyhedron P contained as a subset within Rd can be written as algebraic sum of simple terms, each an integer multiple of the intersection of d or fewer half-spaces defined by facets of P. P can be non-convex and can have holes of any kind. Among the consequences of this result are a short boolean formula for P, a fast parallel algorithm for point classification, and a new proof of the Gram-Sommerville angle relation."}],"main_file_link":[{"url":"https://ieeexplore.ieee.org/abstract/document/492480"}],"type":"conference","acknowledgement":"The author thanks Bei-Fang Chen, Siu-Wing Cheng, David Dobkin, Nikolai Dolbilin, Ping Fu, Sergei Ryshkov, and Vadim Shapiro for discussions on the topic of this paper.","conference":{"end_date":"1995-10-25","location":"Milwaukee, WI, United States of America","name":"FOCS: Foundations of Computer Science","start_date":"1995-10-23"},"publication_status":"published","publisher":"IEEE","date_published":"1995-10-01T00:00:00Z","status":"public","quality_controlled":"1","oa_version":"None"},{"status":"public","date_published":"1995-11-01T00:00:00Z","oa_version":"None","quality_controlled":"1","publisher":"IEEE","publication_status":"published","type":"conference","conference":{"start_date":"1995-10-23","name":"FOCS: Foundations of Computer Science","location":"Milwaukee, WI, United States of America","end_date":"1995-10-25"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-11T12:09:10Z","publication":"Proceedings of IEEE 36th Annual Foundations of Computer Science","abstract":[{"lang":"eng","text":"We present algorithms for computing similarity relations of labeled graphs. Similarity relations have applications for the refinement and verification of reactive systems. For finite graphs, we present an O(mn) algorithm for computing the similarity relation of a graph with n vertices and m edges (assuming m⩾n). For effectively presented infinite graphs, we present a symbolic similarity-checking procedure that terminates if a finite similarity relation exists. We show that 2D rectangular automata, which model discrete reactive systems with continuous environments, define effectively presented infinite graphs with finite similarity relations. It follows that the refinement problem and the ∀CTL* model-checking problem are decidable for 2D rectangular automata"}],"title":"Computing simulations on finite and infinite graphs","_id":"4498","article_processing_charge":"No","month":"11","date_updated":"2024-11-06T12:02:08Z","extern":"1","publist_id":"231","language":[{"iso":"eng"}],"scopus_import":"1","page":"453 - 462","publication_identifier":{"issn":["0272-5428"],"isbn":["0818671831"]},"citation":{"apa":"Henzinger, M., Henzinger, T. A., &#38; Kopke, P. (1995). Computing simulations on finite and infinite graphs. In <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i> (pp. 453–462). Milwaukee, WI, United States of America: IEEE. <a href=\"https://doi.org/10.1109/SFCS.1995.492576\">https://doi.org/10.1109/SFCS.1995.492576</a>","ama":"Henzinger M, Henzinger TA, Kopke P. Computing simulations on finite and infinite graphs. In: <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>. IEEE; 1995:453-462. doi:<a href=\"https://doi.org/10.1109/SFCS.1995.492576\">10.1109/SFCS.1995.492576</a>","mla":"Henzinger, Monika, et al. “Computing Simulations on Finite and Infinite Graphs.” <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, IEEE, 1995, pp. 453–62, doi:<a href=\"https://doi.org/10.1109/SFCS.1995.492576\">10.1109/SFCS.1995.492576</a>.","ista":"Henzinger M, Henzinger TA, Kopke P. 1995. Computing simulations on finite and infinite graphs. Proceedings of IEEE 36th Annual Foundations of Computer Science. FOCS: Foundations of Computer Science, 453–462.","short":"M. Henzinger, T.A. Henzinger, P. Kopke, in:, Proceedings of IEEE 36th Annual Foundations of Computer Science, IEEE, 1995, pp. 453–462.","chicago":"Henzinger, Monika, Thomas A Henzinger, and Peter Kopke. “Computing Simulations on Finite and Infinite Graphs.” In <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, 453–62. IEEE, 1995. <a href=\"https://doi.org/10.1109/SFCS.1995.492576\">https://doi.org/10.1109/SFCS.1995.492576</a>.","ieee":"M. Henzinger, T. A. Henzinger, and P. Kopke, “Computing simulations on finite and infinite graphs,” in <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, Milwaukee, WI, United States of America, 1995, pp. 453–462."},"day":"01","year":"1995","doi":"10.1109/SFCS.1995.492576","author":[{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A"},{"last_name":"Kopke","first_name":"Peter","full_name":"Kopke, Peter"}]},{"doi":"10.1109/SFCS.1987.44","year":"1987","author":[{"last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pach, János","first_name":"János","last_name":"Pach"},{"first_name":"Jacob","last_name":"Schwartz","full_name":"Schwartz, Jacob"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"}],"page":"27 - 37","scopus_import":"1","publication_identifier":{"issn":["0272-5428"],"isbn":["0-8186-0807-2"]},"citation":{"mla":"Edelsbrunner, Herbert, et al. “On the Lower Envelope of Bivariate Functions and Its Applications.” <i>28th Annual Symposium on Foundations of Computer Science </i>, IEEE, 1987, pp. 27–37, doi:<a href=\"https://doi.org/10.1109/SFCS.1987.44\">10.1109/SFCS.1987.44</a>.","ama":"Edelsbrunner H, Pach J, Schwartz J, Sharir M. On the lower envelope of bivariate functions and its applications. In: <i>28th Annual Symposium on Foundations of Computer Science </i>. IEEE; 1987:27-37. doi:<a href=\"https://doi.org/10.1109/SFCS.1987.44\">10.1109/SFCS.1987.44</a>","ista":"Edelsbrunner H, Pach J, Schwartz J, Sharir M. 1987. On the lower envelope of bivariate functions and its applications. 28th Annual Symposium on Foundations of Computer Science . FOCS: Foundations of Computer Science, 27–37.","short":"H. Edelsbrunner, J. Pach, J. Schwartz, M. Sharir, in:, 28th Annual Symposium on Foundations of Computer Science , IEEE, 1987, pp. 27–37.","apa":"Edelsbrunner, H., Pach, J., Schwartz, J., &#38; Sharir, M. (1987). On the lower envelope of bivariate functions and its applications. In <i>28th Annual Symposium on Foundations of Computer Science </i> (pp. 27–37). Los Angeles, CA, USA: IEEE. <a href=\"https://doi.org/10.1109/SFCS.1987.44\">https://doi.org/10.1109/SFCS.1987.44</a>","chicago":"Edelsbrunner, Herbert, János Pach, Jacob Schwartz, and Micha Sharir. “On the Lower Envelope of Bivariate Functions and Its Applications.” In <i>28th Annual Symposium on Foundations of Computer Science </i>, 27–37. IEEE, 1987. <a href=\"https://doi.org/10.1109/SFCS.1987.44\">https://doi.org/10.1109/SFCS.1987.44</a>.","ieee":"H. Edelsbrunner, J. Pach, J. Schwartz, and M. Sharir, “On the lower envelope of bivariate functions and its applications,” in <i>28th Annual Symposium on Foundations of Computer Science </i>, Los Angeles, CA, USA, 1987, pp. 27–37."},"day":"14","language":[{"iso":"eng"}],"extern":"1","publist_id":"2871","article_processing_charge":"No","month":"10","date_updated":"2022-02-07T15:14:55Z","title":"On the lower envelope of bivariate functions and its applications","_id":"3514","main_file_link":[{"url":"https://ieeexplore.ieee.org/document/4568253?denied="}],"abstract":[{"text":"We consider the problem of obtaining sharp (nearly quadratic) bounds for the combinatorial complexity of the lower envelope (i.e. pointwise minimum) of a collection of n bivariate (or generally multi-variate) continuous and &quot;simple&quot; functions, and of designing efficient algorithms for the calculation of this envelope. This problem generalizes the well-studied univariate case (whose analysis is based on the theory of Davenport-Schinzel sequences), but appears to be much more difficult and still largely unsolved. It is a central problem that arises in many areas in computational and combinatorial geometry, and has numerous applications including generalized planar Voronoi diagrams, hidden surface elimination for intersecting surfaces, purely translational motion planning, finding common transversals of polyhedra, and more. In this abstract we provide several partial solutions and generalizations of this problem, and apply them to the problems mentioned above. The most significant of our results is that the lower envelope of n triangles in three dimensions has combinatorial complexity at most O(n2α(n)) (where α(n) is the extremely slowly growing inverse of Ackermann's function), that this bound is tight in the worst case, and that this envelope can be calculated in time O(n2α(n)).","lang":"eng"}],"publication":"28th Annual Symposium on Foundations of Computer Science ","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","date_created":"2018-12-11T12:03:44Z","conference":{"end_date":"1987-10-14","start_date":"1987-10-12","name":"FOCS: Foundations of Computer Science","location":"Los Angeles, CA, USA"},"type":"conference","publisher":"IEEE","publication_status":"published","oa_version":"None","quality_controlled":"1","date_published":"1987-10-14T00:00:00Z","status":"public"}]