[{"citation":{"chicago":"Henzinger, Monika, and Jan Arne Telle. “Faster Algorithms for the Nonemptiness of Streett Automata and for Communication Protocol Pruning.” In <i>5th Scandinavian Workshop on Algorithm Theory</i>, 1097:16–27. Springer Nature, 1996. <a href=\"https://doi.org/10.1007/3-540-61422-2_117\">https://doi.org/10.1007/3-540-61422-2_117</a>.","apa":"Henzinger, M., &#38; Telle, J. A. (1996). Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning. In <i>5th Scandinavian Workshop on Algorithm Theory</i> (Vol. 1097, pp. 16–27). Reykjavik, Iceland: Springer Nature. <a href=\"https://doi.org/10.1007/3-540-61422-2_117\">https://doi.org/10.1007/3-540-61422-2_117</a>","ama":"Henzinger M, Telle JA. Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning. In: <i>5th Scandinavian Workshop on Algorithm Theory</i>. Vol 1097. Springer Nature; 1996:16–27. doi:<a href=\"https://doi.org/10.1007/3-540-61422-2_117\">10.1007/3-540-61422-2_117</a>","short":"M. Henzinger, J.A. Telle, in:, 5th Scandinavian Workshop on Algorithm Theory, Springer Nature, 1996, pp. 16–27.","mla":"Henzinger, Monika, and Jan Arne Telle. “Faster Algorithms for the Nonemptiness of Streett Automata and for Communication Protocol Pruning.” <i>5th Scandinavian Workshop on Algorithm Theory</i>, vol. 1097, Springer Nature, 1996, pp. 16–27, doi:<a href=\"https://doi.org/10.1007/3-540-61422-2_117\">10.1007/3-540-61422-2_117</a>.","ieee":"M. Henzinger and J. A. Telle, “Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning,” in <i>5th Scandinavian Workshop on Algorithm Theory</i>, Reykjavik, Iceland, 1996, vol. 1097, pp. 16–27.","ista":"Henzinger M, Telle JA. 1996. Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning. 5th Scandinavian Workshop on Algorithm Theory. SWAT: Scandinavian Workshop on Algorithm Theory, LNCS, vol. 1097, 16–27."},"quality_controlled":"1","volume":1097,"publication_identifier":{"eissn":["1611-3349"],"eisbn":["9783540685296"],"issn":["0302-9743"],"isbn":["9783540614227"]},"publisher":"Springer Nature","status":"public","scopus_import":"1","alternative_title":["LNCS"],"intvolume":"      1097","day":"01","oa_version":"None","article_processing_charge":"No","type":"conference","_id":"11804","month":"07","author":[{"orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"last_name":"Telle","first_name":"Jan Arne","full_name":"Telle, Jan Arne"}],"title":"Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning","date_created":"2022-08-11T13:42:42Z","date_updated":"2024-11-06T12:13:51Z","abstract":[{"text":"This paper shows how a general technique, called lock-step search, used in dynamic graph algorithms, can be used to improve the running time of two problems arising in program verification and communication protocol design.\r\n(1)We consider the nonemptiness problem for Streett automata: We are given a directed graph G = (V, E) with n = ¦V¦ and m = ¦E¦, and a collection of pairs of subsets of vertices, called Streett pairs,〈L i , U i 〉, i = 1.k. The question is whether G has a cycle (not necessarily simple) which, for each 1 ≤ i ≤ k, if it contains a vertex from L i then it also contains a vertex of U i . Let b=Σ i=1..k |L i |+|U i |. The previously best algorithm takes time O((m + b) min{n, k}). We present an algorithm that takes time 𝑂(𝑚min{𝑚𝑙𝑜𝑔𝑛,‾‾‾‾‾‾√𝑘,𝑛}+𝑏𝑚𝑖𝑛{𝑙𝑜𝑔𝑛,𝑘}).\r\n(2)In communication protocol pruning we are given a directed graph G = (V, E) with l special vertices. The problem is to efficiently maintain the strongly-connected components of the special vertices on a restricted set of edge deletions. Let m i be the number of edges in the strongly connected component of the ith special vertex. The previously best algorithm repeatedly recomputes the strongly-connected components which leads to a running time of O(Σ i m 2i). We present an algorithm with time 𝑂(𝑙√∑𝑖𝑚1.5𝑖).","lang":"eng"}],"extern":"1","publication_status":"published","year":"1996","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"publication":"5th Scandinavian Workshop on Algorithm Theory","date_published":"1996-07-01T00:00:00Z","conference":{"start_date":"1996-07-03","end_date":"1996-07-05","location":"Reykjavik, Iceland","name":"SWAT: Scandinavian Workshop on Algorithm Theory"},"page":"16–27","doi":"10.1007/3-540-61422-2_117"},{"conference":{"end_date":"1996-07-12","location":"Paderborn, Germany","name":"ICALP: International Colloquium on Automata, Languages, and Programming","start_date":"1996-07-08"},"page":"290-299","doi":"10.1007/3-540-61440-0_136","date_published":"1996-07-01T00:00:00Z","language":[{"iso":"eng"}],"publication":"23rd International Colloquium on Automata, Languages, and Programming","publication_status":"published","extern":"1","year":"1996","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We state a new sampling lemma and use it to improve the running time of dynamic graph algorithms.\r\n\r\nFor the dynamic connectivity problem the previously best randomized algorithm takes expected time O(log3 n) per update, amortized over Ω(m) updates. Using the new sampling lemma, we improve its running time to O(log2 n). There exists a lower bound in the cell probe model for the time per operation of Ω(log n/ log log n) for this problem.\r\n\r\nSimilarly improved running times are achieved for 2-edge connectivity, k-weight minimum spanning tree, and bipartiteness.","lang":"eng"}],"date_updated":"2024-11-06T12:25:11Z","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530"},{"full_name":"Thorup, Mikkel","first_name":"Mikkel","last_name":"Thorup"}],"title":"Improved sampling with applications to dynamic graph algorithms","date_created":"2022-08-18T06:42:24Z","month":"07","oa_version":"None","article_processing_charge":"No","_id":"11910","type":"conference","day":"01","alternative_title":["LNCS"],"intvolume":"      1099","scopus_import":"1","publisher":"Springer Nature","status":"public","publication_identifier":{"isbn":["9783540614401"],"issn":["0302-9743"],"eisbn":["9783540685807"],"eissn":["1611-3349"]},"citation":{"ista":"Henzinger M, Thorup M. 1996. Improved sampling with applications to dynamic graph algorithms. 23rd International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 1099, 290–299.","mla":"Henzinger, Monika, and Mikkel Thorup. “Improved Sampling with Applications to Dynamic Graph Algorithms.” <i>23rd International Colloquium on Automata, Languages, and Programming</i>, vol. 1099, Springer Nature, 1996, pp. 290–99, doi:<a href=\"https://doi.org/10.1007/3-540-61440-0_136\">10.1007/3-540-61440-0_136</a>.","short":"M. Henzinger, M. Thorup, in:, 23rd International Colloquium on Automata, Languages, and Programming, Springer Nature, 1996, pp. 290–299.","ieee":"M. Henzinger and M. Thorup, “Improved sampling with applications to dynamic graph algorithms,” in <i>23rd International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 1996, vol. 1099, pp. 290–299.","apa":"Henzinger, M., &#38; Thorup, M. (1996). Improved sampling with applications to dynamic graph algorithms. In <i>23rd International Colloquium on Automata, Languages, and Programming</i> (Vol. 1099, pp. 290–299). Paderborn, Germany: Springer Nature. <a href=\"https://doi.org/10.1007/3-540-61440-0_136\">https://doi.org/10.1007/3-540-61440-0_136</a>","ama":"Henzinger M, Thorup M. Improved sampling with applications to dynamic graph algorithms. In: <i>23rd International Colloquium on Automata, Languages, and Programming</i>. Vol 1099. Springer Nature; 1996:290-299. doi:<a href=\"https://doi.org/10.1007/3-540-61440-0_136\">10.1007/3-540-61440-0_136</a>","chicago":"Henzinger, Monika, and Mikkel Thorup. “Improved Sampling with Applications to Dynamic Graph Algorithms.” In <i>23rd International Colloquium on Automata, Languages, and Programming</i>, 1099:290–99. Springer Nature, 1996. <a href=\"https://doi.org/10.1007/3-540-61440-0_136\">https://doi.org/10.1007/3-540-61440-0_136</a>."},"quality_controlled":"1","volume":1099},{"language":[{"iso":"eng"}],"publication":"3rd Annual European Symposium on Algorithms","year":"1995","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","publication_status":"published","doi":"10.1007/3-540-60313-1_142","page":"171–184","conference":{"location":"Corfu, Greece","end_date":"1995-09-27","name":"ESA: European Symposium on Algorithms","start_date":"1995-09-25"},"date_published":"1995-09-01T00:00:00Z","date_created":"2022-08-11T14:09:52Z","title":"Certificates and fast algorithms for biconnectivity in fully-dynamic graphs","author":[{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"full_name":"Poutré, Han","first_name":"Han","last_name":"Poutré"}],"month":"09","abstract":[{"lang":"eng","text":"In this paper, we present sparse certificates for biconnectivity together with algorithms for updating these certificates. We thus obtain fully-dynamic algorithms for biconnectivity in graphs that run in O(√n log n log⌈m/n⌉) amortized time per operation, where m is the number of edges and n is the number of nodes in the graph. This improves upon the results in [11], in which algorithms were presented running in O(√m) amortized time, and solves the open problem to find certificates to speed up biconnectivity, as stated in [2]."}],"date_updated":"2024-11-06T12:16:15Z","intvolume":"       979","alternative_title":["LNCS"],"scopus_import":"1","type":"conference","_id":"11805","oa_version":"None","article_processing_charge":"No","day":"01","volume":979,"citation":{"mla":"Henzinger, Monika, and Han Poutré. “Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs.” <i>3rd Annual European Symposium on Algorithms</i>, vol. 979, Springer Nature, 1995, pp. 171–184, doi:<a href=\"https://doi.org/10.1007/3-540-60313-1_142\">10.1007/3-540-60313-1_142</a>.","short":"M. Henzinger, H. Poutré, in:, 3rd Annual European Symposium on Algorithms, Springer Nature, 1995, pp. 171–184.","ieee":"M. Henzinger and H. Poutré, “Certificates and fast algorithms for biconnectivity in fully-dynamic graphs,” in <i>3rd Annual European Symposium on Algorithms</i>, Corfu, Greece, 1995, vol. 979, pp. 171–184.","ista":"Henzinger M, Poutré H. 1995. Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. 3rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 979, 171–184.","chicago":"Henzinger, Monika, and Han Poutré. “Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs.” In <i>3rd Annual European Symposium on Algorithms</i>, 979:171–184. Springer Nature, 1995. <a href=\"https://doi.org/10.1007/3-540-60313-1_142\">https://doi.org/10.1007/3-540-60313-1_142</a>.","ama":"Henzinger M, Poutré H. Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. In: <i>3rd Annual European Symposium on Algorithms</i>. Vol 979. Springer Nature; 1995:171–184. doi:<a href=\"https://doi.org/10.1007/3-540-60313-1_142\">10.1007/3-540-60313-1_142</a>","apa":"Henzinger, M., &#38; Poutré, H. (1995). Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. In <i>3rd Annual European Symposium on Algorithms</i> (Vol. 979, pp. 171–184). Corfu, Greece: Springer Nature. <a href=\"https://doi.org/10.1007/3-540-60313-1_142\">https://doi.org/10.1007/3-540-60313-1_142</a>"},"quality_controlled":"1","status":"public","publisher":"Springer Nature","publication_identifier":{"isbn":["9783540603139"],"issn":["0302-9743"],"eisbn":["9783540449133"],"eissn":["1611-3349"]}},{"extern":"1","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"1995","language":[{"iso":"eng"}],"publication":"22nd International Colloquium on Automata, Languages and Programming","date_published":"1995-07-01T00:00:00Z","conference":{"start_date":"1995-07-10","name":"ICALP: International Colloquium on Automata, Languages, and Programming","end_date":"1995-07-14","location":"Szeged, Hungary"},"page":"280–291","doi":"10.1007/3-540-60084-1_81","month":"07","author":[{"orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"}],"title":"Approximating minimum cuts under insertions","date_created":"2022-08-11T14:17:33Z","date_updated":"2024-11-06T08:23:27Z","abstract":[{"lang":"eng","text":"This paper presents insertions-only algorithms for maintaining the exact and approximate size of the minimum edge cut and the minimum vertex cut of a graph. The algorithms output the approximate or exact size k in time O(1) or O(log n) and a cut of size k in time linear in its size. The amortized time per insertion is O(1/ε 2) for a (2+ε)-approximation, O((log λ)((log n)/ε)2) for a (1+ε)-approximation, and O(λ log n) for the exact size of the minimum edge cut, where n is the number of nodes in the graph, λ is the size of the minimum cut and ε>0. The (2+ε)-approximation algorithm and the exact algorithm are deterministic, the (1+ε)-approximation algorithm is randomized. The algorithms are optimal in the sense that the time needed for m insertions matches the time needed by the best static algorithm on a m-edge graph. We also present a static 2-approximation algorithm for the size κ of the minimum vertex cut in a graph, which takes time O(n 2 min(√n,κ)). This is a factor of κ faster than the best algorithm for computing the exact size, which takes time O(κ 2 n 2 +κ 3 n 1.5). We give an insertionsonly algorithm for maintaining a (2+ε)-approximation of the minimum vertex cut with amortized insertion time O(n(logκk)/ε)."}],"scopus_import":"1","alternative_title":["LNCS"],"intvolume":"       944","day":"01","oa_version":"None","article_processing_charge":"No","_id":"11806","type":"conference","quality_controlled":"1","citation":{"ieee":"M. Henzinger, “Approximating minimum cuts under insertions,” in <i>22nd International Colloquium on Automata, Languages and Programming</i>, Szeged, Hungary, 1995, vol. 944, pp. 280–291.","short":"M. Henzinger, in:, 22nd International Colloquium on Automata, Languages and Programming, Springer Nature, 1995, pp. 280–291.","mla":"Henzinger, Monika. “Approximating Minimum Cuts under Insertions.” <i>22nd International Colloquium on Automata, Languages and Programming</i>, vol. 944, Springer Nature, 1995, pp. 280–291, doi:<a href=\"https://doi.org/10.1007/3-540-60084-1_81\">10.1007/3-540-60084-1_81</a>.","ista":"Henzinger M. 1995. Approximating minimum cuts under insertions. 22nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 944, 280–291.","chicago":"Henzinger, Monika. “Approximating Minimum Cuts under Insertions.” In <i>22nd International Colloquium on Automata, Languages and Programming</i>, 944:280–291. Springer Nature, 1995. <a href=\"https://doi.org/10.1007/3-540-60084-1_81\">https://doi.org/10.1007/3-540-60084-1_81</a>.","apa":"Henzinger, M. (1995). Approximating minimum cuts under insertions. In <i>22nd International Colloquium on Automata, Languages and Programming</i> (Vol. 944, pp. 280–291). Szeged, Hungary: Springer Nature. <a href=\"https://doi.org/10.1007/3-540-60084-1_81\">https://doi.org/10.1007/3-540-60084-1_81</a>","ama":"Henzinger M. Approximating minimum cuts under insertions. In: <i>22nd International Colloquium on Automata, Languages and Programming</i>. Vol 944. Springer Nature; 1995:280–291. doi:<a href=\"https://doi.org/10.1007/3-540-60084-1_81\">10.1007/3-540-60084-1_81</a>"},"volume":944,"publication_identifier":{"eissn":["1611-3349"],"eisbn":["9783540600848"],"isbn":["9783540494256"],"issn":["0302-9743"]},"publisher":"Springer Nature","status":"public"}]