Monika Henzinger

Henzinger_Monika Group

199 Publications

Mark all

[199]
2024 | Conference Paper | IST-REx-ID: 15008 | OA
Goranci G, Henzinger MH, Räcke H, Sachdeva S, Sricharan AR. Electrical flows for polylogarithmic competitive oblivious routing. In: 15th Innovations in Theoretical Computer Science Conference. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ITCS.2024.55
[Published Version] View | Files available | DOI | arXiv
 
[198]
2024 | Conference Paper | IST-REx-ID: 14769 | OA
Henzinger MH, Saulpic D, Sidl L. Experimental evaluation of fully dynamic k-means via coresets. In: 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments. Society for Industrial & Applied Mathematics; 2024:220-233. doi:10.1137/1.9781611977929.17
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[197]
2024 | Journal Article | IST-REx-ID: 15121 | OA
Zheng DW, Henzinger MH. Multiplicative auction algorithm for approximate maximum weight bipartite matching. Mathematical Programming. 2024. doi:10.1007/s10107-024-02066-3
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[196]
2024 | Conference Paper | IST-REx-ID: 15093 | OA
Cultrera di Montesano S, Edelsbrunner H, Henzinger MH, Ost L. Dynamically maintaining the persistent homology of time series. In: Woodruff DP, ed. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics; 2024:243-295. doi:10.1137/1.9781611977912.11
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[195]
2024 | Conference Paper | IST-REx-ID: 15253 | OA
Henzinger MH, Upadhyay J, Upadhyay S. A unifying framework for differentially private sums under continual observation. In: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 2024. Society for Industrial and Applied Mathematics; 2024:995-1018. doi:10.1137/1.9781611977912.38
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[194]
2023 | Conference Paper | IST-REx-ID: 12760 | OA
Henzinger MH, Neumann S, Räcke H, Schmid S. Dynamic maintenance of monotone dynamic programs and applications. In: 40th International Symposium on Theoretical Aspects of Computer Science. Vol 254. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.STACS.2023.36
[Published Version] View | Files available | DOI | arXiv
 
[193]
2023 | Conference Paper | IST-REx-ID: 14085 | OA
Goranci G, Henzinger MH. Efficient data structures for incremental exact and approximate maximum flow. In: 50th International Colloquium on Automata, Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.69
[Published Version] View | Files available | DOI
 
[192]
2023 | Conference Paper | IST-REx-ID: 14086 | OA
Henzinger MH, Liu P, Vondrák J, Zheng DW. Faster submodular maximization for several classes of matroids. In: 50th International Colloquium on Automata, Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.74
[Published Version] View | Files available | DOI | arXiv
 
[191]
2023 | Conference Paper | IST-REx-ID: 14462 | OA
Fichtenberger H, Henzinger MH, Upadhyay J. Constant matters: Fine-grained error bound on differentially private continual observation. In: Proceedings of the 40th International Conference on Machine Learning. Vol 202. ML Research Press; 2023:10072-10092.
[Published Version] View | Download Published Version (ext.)
 
[190]
2023 | Journal Article | IST-REx-ID: 14558
Bhattacharya S, Henzinger MH, Nanongkai D, Wu X. Deterministic near-optimal approximation algorithms for dynamic set cover. SIAM Journal on Computing. 2023;52(5):1132-1192. doi:10.1137/21M1428649
View | DOI
 
[189]
2023 | Journal Article | IST-REx-ID: 14043 | OA
Henzinger MH, Jin B, Peng R, Williamson DP. A combinatorial cut-toggling algorithm for solving Laplacian linear systems. Algorithmica. 2023;85:2680-3716. doi:10.1007/s00453-023-01154-8
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[188]
2023 | Conference Paper | IST-REx-ID: 13236 | OA
Zheng DW, Henzinger MH. Multiplicative auction algorithm for approximate maximum weight bipartite matching. In: International Conference on Integer Programming and Combinatorial Optimization. Vol 13904. Springer Nature; 2023:453-465. doi:10.1007/978-3-031-32726-1_32
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[187]
2022 | Journal Article | IST-REx-ID: 11662
Henzinger MH, Peng P. Constant-time Dynamic (Δ +1)-Coloring. ACM Transactions on Algorithms. 2022;18(2). doi:10.1145/3501403
View | DOI
 
[186]
2022 | Conference Paper | IST-REx-ID: 11812 | OA
Hanauer K, Henzinger MH, Hua QC. Fully dynamic four-vertex subgraph counting. In: 1st Symposium on Algorithmic Foundations of Dynamic Networks. Vol 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.SAND.2022.18
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[185]
2022 | Conference Paper | IST-REx-ID: 11808 | OA
Hanauer K, Henzinger MH, Schulz C. Recent advances in fully dynamic graph algorithms. In: 1st Symposium on Algorithmic Foundations of Dynamic Networks. Vol 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.SAND.2022.1
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[184]
2022 | Conference Paper | IST-REx-ID: 11918
Henzinger MH, Lincoln A, Saha B. The complexity of average-case dynamic subgraph counting. In: 33rd Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2022:459-498. doi:10.1137/1.9781611977073.23
View | DOI
 
[183]
2022 | Conference Paper | IST-REx-ID: 11930 | OA
Henzinger MH, Noe A, Schulz C. Practical fully dynamic minimum cut algorithms. In: 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2022:13-26. doi:10.1137/1.9781611977042.2
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[182]
2022 | Preprint | IST-REx-ID: 14236 | OA
Goranci G, Henzinger MH. Incremental approximate maximum flow in m1/2+o(1) update time. arXiv. doi:10.48550/arXiv.2211.09606
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[181]
2021 | Conference Paper | IST-REx-ID: 10054 | OA
Chatterjee K, Henzinger MH, Kale SS, Svozil A. Faster algorithms for bounded liveness in graphs and game graphs. In: 48th International Colloquium on Automata, Languages, and Programming. Vol 198. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.ICALP.2021.124
[Published Version] View | Files available | DOI
 
[180]
2021 | Conference Paper | IST-REx-ID: 11649 | OA
Henzinger MH, Paz A, Schmid S. On the complexity of weight-dynamic network algorithms. In: IFIP Networking Conference. Institute of Electrical and Electronics Engineers; 2021. doi:10.23919/ifipnetworking52078.2021.9472803
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[179]
2021 | Journal Article | IST-REx-ID: 11663 | OA
Bernstein A, Forster S, Henzinger MH. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms. 2021;17(4). doi:10.1145/3469833
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[178]
2021 | Journal Article | IST-REx-ID: 11756 | OA
Henzinger MH, Peng P. Constant-time dynamic weight approximation for minimum spanning forest. Information and Computation. 2021;281(12). doi:10.1016/j.ic.2021.104805
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[177]
2021 | Conference Paper | IST-REx-ID: 11771 | OA
Henzinger MH, Wu X. Upper and lower bounds for fully retroactive graph problems. In: 17th International Symposium on Algorithms and Data Structures. Vol 12808. Springer Nature; 2021:471–484. doi:10.1007/978-3-030-83508-8_34
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[176]
2021 | Conference Paper | IST-REx-ID: 11814 | OA
Fichtenberger H, Henzinger MH, Ost W. Differentially private algorithms for graphs under continual observation. In: 29th Annual European Symposium on Algorithms. Vol 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.ESA.2021.42
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[175]
2021 | Journal Article | IST-REx-ID: 11886 | OA
Henzinger MH, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. 2021;50(3):STOC16-98-STOC16-137. doi:10.1137/16m1097808
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[174]
2021 | Conference Paper | IST-REx-ID: 11919 | OA
Bergamaschi T, Henzinger MH, Gutenberg MP, Williams VV, Wein N. New techniques and fine-grained hardness for dynamic near-additive spanners. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2021:1836-1855. doi:10.1137/1.9781611976465.110
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[173]
2021 | Conference Paper | IST-REx-ID: 11923 | OA
Henzinger MH, Neumann S, Räcke H, Schmid S. Tight bounds for online graph partitioning. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2021:2799-2818. doi:10.1137/1.9781611976465.166
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[172]
2021 | Conference Paper | IST-REx-ID: 11920 | OA
Bhattacharya S, Henzinger MH, Nanongkai D, Wu X. Dynamic set cover: Improved amortized and worst-case update time. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2021:2537-2549. doi:10.1137/1.9781611976465.150
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[171]
2021 | Conference Paper | IST-REx-ID: 11931 | OA
Goranci G, Henzinger MH, Leniowski D, Schulz C, Svozil A. Fully dynamic k-center clustering in low dimensional metrics. In: 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2021:143-153. doi:10.1137/1.9781611976472.11
[Published Version] View | DOI | Download Published Version (ext.)
 
[170]
2021 | Conference Paper | IST-REx-ID: 10002 | OA
Chatterjee K, Dvorak W, Henzinger MH, Svozil A. Symbolic time and space tradeoffs for probabilistic verification. In: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science. Institute of Electrical and Electronics Engineers; 2021:1-13. doi:10.1109/LICS52264.2021.9470739
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[169]
2021 | Journal Article | IST-REx-ID: 9293 | OA
Chatterjee K, Dvořák W, Henzinger MH, Svozil A. Algorithms and conditional lower bounds for planning problems. Artificial Intelligence. 2021;297(8). doi:10.1016/j.artint.2021.103499
[Preprint] View | Files available | DOI | Download Preprint (ext.) | WoS | arXiv
 
[168]
2020 | Journal Article | IST-REx-ID: 11675 | OA
Bhattacharya S, Chakrabarty D, Henzinger MH. Deterministic dynamic matching in O(1) update time. Algorithmica. 2020;82(4):1057-1080. doi:10.1007/s00453-019-00630-4
[Published Version] View | DOI | Download Published Version (ext.)
 
[167]
2020 | Journal Article | IST-REx-ID: 11674 | OA
Henzinger MH, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum of radii. Algorithmica. 2020;82(11):3183-3194. doi:10.1007/s00453-020-00721-7
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[166]
2020 | Conference Paper | IST-REx-ID: 11818 | OA
Henzinger MH, Kale S. Fully-dynamic coresets. In: 28th Annual European Symposium on Algorithms. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.ESA.2020.57
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[165]
2020 | Conference Paper | IST-REx-ID: 11816 | OA
Henzinger MH, Shahbaz K, Paul R, Schulz C. Dynamic matching algorithms in practice. In: 8th Annual European Symposium on Algorithms. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.ESA.2020.58
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[164]
2020 | Conference Paper | IST-REx-ID: 11824 | OA
Henzinger MH, Neumann S, Wiese A. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.51
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[163]
2020 | Conference Paper | IST-REx-ID: 11822 | OA
Hanauer K, Henzinger MH, Schulz C. Faster fully dynamic transitive closure in practice. In: 18th International Symposium on Experimental Algorithms. Vol 160. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SEA.2020.14
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[162]
2020 | Conference Paper | IST-REx-ID: 11825 | OA
Henzinger MH, Peng P. Constant-time dynamic (Δ+1)-coloring. In: 37th International Symposium on Theoretical Aspects of Computer Science. Vol 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.STACS.2020.53
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[161]
2020 | Conference Paper | IST-REx-ID: 11819 | OA
Henzinger MH, Noe A, Schulz C, Strash D. Finding all global minimum cuts in practice. In: 28th Annual European Symposium on Algorithms. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.ESA.2020.59
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[160]
2020 | Conference Paper | IST-REx-ID: 11852 | OA
Chen L, Goranci G, Henzinger MH, Peng R, Saranurak T. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In: 61st Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 2020:1135-1146. doi:10.1109/focs46700.2020.00109
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[159]
2020 | Conference Paper | IST-REx-ID: 11880 | OA
Hanauer K, Henzinger MH, Schulz C. Fully dynamic single-source reachability in practice: An experimental study. In: 2020 Symposium on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2020:106-119. doi:10.1137/1.9781611976007.9
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[158]
2020 | Conference Paper | IST-REx-ID: 11881 | OA
Henzinger MH, Noe A, Schulz C. Shared-memory branch-and-reduce for multiterminal cuts. In: 2020 Symposium on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2020:42-55. doi:10.1137/1.9781611976007.4
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[157]
2020 | Journal Article | IST-REx-ID: 11889
Henzinger MH, Rao S, Wang D. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. 2020;49(1):1-36. doi:10.1137/18m1180335
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[156]
2020 | Journal Article | IST-REx-ID: 11894 | OA
Goranci G, Henzinger MH, Peng P. Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics. 2020;34(1):130-162. doi:10.1137/17m1163153
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[155]
2019 | Conference Paper | IST-REx-ID: 11826 | OA
Ancona B, Henzinger MH, Roditty L, Williams VV, Wein N. Algorithms and hardness for diameter in dynamic graphs. In: 46th International Colloquium on Automata, Languages, and Programming. Vol 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.ICALP.2019.13
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[154]
2019 | Conference Paper | IST-REx-ID: 11850 | OA
Henzinger MH, Neumann S, Schmid S. Efficient distributed workload (re-)embedding. In: SIGMETRICS’19: International Conference on Measurement and Modeling of Computer Systems. Association for Computing Machinery; 2019:43–44. doi:10.1145/3309697.3331503
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[153]
2019 | Book Chapter | IST-REx-ID: 11847
Biedermann S, Henzinger MH, Schulz C, Schuster B. Vienna Graph Clustering. In: Canzar S, Rojas Ringeling F, eds. Protein-Protein Interaction Networks. Vol 2074. MIMB. Springer Nature; 2019:215–231. doi:10.1007/978-1-4939-9873-9_16
View | DOI | PubMed | Europe PMC
 
[152]
2019 | Conference Paper | IST-REx-ID: 11853 | OA
Bhattacharya S, Henzinger MH, Nanongkai D. A new deterministic algorithm for dynamic set cover. In: 60th Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 2019:406-423. doi:10.1109/focs.2019.00033
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[151]
2019 | Conference Paper | IST-REx-ID: 11851
Henzinger MH, Noe A, Schulz C. Shared-memory exact minimum cuts. In: 33rd International Parallel and Distributed Processing Symposium. Institute of Electrical and Electronics Engineers; 2019. doi:10.1109/ipdps.2019.00013
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[150]
2019 | Conference Paper | IST-REx-ID: 11865 | OA
Daga M, Henzinger MH, Nanongkai D, Saranurak T. Distributed edge connectivity in sublinear time. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery; 2019:343–354. doi:10.1145/3313276.3316346
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[149]
2019 | Conference Paper | IST-REx-ID: 11871 | OA
Bernstein A, Forster S, Henzinger MH. A deamortization approach for dynamic spanner and dynamic maximal matching. In: 30th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2019:1899-1918. doi:10.1137/1.9781611975482.115
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[148]
2019 | Journal Article | IST-REx-ID: 11898 | OA
Bhattacharya S, Henzinger MH, Neumann S. New amortized cell-probe lower bounds for dynamic problems. Theoretical Computer Science. 2019;779:72-87. doi:10.1016/j.tcs.2019.01.043
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[147]
2019 | Conference Paper | IST-REx-ID: 6887 | OA
Chatterjee K, Dvorák W, Henzinger MH, Svozil A. Near-linear time algorithms for Streett objectives in graphs and MDPs. In: Leibniz International Proceedings in Informatics. Vol 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.CONCUR.2019.7
[Published Version] View | Files available | DOI
 
[146]
2018 | Conference Paper | IST-REx-ID: 10883 | OA
Chatterjee K, Dvořák W, Henzinger MH, Svozil A. Quasipolynomial set-based symbolic algorithms for parity games. In: 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning. Vol 57. EasyChair; 2018:233-253. doi:10.29007/5z5k
[Published Version] View | Files available | DOI | arXiv
 
[145]
2018 | Journal Article | IST-REx-ID: 11657 | OA
Henzinger MH, Noe A, Schulz C, Strash D. Practical minimum cut algorithms. ACM Journal of Experimental Algorithmics. 2018;23:1-22. doi:10.1145/3274662
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[144]
2018 | Journal Article | IST-REx-ID: 11667 | OA
Dütting P, Henzinger MH, Starnberger M. Valuation compressions in VCG-based combinatorial auctions. ACM Transactions on Economics and Computation. 2018;6(2). doi:10.1145/3232860
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[143]
2018 | Journal Article | IST-REx-ID: 11664 | OA
Goranci G, Henzinger MH, Thorup M. Incremental exact min-cut in polylogarithmic amortized update time. ACM Transactions on Algorithms. 2018;14(2). doi:10.1145/3174803
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[142]
2018 | Journal Article | IST-REx-ID: 11757 | OA
Bhattacharya S, Henzinger MH, Italiano G. Dynamic algorithms via the primal-dual method. Information and Computation. 2018;261(08):219-239. doi:10.1016/j.ic.2018.02.005
[Published Version] View | DOI | Download Published Version (ext.)
 
[141]
2018 | Conference Paper | IST-REx-ID: 11828 | OA
Goranci G, Henzinger MH, Peng P. Dynamic effective resistances and approximate schur complement on separable graphs. In: 26th Annual European Symposium on Algorithms. Vol 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.ESA.2018.40
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[140]
2018 | Conference Paper | IST-REx-ID: 11827 | OA
Goranci G, Henzinger MH, Leniowski D. A tree structure for dynamic facility location. In: 26th Annual European Symposium on Algorithms. Vol 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.ESA.2018.39
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[139]
2018 | Journal Article | IST-REx-ID: 11768 | OA
Henzinger MH, Krinninger S, Nanongkai D. Decremental single-source shortest paths on undirected graphs in near-linear total update time. Journal of the ACM. 2018;65(6):1-40. doi:10.1145/3218657
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[138]
2018 | Conference Paper | IST-REx-ID: 11872 | OA
Bhattacharya S, Chakrabarty D, Henzinger MH, Nanongkai D. Dynamic algorithms for graph coloring. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2018:1-20. doi:10.1137/1.9781611975031.1
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[137]
2018 | Conference Paper | IST-REx-ID: 11882 | OA
Henzinger MH, Noe A, Schulz C, Strash D. Practical minimum cut algorithms. In: 20th Workshop on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2018:48-61. doi:10.1137/1.9781611975055.5
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[136]
2018 | Journal Article | IST-REx-ID: 11890 | OA
Bhattacharya S, Henzinger MH, Italiano GF. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 2018;47(3):859-887. doi:10.1137/140998925
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[135]
2018 | Conference Paper | IST-REx-ID: 11911 | OA
Biedermann S, Henzinger MH, Schulz C, Schuster B. Memetic graph clustering. In: 17th International Symposium on Experimental Algorithms. Vol 103. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.SEA.2018.3
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[134]
2018 | Conference Paper | IST-REx-ID: 310 | OA
Chatterjee K, Dvorák W, Henzinger MH, Loitzenbauer V. Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety, and diameter. In: ACM; 2018:2341-2356. doi:10.1137/1.9781611975031.151
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[133]
2018 | Conference Paper | IST-REx-ID: 141 | OA
Chatterjee K, Henzinger MH, Loitzenbauer V, Oraee S, Toman V. Symbolic algorithms for graphs and Markov decision processes with fairness objectives. In: Vol 10982. Springer; 2018:178-197. doi:10.1007/978-3-319-96142-2_13
[Published Version] View | Files available | DOI | WoS
 
[132]
2018 | Conference Paper | IST-REx-ID: 35 | OA
Chatterjee K, Dvorák W, Henzinger MH, Svozil A. Algorithms and conditional lower bounds for planning problems. In: 28th International Conference on Automated Planning and Scheduling . AAAI Press; 2018.
View | Files available | Download None (ext.) | WoS | arXiv
 
[131]
2017 | Conference Paper | IST-REx-ID: 11651 | OA
Wang D, Fountoulakis K, Henzinger MH, Mahoney MW, Rao Satish. Capacity releasing diffusion for speed and locality. In: Proceedings of the 34th International Conference on Machine Learning. Vol 70. ML Research Press; 2017:3598-3607.
[Published Version] View | Download Published Version (ext.) | arXiv
 
[130]
2017 | Journal Article | IST-REx-ID: 11665 | OA
Henzinger MH, Krinninger S, Nanongkai D. Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks. ACM Transactions on Algorithms. 2017;13(4). doi:10.1145/3146550
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[129]
2017 | Journal Article | IST-REx-ID: 11676 | OA
Dvořák W, Henzinger MH, Williamson DP. Maximizing a submodular function with viability constraints. Algorithmica. 2017;77(1):152-172. doi:10.1007/s00453-015-0066-y
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[128]
2017 | Conference Paper | IST-REx-ID: 11772
Henzinger MH. The state of the art in dynamic graph algorithms. In: 44th International Conference on Current Trends in Theory and Practice of Computer Science. Vol 10706. Springer Nature; 2017:40–44. doi:10.1007/978-3-319-73117-9_3
View | DOI
 
[127]
2017 | Conference Paper | IST-REx-ID: 11829 | OA
Henzinger MH, Lincoln A, Neumann S, Vassilevska Williams V. Conditional hardness for sensitivity problems. In: 8th Innovations in Theoretical Computer Science Conference. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ITCS.2017.26
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[126]
2017 | Conference Paper | IST-REx-ID: 11833 | OA
Goranci G, Henzinger MH, Peng P. The power of vertex sparsifiers in dynamic graph algorithms. In: 25th Annual European Symposium on Algorithms. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.45
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[125]
2017 | Conference Paper | IST-REx-ID: 11832 | OA
Henzinger MH, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum of radii. In: 25th Annual European Symposium on Algorithms. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.48
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[124]
2017 | Conference Paper | IST-REx-ID: 11874 | OA
Bhattacharya S, Henzinger MH, Nanongkai D. Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 0. Society for Industrial and Applied Mathematics; 2017:470-489. doi:10.1137/1.9781611974782.30
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[123]
2017 | Conference Paper | IST-REx-ID: 11873 | OA
Henzinger MH, Rao S, Wang D. Local flow partitioning for faster edge connectivity. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2017:1919-1938. doi:10.1137/1.9781611974782.125
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[122]
2017 | Conference Paper | IST-REx-ID: 11831 | OA
Goranci G, Henzinger MH, Peng P. Improved guarantees for vertex sparsification in planar graphs. In: 25th Annual European Symposium on Algorithms. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.44
[Published Version] View | Files available | DOI | Download Published Version (ext.) | arXiv
 
[121]
2017 | Journal Article | IST-REx-ID: 11903 | OA
Bhattacharya S, Dvořák W, Henzinger MH, Starnberger M. Welfare maximization with friends-of-friends network externalities. Theory of Computing Systems. 2017;61(4):948-986. doi:10.1007/s00224-017-9759-8
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[120]
2017 | Conference Paper | IST-REx-ID: 12571 | OA
Bhattacharya S, Chakrabarty D, Henzinger MH. Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. In: 19th International Conference on Integer Programming and Combinatorial Optimization. Vol 10328. Springer Nature; 2017:86-98. doi:10.1007/978-3-319-59250-3_8
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[119]
2017 | Journal Article | IST-REx-ID: 464 | OA
Chatterjee K, Henzinger MH, Loitzenbauer V. Improved algorithms for parity and Streett objectives. Logical Methods in Computer Science. 2017;13(3). doi:10.23638/LMCS-13(3:26)2017
[Published Version] View | Files available | DOI | arXiv
 
[118]
2017 | Conference Paper | IST-REx-ID: 552 | OA
Chatterjee K, Henzinger MH, Svozil A. Faster algorithms for mean-payoff parity games. In: Leibniz International Proceedings in Informatics. Vol 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.MFCS.2017.39
[Published Version] View | Files available | DOI
 
[117]
2017 | Conference Paper | IST-REx-ID: 6519 | OA
Chatterjee K, Dvorák W, Henzinger MH, Loitzenbauer V. Improved set-based symbolic algorithms for parity games. In: Vol 82. Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik; 2017. doi:10.4230/LIPICS.CSL.2017.18
[Published Version] View | Files available | DOI
 
[116]
2016 | Conference Paper | IST-REx-ID: 1068 | OA
Chatterjee K, Dvorák W, Henzinger MH, Loitzenbauer V. Conditionally optimal algorithms for generalized Büchi Games. In: Vol 58. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPIcs.MFCS.2016.25
[Published Version] View | Files available | DOI
 
[115]
2016 | Conference Paper | IST-REx-ID: 1140 | OA
Chatterjee K, Dvoák W, Henzinger MH, Loitzenbauer V. Model and objective separation with conditional lower bounds: disjunction is harder than conjunction. In: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE; 2016:197-206. doi:10.1145/2933575.2935304
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[114]
2016 | Conference Paper | IST-REx-ID: 11836 | OA
Cheung YK, Goranci G, Henzinger MH. Graph minors for preserving terminal distances approximately - lower and upper bounds. In: 43rd International Colloquium on Automata, Languages, and Programming. Vol 55. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPICS.ICALP.2016.131
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[113]
2016 | Conference Paper | IST-REx-ID: 11834 | OA
Goranci G, Henzinger MH, Thorup M. Incremental exact min-cut in poly-logarithmic amortized update time. In: 24th Annual European Symposium on Algorithms. Vol 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPICS.ESA.2016.46
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[112]
2016 | Conference Paper | IST-REx-ID: 11835 | OA
Henzinger MH, Neumann S. Incremental and fully dynamic subgraph connectivity for emergency planning. In: 24th Annual European Symposium on Algorithms. Vol 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPICS.ESA.2016.48
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[111]
2016 | Conference Paper | IST-REx-ID: 11866 | OA
Henzinger MH, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In: 48th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery; 2016:489-498. doi:10.1145/2897518.2897638
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[110]
2016 | Conference Paper | IST-REx-ID: 11867 | OA
Bhattacharya S, Henzinger MH, Nanongkai D. New deterministic approximation algorithms for fully dynamic matching. In: 48th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery; 2016:398-411. doi:10.1145/2897518.2897568
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[109]
2016 | Journal Article | IST-REx-ID: 11891 | OA
Henzinger MH, Krinninger S, Nanongkai D. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing. 2016;45(3):947-1006. doi:10.1137/140957299
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[108]
2015 | Journal Article | IST-REx-ID: 11668 | OA
Colini-Baldeschi R, Leonardi S, Henzinger MH, Starnberger M. On multiple keyword sponsored search auctions with budgets. ACM Transactions on Economics and Computation. 2015;4(1). doi:10.1145/2818357
[Submitted Version] View | DOI | Download Submitted Version (ext.)
 
[107]
2015 | Journal Article | IST-REx-ID: 11669 | OA
Dütting P, Henzinger MH, Starnberger M. Auctions for heterogeneous items and budget limits. ACM Transactions on Economics and Computation. 2015;4(1). doi:10.1145/2818351
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[106]
2015 | Journal Article | IST-REx-ID: 11670
Dütting P, Henzinger MH, Weber I. An expressive mechanism for auctions on the web. ACM Transactions on Economics and Computation. 2015;4(1). doi:10.1145/2716312
View | DOI
 
[105]
2015 | Conference Paper | IST-REx-ID: 11774 | OA
Cheung YK, Henzinger MH, Hoefer M, Starnberger M. Combinatorial auctions with conflict-based externalities. In: 11th International Conference on Web and Internet Economics. Vol 9470. Springer Nature; 2015:230–243. doi:10.1007/978-3-662-48995-6_17
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[104]
2015 | Conference Paper | IST-REx-ID: 11773 | OA
Ben-Zwi O, Henzinger MH, Loitzenbauer V. Ad exchange: Envy-free auctions with mediators. In: 11th International Conference on Web and Internet Economics. Vol 9470. Springer Nature; 2015:104–117. doi:10.1007/978-3-662-48995-6_8
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[103]
2015 | Conference Paper | IST-REx-ID: 11785 | OA
Henzinger MH, Krinninger S, Nanongkai D. Improved algorithms for decremental single-source reachability on directed graphs. In: 42nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:725-736. doi:10.1007/978-3-662-47672-7_59
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[102]
2015 | Conference Paper | IST-REx-ID: 11787 | OA
Henzinger MH, Krinninger S, Loitzenbauer V. Finding 2-edge and 2-vertex strongly connected components in quadratic time. In: 2nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:713-724. doi:10.1007/978-3-662-47672-7_58
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[101]
2015 | Conference Paper | IST-REx-ID: 11788 | OA
Dvořák W, Henzinger MH. Online ad assignment with an ad exchange. In: 12th International Workshop of Approximation and Online Algorithms. Vol 8952. Springer Nature; 2015:156–167. doi:10.1007/978-3-319-18263-6_14
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[100]
2015 | Conference Paper | IST-REx-ID: 11786 | OA
Bhattacharya S, Henzinger MH, Italiano GF. Design of dynamic algorithms via primal-dual method. In: 42nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:206-218. doi:10.1007/978-3-662-47672-7_17
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[99]
2015 | Journal Article | IST-REx-ID: 11845 | OA
Chernomor O, Minh BQ, Forest F, et al. Split diversity in constrained conservation prioritization using integer linear programming. Methods in Ecology and Evolution. 2015;6(1):83-91. doi:10.1111/2041-210x.12299
[Published Version] View | Files available | DOI | PubMed | Europe PMC
 
[98]
2015 | Conference Paper | IST-REx-ID: 11868 | OA
Henzinger MH, Krinninger S, Nanongkai D, Saranurak T. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In: 47th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2015. doi:10.1145/2746539.2746609
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[97]
2015 | Conference Paper | IST-REx-ID: 11869 | OA
Bhattacharya S, Henzinger MH, Nanongkai D, Tsourakakis C. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: 47th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2015:173-182. doi:10.1145/2746539.2746592
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[96]
2015 | Conference Paper | IST-REx-ID: 11837 | OA
Bhattacharya S, Dvorák W, Henzinger MH, Starnberger Martin. Welfare maximization with friends-of-friends network externalities. In: 32nd International Symposium on Theoretical Aspects of Computer Science. Vol 30. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:90-102. doi:10.4230/LIPICS.STACS.2015.90
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[95]
2015 | Journal Article | IST-REx-ID: 11901 | OA
Henzinger MH, Loitzenbauer V. Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. 2015;573:1-15. doi:10.1016/j.tcs.2015.01.033
View | DOI | Download None (ext.)
 
[94]
2015 | Conference Paper | IST-REx-ID: 1661 | OA
Chatterjee K, Henzinger MH, Loitzenbauer V. Improved algorithms for one-pair and k-pair Streett objectives. In: Proceedings - Symposium on Logic in Computer Science. Vol 2015-July. IEEE; 2015. doi:10.1109/LICS.2015.34
[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.)
 
[93]
2014 | Conference Paper | IST-REx-ID: 11789 | OA
Charikar M, Henzinger MH, Nguyễn HL. Online bipartite matching with decomposable weights. In: 22nd Annual European Symposium on Algorithms. Vol 8737. Springer Nature; 2014:260-271. doi:10.1007/978-3-662-44777-2_22
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[92]
2014 | Conference Paper | IST-REx-ID: 11790
Cigler L, Dvořák W, Henzinger MH, Starnberger M. Limiting price discrimination when selling products with positive network externalities. In: 10th International Conference of Web and Internet Economics. Vol 8877. Springer Nature; 2014:44-57. doi:10.1007/978-3-319-13129-0_4
View | DOI
 
[91]
2014 | Conference Paper | IST-REx-ID: 11855 | OA
Henzinger MH, Krinninger S, Nanongkai D. Decremental single-source shortest paths on undirected graphs in near-linear total update time. In: 55th Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 2014:146-155. doi:10.1109/focs.2014.24
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[90]
2014 | Conference Paper | IST-REx-ID: 11870 | OA
Henzinger MH, Krinninger S, Nanongkai D. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In: 46th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2014. doi:10.1145/2591796.2591869
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[89]
2014 | Conference Paper | IST-REx-ID: 11876 | OA
Henzinger MH, Krinninger S, Nanongkai D. A subquadratic-time algorithm for decremental single-source shortest paths. In: 25th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2014:1053-1072. doi:10.1137/1.9781611973402.79
[Published Version] View | DOI | Download Published Version (ext.)
 
[88]
2014 | Conference Paper | IST-REx-ID: 11875 | OA
Bhattacharya S, Henzinger MH, Italiano GF. Deterministic fully dynamic data structures for vertex cover and matching. In: 26th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2014:785-804. doi:10.1137/1.9781611973730.54
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[87]
2014 | Journal Article | IST-REx-ID: 1375 | OA
Chatterjee K, Henzinger MH, Krinninger S, Loitzenbauer V, Raskin M. Approximating the minimum cycle mean. Theoretical Computer Science. 2014;547(C):104-116. doi:10.1016/j.tcs.2014.06.031
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[86]
2014 | Journal Article | IST-REx-ID: 2141 | OA
Chatterjee K, Henzinger MH. Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition. Journal of the ACM. 2014;61(3). doi:10.1145/2597631
[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.)
 
[85]
2014 | Journal Article | IST-REx-ID: 535 | OA
Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. Polynomial-time algorithms for energy games with special weight structures. Algorithmica. 2014;70(3):457-492. doi:10.1007/s00453-013-9843-7
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[84]
2013 | Journal Article | IST-REx-ID: 11671
Baykan E, Weber I, Henzinger MH. A comprehensive study of techniques for URL-based web page language classification. ACM Transactions on the Web. 2013;7(1). doi:10.1145/2435215.2435218
View | DOI
 
[83]
2013 | Journal Article | IST-REx-ID: 11759 | OA
Dütting P, Henzinger MH, Weber I. Sponsored search, market equilibria, and the Hungarian Method. Information Processing Letters. 2013;113(3):67-73. doi:10.1016/j.ipl.2012.11.006
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[82]
2013 | Conference Paper | IST-REx-ID: 11793 | OA
Henzinger MH, Krinninger S, Nanongkai D. Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks. In: 40th International Colloquium on Automata, Languages, and Programming. Vol 7966. Springer Nature; 2013:607–619. doi:10.1007/978-3-642-39212-2_53
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[81]
2013 | Conference Paper | IST-REx-ID: 11791 | OA
Dütting P, Henzinger MH, Starnberger M. Valuation compressions in VCG-based combinatorial auctions. In: 9th International Conference on Web and Internet Economics. Vol 8289. Springer Nature; 2013:146–159. doi:10.1007/978-3-642-45046-4_13
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[80]
2013 | Conference Paper | IST-REx-ID: 11792 | OA
Dvořák W, Henzinger MH, Williamson DP. Maximizing a submodular function with viability constraints. In: 21st Annual European Symposium on Algorithms. Vol 8125. Springer Nature; 2013:409-420. doi:10.1007/978-3-642-40450-4_35
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[79]
2013 | Conference Paper | IST-REx-ID: 11856 | OA
Henzinger MH, Krinninger S, Nanongkai D. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. In: 54th Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 2013:538-547. doi:10.1109/focs.2013.64
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[78]
2013 | Journal Article | IST-REx-ID: 11902
Dütting P, Henzinger MH, Weber I. Bidder optimal assignments for general utilities. Theoretical Computer Science. 2013;478(3):22-32. doi:10.1016/j.tcs.2013.01.030
View | Files available | DOI
 
[77]
2013 | Journal Article | IST-REx-ID: 11758
Aceto L, Henzinger MH, Sgall J. 38th International Colloquium on Automata, Languages and Programming. Information and Computation. 2013;222(1):1. doi:10.1016/j.ic.2012.11.002
View | DOI
 
[76]
2013 | Journal Article | IST-REx-ID: 2831 | OA
Chatterjee K, Henzinger MH, Joglekar M, Shah N. Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. Formal Methods in System Design. 2013;42(3):301-327. doi:10.1007/s10703-012-0180-2
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[75]
2012 | Conference Paper | IST-REx-ID: 11656
Dütting P, Henzinger MH, Weber I. Maximizing revenue from strategic recommendations under decaying trust. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management. Association for Computing Machinery; 2012:2268-2286. doi:10.1145/2396761.2398621
View | DOI
 
[74]
2012 | Conference Paper | IST-REx-ID: 11794 | OA
Dütting P, Henzinger MH, Starnberger M. Auctions with heterogeneous items and budget limits. In: 8th International Workshop on Internet and Network Economics. Vol 7695. Springer Nature; 2012:44–57. doi:10.1007/978-3-642-35311-6_4
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[73]
2012 | Conference Paper | IST-REx-ID: 11795
Colini-Baldeschi R, Henzinger MH, Leonardi S, Starnberger M. On multiple keyword sponsored search auctions with budgets. In: 39th International Colloquium on Automata, Languages, and Programming. Vol 7392. Springer Nature; 2012:1–12. doi:10.1007/978-3-642-31585-5_1
View | Files available | DOI
 
[72]
2012 | Conference Paper | IST-REx-ID: 3165 | OA
Chatterjee K, Henzinger MH. An O(n2) time algorithm for alternating Büchi games. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM; 2012:1386-1399. doi:10.1137/1.9781611973099.109
View | Files available | DOI | Download None (ext.) | arXiv
 
[71]
2012 | Conference Paper | IST-REx-ID: 10905 | OA
Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. Polynomial-time algorithms for energy games with special weight structures. In: Algorithms – ESA 2012. Vol 7501. Springer; 2012:301-312. doi:10.1007/978-3-642-33090-2_27
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[70]
2011 | Journal Article | IST-REx-ID: 11673
Baykan E, Henzinger MH, Marian L, Weber I. A comprehensive study of features and algorithms for URL-based topic classification. ACM Transactions on the Web. 2011;5(3). doi:10.1145/1993053.1993057
View | DOI
 
[69]
2011 | Journal Article | IST-REx-ID: 11760
Dütting P, Henzinger MH, Weber I. Offline file assignments for online load balancing. Information Processing Letters. 2011;111(4):178-183. doi:10.1016/j.ipl.2010.11.022
View | DOI
 
[68]
2011 | Conference Paper | IST-REx-ID: 11796
Henzinger MH, Vidali A. Multi-parameter mechanism design under budget and matroid constraints. In: 19th Annual European Symposium on Algorithms. Vol 6942. Springer Nature; 2011:192–202. doi:10.1007/978-3-642-23719-5_17
View | DOI
 
[67]
2011 | Conference Paper | IST-REx-ID: 11864
Dütting P, Henzinger MH, Weber I. An expressive mechanism for auctions on the web. In: Proceedings of the 20th International Conference on World Wide Web. Association for Computing Machinery; 2011:127-136. doi:10.1145/1963405.1963427
View | DOI
 
[66]
2011 | Conference Paper | IST-REx-ID: 3342 | OA
Chatterjee K, Henzinger MH, Joglekar M, Nisarg S. Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. In: Gopalakrishnan G, Qadeer S, eds. Vol 6806. Springer; 2011:260-276. doi:10.1007/978-3-642-22110-1_21
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[65]
2011 | Conference Paper | IST-REx-ID: 3343 | OA
Chatterjee K, Henzinger MH. Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification. In: SIAM; 2011:1318-1336. doi:10.1137/1.9781611973082.101
[Submitted Version] View | DOI | Download Submitted Version (ext.)
 
[64]
2011 | Technical Report | IST-REx-ID: 5379 | OA
Chatterjee K, Henzinger MH. An O(N2) Time Algorithm for Alternating Büchi Games. IST Austria; 2011. doi:10.15479/AT:IST-2011-0009
[Published Version] View | Files available | DOI
 
[63]
2010 | Conference Paper | IST-REx-ID: 11797 | OA
Feldman J, Henzinger MH, Korula N, Mirrokni VS, Stein C. Online stochastic packing applied to display ad allocation. In: 18th Annual European Symposium on Algorithms. Vol 6346. Springer Nature; 2010:182–194. doi:10.1007/978-3-642-15775-2_16
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[62]
2010 | Conference Paper | IST-REx-ID: 11798
Dütting P, Henzinger MH. Mechanisms for the marriage and the assignment game. In: 7th International Conference on Algorithms and Complexity. Vol 6078. Springer Nature; 2010:6–12. doi:10.1007/978-3-642-13073-1_2
View | DOI
 
[61]
2010 | Conference Paper | IST-REx-ID: 11838 | OA
Dütting P, Henzinger MH, Weber I. Sponsored search, market equilibria, and the Hungarian Method. In: 27th International Symposium on Theoretical Aspects of Computer Science. Vol 5. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2010:287-298. doi:10.4230/LIPICS.STACS.2010.2463
[Published Version] View | Files available | DOI | Download Published Version (ext.) | arXiv
 
[60]
2010 | Conference Paper | IST-REx-ID: 11863
Dütting P, Henzinger MH, Weber I. How much is your personal recommendation worth? In: Proceedings of the 19th International Conference on World Wide Web . Association for Computing Machinery; 2010:1085-1086. doi:10.1145/1772690.1772816
View | DOI
 
[59]
2010 | Journal Article | IST-REx-ID: 11885
Henzinger MH, Suñol J, Weber I. The stability of the h-index. Scientometrics. 2010;84(2):465-479. doi:10.1007/s11192-009-0098-7
View | DOI
 
[58]
2009 | Conference Paper | IST-REx-ID: 11799
Dütting P, Henzinger MH, Weber I. Bidder optimal assignments for general utilities. In: 5th International Workshop on Internet and Network Economics. Vol 5929. Springer Nature; 2009:575-582. doi:10.1007/978-3-642-10841-9_58
View | Files available | DOI
 
[57]
2009 | Conference Paper | IST-REx-ID: 11912 | OA
Baykan Eda, Henzinger MH, Keller SF, de Castelberg S, Kinzler M. A comparison of techniques for sampling web pages. In: 26th International Symposium on Theoretical Aspects of Computer Science. Vol 3. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2009:13-30. doi:10.4230/LIPICS.STACS.2009.1809
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[56]
2009 | Conference Paper | IST-REx-ID: 11905
Baykan E, Henzinger MH, Marian L, Weber I. Purely URL-based topic classification. In: 18th International World Wide Web Conference. Association for Computing Machinery; 2009:1109-1110. doi:10.1145/1526709.1526880
View | DOI
 
[55]
2009 | Conference Paper | IST-REx-ID: 11906
Abdel Hamid O, Behzadi B, Christoph S, Henzinger MH. Detecting the origin of text segments efficiently. In: 18th International World Wide Web Conference. Association for Computing Machinery; 2009:61-70. doi:10.1145/1526709.1526719
View | DOI
 
[54]
2008 | Journal Article | IST-REx-ID: 11878
Baykan E, Henzinger MH, Weber I. Web page language identification based on URLs. Proceedings of the VLDB Endowment. 2008;1(1):176-187. doi:10.14778/1453856.1453880
View | DOI
 
[53]
2007 | Journal Article | IST-REx-ID: 11884
Henzinger MH. Search technologies for the internet. Science. 2007;317(5837):468-471. doi:10.1126/science.1126557
View | DOI | PubMed | Europe PMC
 
[52]
2007 | Conference Paper | IST-REx-ID: 11924
Henzinger MH. Combinatorial algorithms for web search engines: three success stories. In: 18th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial & Applied Mathematics; 2007:1022-1026.
View
 
[51]
2006 | Conference Paper | IST-REx-ID: 11929
Henzinger MH. Finding near-duplicate web pages: A large-scale evaluation of algorithms. In: 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Association for Computing Machinery; 2006:284-291. doi:10.1145/1148170.1148222
View | DOI
 
[50]
2005 | Conference Paper | IST-REx-ID: 11698
Henzinger MH. Hyperlink analysis on the world wide web. In: Proceedings of the 16th ACM Conference on Hypertext and Hypermedia. Association for Computing Machinery; 2005:1-3. doi:10.1145/1083356.1083357
View | DOI
 
[49]
2005 | Journal Article | IST-REx-ID: 11904
Henzinger MH, Chang B-W, Milch B, Brin S. Query-free news search. World Wide Web. 2005;8(2):101-126. doi:10.1007/s11280-004-4870-6
View | Files available | DOI
 
[48]
2005 | Journal Article | IST-REx-ID: 11763 | OA
Goel A, Henzinger MH, Plotkin S. An online throughput-competitive algorithm for multicast routing and admission control. Journal of Algorithms. 2005;55(1):1-20. doi:10.1016/j.jalgor.2004.11.001
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[47]
2004 | Journal Article | IST-REx-ID: 11762 | OA
Henzinger MH. Algorithmic challenges in web search engines. Internet Mathematics. 2004;1(1):115-123. doi:10.1080/15427951.2004.10129079
[Published Version] View | DOI | Download Published Version (ext.)
 
[46]
2004 | Conference Paper | IST-REx-ID: 11801
Henzinger MH. Algorithmic aspects of web search engines. In: 2th Annual European Symposium on Algorithms. Vol 3221. Springer Nature; 2004:3. doi:10.1007/978-3-540-30140-0_2
View | DOI
 
[45]
2004 | Conference Paper | IST-REx-ID: 11800
Henzinger MH. The past, present, and future of web search engines. In: 31st International Colloquium on Automata, Languages and Programming. Vol 3142. Springer Nature; 2004:3. doi:10.1007/978-3-540-27836-8_2
View | DOI
 
[44]
2004 | Conference Paper | IST-REx-ID: 11859
Henzinger MH. The past, present, and future of web information retrieval. In: SPIE Proceedings. Vol 5296. Society of Photo-Optical Instrumentation Engineers; 2004:23-26. doi:10.1117/12.537534
View | DOI
 
[43]
2004 | Journal Article | IST-REx-ID: 11877 | OA
Henzinger MH, Lawrence S. Extracting knowledge from the World Wide Web. Proceedings of the National Academy of Sciences. 2004;101(suppl_1):5186-5191. doi:10.1073/pnas.0307528100
[Published Version] View | DOI | Download Published Version (ext.) | PubMed | Europe PMC
 
[42]
2003 | Journal Article | IST-REx-ID: 11766 | OA
Henzinger MH, Leonardi S. Scheduling multicasts on unit-capacity trees and meshes. Journal of Computer and System Sciences. 2003;66(3):567-611. doi:10.1016/s0022-0000(03)00043-6
[Published Version] View | DOI | Download Published Version (ext.)
 
[41]
2003 | Journal Article | IST-REx-ID: 11764
Goel A, Henzinger MH, Plotkin S, Tardos E. Scheduling data transfers in a network and the set scheduling problem. Journal of Algorithms. 2003;48(2):314-332. doi:10.1016/s0196-6774(03)00054-3
View | DOI
 
[40]
2003 | Conference Paper | IST-REx-ID: 11897
Bharat K, Henzinger MH. Improved algorithms for topic distillation in a hyperlinked environment. In: 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Association for Computing Machinery; 2003:104–111. doi:10.1145/290941.290972
View | DOI
 
[39]
2003 | Conference Paper | IST-REx-ID: 11860
Henzinger MH, Chang B-W, Milch B, Brin S. Query-free news search. In: Proceedings of the 12th International Conference on World Wide Web. Association for Computing Machinery; 2003. doi:10.1145/775152.775154
View | Files available | DOI
 
[38]
2003 | Conference Paper | IST-REx-ID: 11909 | OA
Henzinger MH, Motwani R, Silverstein C. Challenges in web search engines. In: 18th International Joint Conference on Artificial Intelligence. Association for Computing Machinery; 2003:1573-1579.
[Published Version] View | Download Published Version (ext.)
 
[37]
2001 | Journal Article | IST-REx-ID: 11892
Henzinger MH, King V. Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. 2001;31(2):364-374. doi:10.1137/s0097539797327209
View | DOI
 
[36]
2001 | Conference Paper | IST-REx-ID: 11914
Bharat K, Chang B-W, Henzinger MH, Ruhl M. Who links to whom: Mining linkage between Web sites. In: 1st IEEE International Conference on Data Mining. Institute of Electrical and Electronics Engineers; 2001:51-58. doi:10.1109/ICDM.2001.989500
View | DOI
 
[35]
2001 | Journal Article | IST-REx-ID: 11755
Henzinger MH. Hyperlink analysis for the Web. IEEE Internet Computing. 2001;5(1):45-50. doi:10.1109/4236.895141
View | DOI | WoS
 
[34]
2000 | Journal Article | IST-REx-ID: 11683
Henzinger MH, Rao S, Gabow HN. Computing vertex connectivity: New bounds from old techniques. Journal of Algorithms. 2000;34(2):222-250. doi:10.1006/jagm.1999.1055
View | DOI
 
[33]
2000 | Journal Article | IST-REx-ID: 11685
Henzinger MH, Heydon A, Mitzenmacher M, Najork M. On near-uniform URL sampling. Computer Networks. 2000;33(1-6):295-308. doi:10.1016/s1389-1286(00)00055-4
View | DOI
 
[32]
2000 | Journal Article | IST-REx-ID: 11694
Albers S, Henzinger MH. Exploring unknown environments. SIAM Journal on Computing. 2000;29(4):1164-1188. doi:10.1137/s009753979732428x
View | DOI
 
[31]
2000 | Journal Article | IST-REx-ID: 11770 | OA
Bharat K, Broder A, Dean J, Henzinger MH. A comparison of techniques to find mirrored hosts on the WWW. Journal of the American Society for Information Science. 2000;51(12):1114-1122. doi:10.1002/1097-4571(2000)9999:9999<::aid-asi1025>3.0.co;2-0
[Published Version] View | DOI | Download Published Version (ext.)
 
[30]
2000 | Conference Paper | IST-REx-ID: 11802
Henzinger MH. Web information retrieval - an algorithmic perspective. In: 8th Annual European Symposium on Algorithms. Vol 1879. Springer Nature; 2000:1–8. doi:10.1007/3-540-45253-2_1
View | DOI
 
[29]
2000 | Journal Article | IST-REx-ID: 11893
Henzinger MH. Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. 2000;29(6):1761-1815. doi:10.1137/s0097539794263907
View | DOI
 
[28]
1999 | Conference Paper | IST-REx-ID: 11691
Goel A, Henzinger MH, Plotkin S, Tardos E. Scheduling data transfers in a network and the set scheduling problem. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 1999:189-197. doi:10.1145/301250.301300
View | DOI
 
[27]
1999 | Journal Article | IST-REx-ID: 11687
Dean J, Henzinger MH. Finding related pages in the world wide Web. Computer Networks. 1999;31(11-16):1467-1479. doi:10.1016/s1389-1286(99)00022-5
View | DOI
 
[26]
1999 | Journal Article | IST-REx-ID: 11688
Henzinger MH, Heydon A, Mitzenmacher M, Najork M. Measuring index quality using random walks on the web. Computer Networks. 1999;31(11-16):1291-1303. doi:10.1016/s1389-1286(99)00016-x
View | DOI
 
[25]
1999 | Journal Article | IST-REx-ID: 11769
Henzinger MH, King V. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM. 1999;46(4):502-516. doi:10.1145/320211.320215
View | DOI
 
[24]
1999 | Journal Article | IST-REx-ID: 11895 | OA
Silverstein C, Marais H, Henzinger MH, Moricz M. Analysis of a very large web search engine query log. ACM SIGIR Forum. 1999;33(1):6-12. doi:10.1145/331403.331405
[Published Version] View | DOI | Download Published Version (ext.)
 
[23]
1999 | Journal Article | IST-REx-ID: 11679
Henzinger MH, King V, Warnow T. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica. 1999;24:1-13. doi:10.1007/pl00009268
View | Files available | DOI
 
[22]
1999 | Conference Paper | IST-REx-ID: 11925
Henzinger MH, Leonardi  S. Scheduling multicasts on unit-capacity trees and meshes. In: 10th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial & Applied Mathematics; 1999:438-447.
View
 
[21]
1998 | Conference Paper | IST-REx-ID: 11682
Agarwal PK, EppsteinL. J. Guibas D, Henzinger MH. Parametric and kinetic minimum spanning trees. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science. ; 1998:596-605. doi:10.1109/SFCS.1998.743510
View | DOI
 
[20]
1998 | Journal Article | IST-REx-ID: 11681
Henzinger MH, Fredman ML. Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica. 1998;22(3):351-362. doi:10.1007/pl00009228
View | DOI
 
[19]
1998 | Conference Paper | IST-REx-ID: 11926
Goel A, Henzinger MH, Plotkin S. An online throughput-competitive algorithm for multicast routing and admission control. In: 9th Annual ACM SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 1998:97-106.
View | Files available
 
[18]
1998 | Journal Article | IST-REx-ID: 11680
Alberts D, Henzinger MH. Average-case analysis of dynamic graph algorithms. Algorithmica. 1998;20:31-60. doi:10.1007/pl00009186
View | Files available | DOI
 
[17]
1997 | Journal Article | IST-REx-ID: 11666
Anderson JM, Berc LM, Dean J, et al. Continuous profiling: Where have all the cycles gone? ACM Transactions on Computer Systems. 1997;15(4):357-390. doi:10.1145/265924.265925
View | DOI
 
[16]
1997 | Journal Article | IST-REx-ID: 11767 | OA
Henzinger MH, Klein P, Rao S, Subramanian S. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences. 1997;55(1):3-23. doi:10.1006/jcss.1997.1493
[Published Version] View | DOI | Download Published Version (ext.)
 
[15]
1997 | Journal Article | IST-REx-ID: 11765
Henzinger MH. A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. Journal of Algorithms. 1997;24(1):194-220. doi:10.1006/jagm.1997.0855
View | DOI
 
[14]
1997 | Conference Paper | IST-REx-ID: 11803
Henzinger MH, King V. Maintaining minimum spanning trees in dynamic graphs. In: 24th International Colloquium on Automata, Languages and Programming. Vol 1256. Springer Nature; 1997:594–604. doi:10.1007/3-540-63165-8_214
View | DOI
 
[13]
1997 | Journal Article | IST-REx-ID: 11849 | OA
Anderson JM, Berc LM, Dean J, et al. Continuous profiling: Where have all the cycles gone? ACM SIGOPS Operating Systems Review. 1997;31(5):1-14. doi:10.1145/269005.266637
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[12]
1997 | Journal Article | IST-REx-ID: 11883
Henzinger MH, Thorup M. Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Random Structures and Algorithms. 1997;11(4):369-379. doi:10.1002/(sici)1098-2418(199712)11:4<369::aid-rsa5>3.0.co;2-x
View | DOI
 
[11]
1996 | Journal Article | IST-REx-ID: 11761
Henzinger MH, Williamson DP. On the number of small cuts in a graph. Information Processing Letters. 1996;59(1):41-44. doi:10.1016/0020-0190(96)00079-8
View | DOI
 
[10]
1996 | Conference Paper | IST-REx-ID: 11804
Henzinger MH, Telle JA. Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning. In: 5th Scandinavian Workshop on Algorithm Theory. Vol 1097. Springer Nature; 1996:16–27. doi:10.1007/3-540-61422-2_117
View | DOI
 
[9]
1996 | Conference Paper | IST-REx-ID: 11910
Henzinger MH, Thorup M. Improved sampling with applications to dynamic graph algorithms. In: 23rd International Colloquium on Automata, Languages, and Programming. Vol 1099. Springer Nature; 1996:290-299. doi:10.1007/3-540-61440-0_136
View | DOI
 
[8]
1996 | Conference Paper | IST-REx-ID: 11927 | OA
Henzinger MH, King V, Warnow T. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. In: 7th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 1996:333-340.
[Published Version] View | Files available | Download Published Version (ext.)
 
[7]
1995 | Journal Article | IST-REx-ID: 11677
Henzinger MH. Fully dynamic biconnectivity in graphs. Algorithmica. 1995;13(6):503-538. doi:10.1007/bf01189067
View | DOI
 
[6]
1995 | Conference Paper | IST-REx-ID: 11684
Henzinger MH, King V. Fully dynamic biconnectivity and transitive closure. In: Proceedings of IEEE 36th Annual Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 1995:664-672. doi:10.1109/SFCS.1995.492668
View | DOI
 
[5]
1995 | Conference Paper | IST-REx-ID: 11806
Henzinger MH. Approximating minimum cuts under insertions. In: 22nd International Colloquium on Automata, Languages and Programming. Vol 944. Springer Nature; 1995:280–291. doi:10.1007/3-540-60084-1_81
View | DOI
 
[4]
1995 | Conference Paper | IST-REx-ID: 11805
Henzinger MH, Poutré H. Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. In: 3rd Annual European Symposium on Algorithms. Vol 979. Springer Nature; 1995:171–184. doi:10.1007/3-540-60313-1_142
View | DOI
 
[3]
1995 | Conference Paper | IST-REx-ID: 11928 | OA
Alberts D, Henzinger MH. Average case analysis of dynamic graph algorithms. In: 6th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 1995:312-321.
[Published Version] View | Files available | Download Published Version (ext.)
 
[2]
1995 | Conference Paper | IST-REx-ID: 4498
Henzinger MH, Henzinger TA, Kopke P. Computing simulations on finite and infinite graphs. In: Proceedings of IEEE 36th Annual Foundations of Computer Science. IEEE; 1995:453-462. doi:10.1109/SFCS.1995.492576
View | DOI
 
[1]
1994 | Conference Paper | IST-REx-ID: 11857
Henzinger MH. Fully dynamic cycle-equivalence in graphs. In: 35th Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 1994:744-755. doi:10.1109/sfcs.1994.365718
View | DOI
 
Marked Publication(s)

Search

Filter Publications

199 Publications

Mark all

[199]
2024 | Conference Paper | IST-REx-ID: 15008 | OA
Goranci G, Henzinger MH, Räcke H, Sachdeva S, Sricharan AR. Electrical flows for polylogarithmic competitive oblivious routing. In: 15th Innovations in Theoretical Computer Science Conference. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ITCS.2024.55
[Published Version] View | Files available | DOI | arXiv
 
[198]
2024 | Conference Paper | IST-REx-ID: 14769 | OA
Henzinger MH, Saulpic D, Sidl L. Experimental evaluation of fully dynamic k-means via coresets. In: 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments. Society for Industrial & Applied Mathematics; 2024:220-233. doi:10.1137/1.9781611977929.17
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[197]
2024 | Journal Article | IST-REx-ID: 15121 | OA
Zheng DW, Henzinger MH. Multiplicative auction algorithm for approximate maximum weight bipartite matching. Mathematical Programming. 2024. doi:10.1007/s10107-024-02066-3
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[196]
2024 | Conference Paper | IST-REx-ID: 15093 | OA
Cultrera di Montesano S, Edelsbrunner H, Henzinger MH, Ost L. Dynamically maintaining the persistent homology of time series. In: Woodruff DP, ed. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics; 2024:243-295. doi:10.1137/1.9781611977912.11
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[195]
2024 | Conference Paper | IST-REx-ID: 15253 | OA
Henzinger MH, Upadhyay J, Upadhyay S. A unifying framework for differentially private sums under continual observation. In: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 2024. Society for Industrial and Applied Mathematics; 2024:995-1018. doi:10.1137/1.9781611977912.38
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[194]
2023 | Conference Paper | IST-REx-ID: 12760 | OA
Henzinger MH, Neumann S, Räcke H, Schmid S. Dynamic maintenance of monotone dynamic programs and applications. In: 40th International Symposium on Theoretical Aspects of Computer Science. Vol 254. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.STACS.2023.36
[Published Version] View | Files available | DOI | arXiv
 
[193]
2023 | Conference Paper | IST-REx-ID: 14085 | OA
Goranci G, Henzinger MH. Efficient data structures for incremental exact and approximate maximum flow. In: 50th International Colloquium on Automata, Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.69
[Published Version] View | Files available | DOI
 
[192]
2023 | Conference Paper | IST-REx-ID: 14086 | OA
Henzinger MH, Liu P, Vondrák J, Zheng DW. Faster submodular maximization for several classes of matroids. In: 50th International Colloquium on Automata, Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.74
[Published Version] View | Files available | DOI | arXiv
 
[191]
2023 | Conference Paper | IST-REx-ID: 14462 | OA
Fichtenberger H, Henzinger MH, Upadhyay J. Constant matters: Fine-grained error bound on differentially private continual observation. In: Proceedings of the 40th International Conference on Machine Learning. Vol 202. ML Research Press; 2023:10072-10092.
[Published Version] View | Download Published Version (ext.)
 
[190]
2023 | Journal Article | IST-REx-ID: 14558
Bhattacharya S, Henzinger MH, Nanongkai D, Wu X. Deterministic near-optimal approximation algorithms for dynamic set cover. SIAM Journal on Computing. 2023;52(5):1132-1192. doi:10.1137/21M1428649
View | DOI
 
[189]
2023 | Journal Article | IST-REx-ID: 14043 | OA
Henzinger MH, Jin B, Peng R, Williamson DP. A combinatorial cut-toggling algorithm for solving Laplacian linear systems. Algorithmica. 2023;85:2680-3716. doi:10.1007/s00453-023-01154-8
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[188]
2023 | Conference Paper | IST-REx-ID: 13236 | OA
Zheng DW, Henzinger MH. Multiplicative auction algorithm for approximate maximum weight bipartite matching. In: International Conference on Integer Programming and Combinatorial Optimization. Vol 13904. Springer Nature; 2023:453-465. doi:10.1007/978-3-031-32726-1_32
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[187]
2022 | Journal Article | IST-REx-ID: 11662
Henzinger MH, Peng P. Constant-time Dynamic (Δ +1)-Coloring. ACM Transactions on Algorithms. 2022;18(2). doi:10.1145/3501403
View | DOI
 
[186]
2022 | Conference Paper | IST-REx-ID: 11812 | OA
Hanauer K, Henzinger MH, Hua QC. Fully dynamic four-vertex subgraph counting. In: 1st Symposium on Algorithmic Foundations of Dynamic Networks. Vol 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.SAND.2022.18
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[185]
2022 | Conference Paper | IST-REx-ID: 11808 | OA
Hanauer K, Henzinger MH, Schulz C. Recent advances in fully dynamic graph algorithms. In: 1st Symposium on Algorithmic Foundations of Dynamic Networks. Vol 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.SAND.2022.1
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[184]
2022 | Conference Paper | IST-REx-ID: 11918
Henzinger MH, Lincoln A, Saha B. The complexity of average-case dynamic subgraph counting. In: 33rd Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2022:459-498. doi:10.1137/1.9781611977073.23
View | DOI
 
[183]
2022 | Conference Paper | IST-REx-ID: 11930 | OA
Henzinger MH, Noe A, Schulz C. Practical fully dynamic minimum cut algorithms. In: 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2022:13-26. doi:10.1137/1.9781611977042.2
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[182]
2022 | Preprint | IST-REx-ID: 14236 | OA
Goranci G, Henzinger MH. Incremental approximate maximum flow in m1/2+o(1) update time. arXiv. doi:10.48550/arXiv.2211.09606
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[181]
2021 | Conference Paper | IST-REx-ID: 10054 | OA
Chatterjee K, Henzinger MH, Kale SS, Svozil A. Faster algorithms for bounded liveness in graphs and game graphs. In: 48th International Colloquium on Automata, Languages, and Programming. Vol 198. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.ICALP.2021.124
[Published Version] View | Files available | DOI
 
[180]
2021 | Conference Paper | IST-REx-ID: 11649 | OA
Henzinger MH, Paz A, Schmid S. On the complexity of weight-dynamic network algorithms. In: IFIP Networking Conference. Institute of Electrical and Electronics Engineers; 2021. doi:10.23919/ifipnetworking52078.2021.9472803
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[179]
2021 | Journal Article | IST-REx-ID: 11663 | OA
Bernstein A, Forster S, Henzinger MH. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms. 2021;17(4). doi:10.1145/3469833
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[178]
2021 | Journal Article | IST-REx-ID: 11756 | OA
Henzinger MH, Peng P. Constant-time dynamic weight approximation for minimum spanning forest. Information and Computation. 2021;281(12). doi:10.1016/j.ic.2021.104805
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[177]
2021 | Conference Paper | IST-REx-ID: 11771 | OA
Henzinger MH, Wu X. Upper and lower bounds for fully retroactive graph problems. In: 17th International Symposium on Algorithms and Data Structures. Vol 12808. Springer Nature; 2021:471–484. doi:10.1007/978-3-030-83508-8_34
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[176]
2021 | Conference Paper | IST-REx-ID: 11814 | OA
Fichtenberger H, Henzinger MH, Ost W. Differentially private algorithms for graphs under continual observation. In: 29th Annual European Symposium on Algorithms. Vol 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.ESA.2021.42
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[175]
2021 | Journal Article | IST-REx-ID: 11886 | OA
Henzinger MH, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. 2021;50(3):STOC16-98-STOC16-137. doi:10.1137/16m1097808
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[174]
2021 | Conference Paper | IST-REx-ID: 11919 | OA
Bergamaschi T, Henzinger MH, Gutenberg MP, Williams VV, Wein N. New techniques and fine-grained hardness for dynamic near-additive spanners. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2021:1836-1855. doi:10.1137/1.9781611976465.110
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[173]
2021 | Conference Paper | IST-REx-ID: 11923 | OA
Henzinger MH, Neumann S, Räcke H, Schmid S. Tight bounds for online graph partitioning. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2021:2799-2818. doi:10.1137/1.9781611976465.166
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[172]
2021 | Conference Paper | IST-REx-ID: 11920 | OA
Bhattacharya S, Henzinger MH, Nanongkai D, Wu X. Dynamic set cover: Improved amortized and worst-case update time. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2021:2537-2549. doi:10.1137/1.9781611976465.150
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[171]
2021 | Conference Paper | IST-REx-ID: 11931 | OA
Goranci G, Henzinger MH, Leniowski D, Schulz C, Svozil A. Fully dynamic k-center clustering in low dimensional metrics. In: 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2021:143-153. doi:10.1137/1.9781611976472.11
[Published Version] View | DOI | Download Published Version (ext.)
 
[170]
2021 | Conference Paper | IST-REx-ID: 10002 | OA
Chatterjee K, Dvorak W, Henzinger MH, Svozil A. Symbolic time and space tradeoffs for probabilistic verification. In: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science. Institute of Electrical and Electronics Engineers; 2021:1-13. doi:10.1109/LICS52264.2021.9470739
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[169]
2021 | Journal Article | IST-REx-ID: 9293 | OA
Chatterjee K, Dvořák W, Henzinger MH, Svozil A. Algorithms and conditional lower bounds for planning problems. Artificial Intelligence. 2021;297(8). doi:10.1016/j.artint.2021.103499
[Preprint] View | Files available | DOI | Download Preprint (ext.) | WoS | arXiv
 
[168]
2020 | Journal Article | IST-REx-ID: 11675 | OA
Bhattacharya S, Chakrabarty D, Henzinger MH. Deterministic dynamic matching in O(1) update time. Algorithmica. 2020;82(4):1057-1080. doi:10.1007/s00453-019-00630-4
[Published Version] View | DOI | Download Published Version (ext.)
 
[167]
2020 | Journal Article | IST-REx-ID: 11674 | OA
Henzinger MH, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum of radii. Algorithmica. 2020;82(11):3183-3194. doi:10.1007/s00453-020-00721-7
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[166]
2020 | Conference Paper | IST-REx-ID: 11818 | OA
Henzinger MH, Kale S. Fully-dynamic coresets. In: 28th Annual European Symposium on Algorithms. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.ESA.2020.57
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[165]
2020 | Conference Paper | IST-REx-ID: 11816 | OA
Henzinger MH, Shahbaz K, Paul R, Schulz C. Dynamic matching algorithms in practice. In: 8th Annual European Symposium on Algorithms. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.ESA.2020.58
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[164]
2020 | Conference Paper | IST-REx-ID: 11824 | OA
Henzinger MH, Neumann S, Wiese A. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.51
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[163]
2020 | Conference Paper | IST-REx-ID: 11822 | OA
Hanauer K, Henzinger MH, Schulz C. Faster fully dynamic transitive closure in practice. In: 18th International Symposium on Experimental Algorithms. Vol 160. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SEA.2020.14
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[162]
2020 | Conference Paper | IST-REx-ID: 11825 | OA
Henzinger MH, Peng P. Constant-time dynamic (Δ+1)-coloring. In: 37th International Symposium on Theoretical Aspects of Computer Science. Vol 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.STACS.2020.53
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[161]
2020 | Conference Paper | IST-REx-ID: 11819 | OA
Henzinger MH, Noe A, Schulz C, Strash D. Finding all global minimum cuts in practice. In: 28th Annual European Symposium on Algorithms. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.ESA.2020.59
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[160]
2020 | Conference Paper | IST-REx-ID: 11852 | OA
Chen L, Goranci G, Henzinger MH, Peng R, Saranurak T. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In: 61st Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 2020:1135-1146. doi:10.1109/focs46700.2020.00109
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[159]
2020 | Conference Paper | IST-REx-ID: 11880 | OA
Hanauer K, Henzinger MH, Schulz C. Fully dynamic single-source reachability in practice: An experimental study. In: 2020 Symposium on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2020:106-119. doi:10.1137/1.9781611976007.9
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[158]
2020 | Conference Paper | IST-REx-ID: 11881 | OA
Henzinger MH, Noe A, Schulz C. Shared-memory branch-and-reduce for multiterminal cuts. In: 2020 Symposium on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2020:42-55. doi:10.1137/1.9781611976007.4
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[157]
2020 | Journal Article | IST-REx-ID: 11889
Henzinger MH, Rao S, Wang D. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. 2020;49(1):1-36. doi:10.1137/18m1180335
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[156]
2020 | Journal Article | IST-REx-ID: 11894 | OA
Goranci G, Henzinger MH, Peng P. Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics. 2020;34(1):130-162. doi:10.1137/17m1163153
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[155]
2019 | Conference Paper | IST-REx-ID: 11826 | OA
Ancona B, Henzinger MH, Roditty L, Williams VV, Wein N. Algorithms and hardness for diameter in dynamic graphs. In: 46th International Colloquium on Automata, Languages, and Programming. Vol 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.ICALP.2019.13
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[154]
2019 | Conference Paper | IST-REx-ID: 11850 | OA
Henzinger MH, Neumann S, Schmid S. Efficient distributed workload (re-)embedding. In: SIGMETRICS’19: International Conference on Measurement and Modeling of Computer Systems. Association for Computing Machinery; 2019:43–44. doi:10.1145/3309697.3331503
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[153]
2019 | Book Chapter | IST-REx-ID: 11847
Biedermann S, Henzinger MH, Schulz C, Schuster B. Vienna Graph Clustering. In: Canzar S, Rojas Ringeling F, eds. Protein-Protein Interaction Networks. Vol 2074. MIMB. Springer Nature; 2019:215–231. doi:10.1007/978-1-4939-9873-9_16
View | DOI | PubMed | Europe PMC
 
[152]
2019 | Conference Paper | IST-REx-ID: 11853 | OA
Bhattacharya S, Henzinger MH, Nanongkai D. A new deterministic algorithm for dynamic set cover. In: 60th Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 2019:406-423. doi:10.1109/focs.2019.00033
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[151]
2019 | Conference Paper | IST-REx-ID: 11851
Henzinger MH, Noe A, Schulz C. Shared-memory exact minimum cuts. In: 33rd International Parallel and Distributed Processing Symposium. Institute of Electrical and Electronics Engineers; 2019. doi:10.1109/ipdps.2019.00013
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[150]
2019 | Conference Paper | IST-REx-ID: 11865 | OA
Daga M, Henzinger MH, Nanongkai D, Saranurak T. Distributed edge connectivity in sublinear time. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery; 2019:343–354. doi:10.1145/3313276.3316346
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[149]
2019 | Conference Paper | IST-REx-ID: 11871 | OA
Bernstein A, Forster S, Henzinger MH. A deamortization approach for dynamic spanner and dynamic maximal matching. In: 30th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2019:1899-1918. doi:10.1137/1.9781611975482.115
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[148]
2019 | Journal Article | IST-REx-ID: 11898 | OA
Bhattacharya S, Henzinger MH, Neumann S. New amortized cell-probe lower bounds for dynamic problems. Theoretical Computer Science. 2019;779:72-87. doi:10.1016/j.tcs.2019.01.043
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[147]
2019 | Conference Paper | IST-REx-ID: 6887 | OA
Chatterjee K, Dvorák W, Henzinger MH, Svozil A. Near-linear time algorithms for Streett objectives in graphs and MDPs. In: Leibniz International Proceedings in Informatics. Vol 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.CONCUR.2019.7
[Published Version] View | Files available | DOI
 
[146]
2018 | Conference Paper | IST-REx-ID: 10883 | OA
Chatterjee K, Dvořák W, Henzinger MH, Svozil A. Quasipolynomial set-based symbolic algorithms for parity games. In: 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning. Vol 57. EasyChair; 2018:233-253. doi:10.29007/5z5k
[Published Version] View | Files available | DOI | arXiv
 
[145]
2018 | Journal Article | IST-REx-ID: 11657 | OA
Henzinger MH, Noe A, Schulz C, Strash D. Practical minimum cut algorithms. ACM Journal of Experimental Algorithmics. 2018;23:1-22. doi:10.1145/3274662
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[144]
2018 | Journal Article | IST-REx-ID: 11667 | OA
Dütting P, Henzinger MH, Starnberger M. Valuation compressions in VCG-based combinatorial auctions. ACM Transactions on Economics and Computation. 2018;6(2). doi:10.1145/3232860
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[143]
2018 | Journal Article | IST-REx-ID: 11664 | OA
Goranci G, Henzinger MH, Thorup M. Incremental exact min-cut in polylogarithmic amortized update time. ACM Transactions on Algorithms. 2018;14(2). doi:10.1145/3174803
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[142]
2018 | Journal Article | IST-REx-ID: 11757 | OA
Bhattacharya S, Henzinger MH, Italiano G. Dynamic algorithms via the primal-dual method. Information and Computation. 2018;261(08):219-239. doi:10.1016/j.ic.2018.02.005
[Published Version] View | DOI | Download Published Version (ext.)
 
[141]
2018 | Conference Paper | IST-REx-ID: 11828 | OA
Goranci G, Henzinger MH, Peng P. Dynamic effective resistances and approximate schur complement on separable graphs. In: 26th Annual European Symposium on Algorithms. Vol 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.ESA.2018.40
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[140]
2018 | Conference Paper | IST-REx-ID: 11827 | OA
Goranci G, Henzinger MH, Leniowski D. A tree structure for dynamic facility location. In: 26th Annual European Symposium on Algorithms. Vol 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.ESA.2018.39
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[139]
2018 | Journal Article | IST-REx-ID: 11768 | OA
Henzinger MH, Krinninger S, Nanongkai D. Decremental single-source shortest paths on undirected graphs in near-linear total update time. Journal of the ACM. 2018;65(6):1-40. doi:10.1145/3218657
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[138]
2018 | Conference Paper | IST-REx-ID: 11872 | OA
Bhattacharya S, Chakrabarty D, Henzinger MH, Nanongkai D. Dynamic algorithms for graph coloring. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2018:1-20. doi:10.1137/1.9781611975031.1
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[137]
2018 | Conference Paper | IST-REx-ID: 11882 | OA
Henzinger MH, Noe A, Schulz C, Strash D. Practical minimum cut algorithms. In: 20th Workshop on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2018:48-61. doi:10.1137/1.9781611975055.5
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[136]
2018 | Journal Article | IST-REx-ID: 11890 | OA
Bhattacharya S, Henzinger MH, Italiano GF. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 2018;47(3):859-887. doi:10.1137/140998925
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[135]
2018 | Conference Paper | IST-REx-ID: 11911 | OA
Biedermann S, Henzinger MH, Schulz C, Schuster B. Memetic graph clustering. In: 17th International Symposium on Experimental Algorithms. Vol 103. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.SEA.2018.3
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[134]
2018 | Conference Paper | IST-REx-ID: 310 | OA
Chatterjee K, Dvorák W, Henzinger MH, Loitzenbauer V. Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety, and diameter. In: ACM; 2018:2341-2356. doi:10.1137/1.9781611975031.151
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[133]
2018 | Conference Paper | IST-REx-ID: 141 | OA
Chatterjee K, Henzinger MH, Loitzenbauer V, Oraee S, Toman V. Symbolic algorithms for graphs and Markov decision processes with fairness objectives. In: Vol 10982. Springer; 2018:178-197. doi:10.1007/978-3-319-96142-2_13
[Published Version] View | Files available | DOI | WoS
 
[132]
2018 | Conference Paper | IST-REx-ID: 35 | OA
Chatterjee K, Dvorák W, Henzinger MH, Svozil A. Algorithms and conditional lower bounds for planning problems. In: 28th International Conference on Automated Planning and Scheduling . AAAI Press; 2018.
View | Files available | Download None (ext.) | WoS | arXiv
 
[131]
2017 | Conference Paper | IST-REx-ID: 11651 | OA
Wang D, Fountoulakis K, Henzinger MH, Mahoney MW, Rao Satish. Capacity releasing diffusion for speed and locality. In: Proceedings of the 34th International Conference on Machine Learning. Vol 70. ML Research Press; 2017:3598-3607.
[Published Version] View | Download Published Version (ext.) | arXiv
 
[130]
2017 | Journal Article | IST-REx-ID: 11665 | OA
Henzinger MH, Krinninger S, Nanongkai D. Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks. ACM Transactions on Algorithms. 2017;13(4). doi:10.1145/3146550
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[129]
2017 | Journal Article | IST-REx-ID: 11676 | OA
Dvořák W, Henzinger MH, Williamson DP. Maximizing a submodular function with viability constraints. Algorithmica. 2017;77(1):152-172. doi:10.1007/s00453-015-0066-y
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[128]
2017 | Conference Paper | IST-REx-ID: 11772
Henzinger MH. The state of the art in dynamic graph algorithms. In: 44th International Conference on Current Trends in Theory and Practice of Computer Science. Vol 10706. Springer Nature; 2017:40–44. doi:10.1007/978-3-319-73117-9_3
View | DOI
 
[127]
2017 | Conference Paper | IST-REx-ID: 11829 | OA
Henzinger MH, Lincoln A, Neumann S, Vassilevska Williams V. Conditional hardness for sensitivity problems. In: 8th Innovations in Theoretical Computer Science Conference. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ITCS.2017.26
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[126]
2017 | Conference Paper | IST-REx-ID: 11833 | OA
Goranci G, Henzinger MH, Peng P. The power of vertex sparsifiers in dynamic graph algorithms. In: 25th Annual European Symposium on Algorithms. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.45
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[125]
2017 | Conference Paper | IST-REx-ID: 11832 | OA
Henzinger MH, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum of radii. In: 25th Annual European Symposium on Algorithms. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.48
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[124]
2017 | Conference Paper | IST-REx-ID: 11874 | OA
Bhattacharya S, Henzinger MH, Nanongkai D. Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 0. Society for Industrial and Applied Mathematics; 2017:470-489. doi:10.1137/1.9781611974782.30
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[123]
2017 | Conference Paper | IST-REx-ID: 11873 | OA
Henzinger MH, Rao S, Wang D. Local flow partitioning for faster edge connectivity. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2017:1919-1938. doi:10.1137/1.9781611974782.125
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[122]
2017 | Conference Paper | IST-REx-ID: 11831 | OA
Goranci G, Henzinger MH, Peng P. Improved guarantees for vertex sparsification in planar graphs. In: 25th Annual European Symposium on Algorithms. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.44
[Published Version] View | Files available | DOI | Download Published Version (ext.) | arXiv
 
[121]
2017 | Journal Article | IST-REx-ID: 11903 | OA
Bhattacharya S, Dvořák W, Henzinger MH, Starnberger M. Welfare maximization with friends-of-friends network externalities. Theory of Computing Systems. 2017;61(4):948-986. doi:10.1007/s00224-017-9759-8
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[120]
2017 | Conference Paper | IST-REx-ID: 12571 | OA
Bhattacharya S, Chakrabarty D, Henzinger MH. Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. In: 19th International Conference on Integer Programming and Combinatorial Optimization. Vol 10328. Springer Nature; 2017:86-98. doi:10.1007/978-3-319-59250-3_8
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[119]
2017 | Journal Article | IST-REx-ID: 464 | OA
Chatterjee K, Henzinger MH, Loitzenbauer V. Improved algorithms for parity and Streett objectives. Logical Methods in Computer Science. 2017;13(3). doi:10.23638/LMCS-13(3:26)2017
[Published Version] View | Files available | DOI | arXiv
 
[118]
2017 | Conference Paper | IST-REx-ID: 552 | OA
Chatterjee K, Henzinger MH, Svozil A. Faster algorithms for mean-payoff parity games. In: Leibniz International Proceedings in Informatics. Vol 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.MFCS.2017.39
[Published Version] View | Files available | DOI
 
[117]
2017 | Conference Paper | IST-REx-ID: 6519 | OA
Chatterjee K, Dvorák W, Henzinger MH, Loitzenbauer V. Improved set-based symbolic algorithms for parity games. In: Vol 82. Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik; 2017. doi:10.4230/LIPICS.CSL.2017.18
[Published Version] View | Files available | DOI
 
[116]
2016 | Conference Paper | IST-REx-ID: 1068 | OA
Chatterjee K, Dvorák W, Henzinger MH, Loitzenbauer V. Conditionally optimal algorithms for generalized Büchi Games. In: Vol 58. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPIcs.MFCS.2016.25
[Published Version] View | Files available | DOI
 
[115]
2016 | Conference Paper | IST-REx-ID: 1140 | OA
Chatterjee K, Dvoák W, Henzinger MH, Loitzenbauer V. Model and objective separation with conditional lower bounds: disjunction is harder than conjunction. In: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE; 2016:197-206. doi:10.1145/2933575.2935304
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[114]
2016 | Conference Paper | IST-REx-ID: 11836 | OA
Cheung YK, Goranci G, Henzinger MH. Graph minors for preserving terminal distances approximately - lower and upper bounds. In: 43rd International Colloquium on Automata, Languages, and Programming. Vol 55. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPICS.ICALP.2016.131
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[113]
2016 | Conference Paper | IST-REx-ID: 11834 | OA
Goranci G, Henzinger MH, Thorup M. Incremental exact min-cut in poly-logarithmic amortized update time. In: 24th Annual European Symposium on Algorithms. Vol 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPICS.ESA.2016.46
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[112]
2016 | Conference Paper | IST-REx-ID: 11835 | OA
Henzinger MH, Neumann S. Incremental and fully dynamic subgraph connectivity for emergency planning. In: 24th Annual European Symposium on Algorithms. Vol 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPICS.ESA.2016.48
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[111]
2016 | Conference Paper | IST-REx-ID: 11866 | OA
Henzinger MH, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In: 48th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery; 2016:489-498. doi:10.1145/2897518.2897638
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[110]
2016 | Conference Paper | IST-REx-ID: 11867 | OA
Bhattacharya S, Henzinger MH, Nanongkai D. New deterministic approximation algorithms for fully dynamic matching. In: 48th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery; 2016:398-411. doi:10.1145/2897518.2897568
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[109]
2016 | Journal Article | IST-REx-ID: 11891 | OA
Henzinger MH, Krinninger S, Nanongkai D. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing. 2016;45(3):947-1006. doi:10.1137/140957299
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[108]
2015 | Journal Article | IST-REx-ID: 11668 | OA
Colini-Baldeschi R, Leonardi S, Henzinger MH, Starnberger M. On multiple keyword sponsored search auctions with budgets. ACM Transactions on Economics and Computation. 2015;4(1). doi:10.1145/2818357
[Submitted Version] View | DOI | Download Submitted Version (ext.)
 
[107]
2015 | Journal Article | IST-REx-ID: 11669 | OA
Dütting P, Henzinger MH, Starnberger M. Auctions for heterogeneous items and budget limits. ACM Transactions on Economics and Computation. 2015;4(1). doi:10.1145/2818351
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[106]
2015 | Journal Article | IST-REx-ID: 11670
Dütting P, Henzinger MH, Weber I. An expressive mechanism for auctions on the web. ACM Transactions on Economics and Computation. 2015;4(1). doi:10.1145/2716312
View | DOI
 
[105]
2015 | Conference Paper | IST-REx-ID: 11774 | OA
Cheung YK, Henzinger MH, Hoefer M, Starnberger M. Combinatorial auctions with conflict-based externalities. In: 11th International Conference on Web and Internet Economics. Vol 9470. Springer Nature; 2015:230–243. doi:10.1007/978-3-662-48995-6_17
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[104]
2015 | Conference Paper | IST-REx-ID: 11773 | OA
Ben-Zwi O, Henzinger MH, Loitzenbauer V. Ad exchange: Envy-free auctions with mediators. In: 11th International Conference on Web and Internet Economics. Vol 9470. Springer Nature; 2015:104–117. doi:10.1007/978-3-662-48995-6_8
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[103]
2015 | Conference Paper | IST-REx-ID: 11785 | OA
Henzinger MH, Krinninger S, Nanongkai D. Improved algorithms for decremental single-source reachability on directed graphs. In: 42nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:725-736. doi:10.1007/978-3-662-47672-7_59
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[102]
2015 | Conference Paper | IST-REx-ID: 11787 | OA
Henzinger MH, Krinninger S, Loitzenbauer V. Finding 2-edge and 2-vertex strongly connected components in quadratic time. In: 2nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:713-724. doi:10.1007/978-3-662-47672-7_58
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[101]
2015 | Conference Paper | IST-REx-ID: 11788 | OA
Dvořák W, Henzinger MH. Online ad assignment with an ad exchange. In: 12th International Workshop of Approximation and Online Algorithms. Vol 8952. Springer Nature; 2015:156–167. doi:10.1007/978-3-319-18263-6_14
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[100]
2015 | Conference Paper | IST-REx-ID: 11786 | OA
Bhattacharya S, Henzinger MH, Italiano GF. Design of dynamic algorithms via primal-dual method. In: 42nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:206-218. doi:10.1007/978-3-662-47672-7_17
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[99]
2015 | Journal Article | IST-REx-ID: 11845 | OA
Chernomor O, Minh BQ, Forest F, et al. Split diversity in constrained conservation prioritization using integer linear programming. Methods in Ecology and Evolution. 2015;6(1):83-91. doi:10.1111/2041-210x.12299
[Published Version] View | Files available | DOI | PubMed | Europe PMC
 
[98]
2015 | Conference Paper | IST-REx-ID: 11868 | OA
Henzinger MH, Krinninger S, Nanongkai D, Saranurak T. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In: 47th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2015. doi:10.1145/2746539.2746609
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[97]
2015 | Conference Paper | IST-REx-ID: 11869 | OA
Bhattacharya S, Henzinger MH, Nanongkai D, Tsourakakis C. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: 47th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2015:173-182. doi:10.1145/2746539.2746592
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[96]
2015 | Conference Paper | IST-REx-ID: 11837 | OA
Bhattacharya S, Dvorák W, Henzinger MH, Starnberger Martin. Welfare maximization with friends-of-friends network externalities. In: 32nd International Symposium on Theoretical Aspects of Computer Science. Vol 30. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:90-102. doi:10.4230/LIPICS.STACS.2015.90
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[95]
2015 | Journal Article | IST-REx-ID: 11901 | OA
Henzinger MH, Loitzenbauer V. Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. 2015;573:1-15. doi:10.1016/j.tcs.2015.01.033
View | DOI | Download None (ext.)
 
[94]
2015 | Conference Paper | IST-REx-ID: 1661 | OA
Chatterjee K, Henzinger MH, Loitzenbauer V. Improved algorithms for one-pair and k-pair Streett objectives. In: Proceedings - Symposium on Logic in Computer Science. Vol 2015-July. IEEE; 2015. doi:10.1109/LICS.2015.34
[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.)
 
[93]
2014 | Conference Paper | IST-REx-ID: 11789 | OA
Charikar M, Henzinger MH, Nguyễn HL. Online bipartite matching with decomposable weights. In: 22nd Annual European Symposium on Algorithms. Vol 8737. Springer Nature; 2014:260-271. doi:10.1007/978-3-662-44777-2_22
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[92]
2014 | Conference Paper | IST-REx-ID: 11790
Cigler L, Dvořák W, Henzinger MH, Starnberger M. Limiting price discrimination when selling products with positive network externalities. In: 10th International Conference of Web and Internet Economics. Vol 8877. Springer Nature; 2014:44-57. doi:10.1007/978-3-319-13129-0_4
View | DOI
 
[91]
2014 | Conference Paper | IST-REx-ID: 11855 | OA
Henzinger MH, Krinninger S, Nanongkai D. Decremental single-source shortest paths on undirected graphs in near-linear total update time. In: 55th Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 2014:146-155. doi:10.1109/focs.2014.24
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[90]
2014 | Conference Paper | IST-REx-ID: 11870 | OA
Henzinger MH, Krinninger S, Nanongkai D. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In: 46th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2014. doi:10.1145/2591796.2591869
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[89]
2014 | Conference Paper | IST-REx-ID: 11876 | OA
Henzinger MH, Krinninger S, Nanongkai D. A subquadratic-time algorithm for decremental single-source shortest paths. In: 25th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2014:1053-1072. doi:10.1137/1.9781611973402.79
[Published Version] View | DOI | Download Published Version (ext.)
 
[88]
2014 | Conference Paper | IST-REx-ID: 11875 | OA
Bhattacharya S, Henzinger MH, Italiano GF. Deterministic fully dynamic data structures for vertex cover and matching. In: 26th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2014:785-804. doi:10.1137/1.9781611973730.54
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[87]
2014 | Journal Article | IST-REx-ID: 1375 | OA
Chatterjee K, Henzinger MH, Krinninger S, Loitzenbauer V, Raskin M. Approximating the minimum cycle mean. Theoretical Computer Science. 2014;547(C):104-116. doi:10.1016/j.tcs.2014.06.031
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[86]
2014 | Journal Article | IST-REx-ID: 2141 | OA
Chatterjee K, Henzinger MH. Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition. Journal of the ACM. 2014;61(3). doi:10.1145/2597631
[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.)
 
[85]
2014 | Journal Article | IST-REx-ID: 535 | OA
Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. Polynomial-time algorithms for energy games with special weight structures. Algorithmica. 2014;70(3):457-492. doi:10.1007/s00453-013-9843-7
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[84]
2013 | Journal Article | IST-REx-ID: 11671
Baykan E, Weber I, Henzinger MH. A comprehensive study of techniques for URL-based web page language classification. ACM Transactions on the Web. 2013;7(1). doi:10.1145/2435215.2435218
View | DOI
 
[83]
2013 | Journal Article | IST-REx-ID: 11759 | OA
Dütting P, Henzinger MH, Weber I. Sponsored search, market equilibria, and the Hungarian Method. Information Processing Letters. 2013;113(3):67-73. doi:10.1016/j.ipl.2012.11.006
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[82]
2013 | Conference Paper | IST-REx-ID: 11793 | OA
Henzinger MH, Krinninger S, Nanongkai D. Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks. In: 40th International Colloquium on Automata, Languages, and Programming. Vol 7966. Springer Nature; 2013:607–619. doi:10.1007/978-3-642-39212-2_53
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[81]
2013 | Conference Paper | IST-REx-ID: 11791 | OA
Dütting P, Henzinger MH, Starnberger M. Valuation compressions in VCG-based combinatorial auctions. In: 9th International Conference on Web and Internet Economics. Vol 8289. Springer Nature; 2013:146–159. doi:10.1007/978-3-642-45046-4_13
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[80]
2013 | Conference Paper | IST-REx-ID: 11792 | OA
Dvořák W, Henzinger MH, Williamson DP. Maximizing a submodular function with viability constraints. In: 21st Annual European Symposium on Algorithms. Vol 8125. Springer Nature; 2013:409-420. doi:10.1007/978-3-642-40450-4_35
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[79]
2013 | Conference Paper | IST-REx-ID: 11856 | OA
Henzinger MH, Krinninger S, Nanongkai D. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. In: 54th Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 2013:538-547. doi:10.1109/focs.2013.64
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[78]
2013 | Journal Article | IST-REx-ID: 11902
Dütting P, Henzinger MH, Weber I. Bidder optimal assignments for general utilities. Theoretical Computer Science. 2013;478(3):22-32. doi:10.1016/j.tcs.2013.01.030
View | Files available | DOI
 
[77]
2013 | Journal Article | IST-REx-ID: 11758
Aceto L, Henzinger MH, Sgall J. 38th International Colloquium on Automata, Languages and Programming. Information and Computation. 2013;222(1):1. doi:10.1016/j.ic.2012.11.002
View | DOI
 
[76]
2013 | Journal Article | IST-REx-ID: 2831 | OA
Chatterjee K, Henzinger MH, Joglekar M, Shah N. Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. Formal Methods in System Design. 2013;42(3):301-327. doi:10.1007/s10703-012-0180-2
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[75]
2012 | Conference Paper | IST-REx-ID: 11656
Dütting P, Henzinger MH, Weber I. Maximizing revenue from strategic recommendations under decaying trust. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management. Association for Computing Machinery; 2012:2268-2286. doi:10.1145/2396761.2398621
View | DOI
 
[74]
2012 | Conference Paper | IST-REx-ID: 11794 | OA
Dütting P, Henzinger MH, Starnberger M. Auctions with heterogeneous items and budget limits. In: 8th International Workshop on Internet and Network Economics. Vol 7695. Springer Nature; 2012:44–57. doi:10.1007/978-3-642-35311-6_4
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[73]
2012 | Conference Paper | IST-REx-ID: 11795
Colini-Baldeschi R, Henzinger MH, Leonardi S, Starnberger M. On multiple keyword sponsored search auctions with budgets. In: 39th International Colloquium on Automata, Languages, and Programming. Vol 7392. Springer Nature; 2012:1–12. doi:10.1007/978-3-642-31585-5_1
View | Files available | DOI
 
[72]
2012 | Conference Paper | IST-REx-ID: 3165 | OA
Chatterjee K, Henzinger MH. An O(n2) time algorithm for alternating Büchi games. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM; 2012:1386-1399. doi:10.1137/1.9781611973099.109
View | Files available | DOI | Download None (ext.) | arXiv
 
[71]
2012 | Conference Paper | IST-REx-ID: 10905 | OA
Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. Polynomial-time algorithms for energy games with special weight structures. In: Algorithms – ESA 2012. Vol 7501. Springer; 2012:301-312. doi:10.1007/978-3-642-33090-2_27
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[70]
2011 | Journal Article | IST-REx-ID: 11673
Baykan E, Henzinger MH, Marian L, Weber I. A comprehensive study of features and algorithms for URL-based topic classification. ACM Transactions on the Web. 2011;5(3). doi:10.1145/1993053.1993057
View | DOI
 
[69]
2011 | Journal Article | IST-REx-ID: 11760
Dütting P, Henzinger MH, Weber I. Offline file assignments for online load balancing. Information Processing Letters. 2011;111(4):178-183. doi:10.1016/j.ipl.2010.11.022
View | DOI
 
[68]
2011 | Conference Paper | IST-REx-ID: 11796
Henzinger MH, Vidali A. Multi-parameter mechanism design under budget and matroid constraints. In: 19th Annual European Symposium on Algorithms. Vol 6942. Springer Nature; 2011:192–202. doi:10.1007/978-3-642-23719-5_17
View | DOI
 
[67]
2011 | Conference Paper | IST-REx-ID: 11864
Dütting P, Henzinger MH, Weber I. An expressive mechanism for auctions on the web. In: Proceedings of the 20th International Conference on World Wide Web. Association for Computing Machinery; 2011:127-136. doi:10.1145/1963405.1963427
View | DOI
 
[66]
2011 | Conference Paper | IST-REx-ID: 3342 | OA
Chatterjee K, Henzinger MH, Joglekar M, Nisarg S. Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. In: Gopalakrishnan G, Qadeer S, eds. Vol 6806. Springer; 2011:260-276. doi:10.1007/978-3-642-22110-1_21
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[65]
2011 | Conference Paper | IST-REx-ID: 3343 | OA
Chatterjee K, Henzinger MH. Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification. In: SIAM; 2011:1318-1336. doi:10.1137/1.9781611973082.101
[Submitted Version] View | DOI | Download Submitted Version (ext.)
 
[64]
2011 | Technical Report | IST-REx-ID: 5379 | OA
Chatterjee K, Henzinger MH. An O(N2) Time Algorithm for Alternating Büchi Games. IST Austria; 2011. doi:10.15479/AT:IST-2011-0009
[Published Version] View | Files available | DOI
 
[63]
2010 | Conference Paper | IST-REx-ID: 11797 | OA
Feldman J, Henzinger MH, Korula N, Mirrokni VS, Stein C. Online stochastic packing applied to display ad allocation. In: 18th Annual European Symposium on Algorithms. Vol 6346. Springer Nature; 2010:182–194. doi:10.1007/978-3-642-15775-2_16
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[62]
2010 | Conference Paper | IST-REx-ID: 11798
Dütting P, Henzinger MH. Mechanisms for the marriage and the assignment game. In: 7th International Conference on Algorithms and Complexity. Vol 6078. Springer Nature; 2010:6–12. doi:10.1007/978-3-642-13073-1_2
View | DOI
 
[61]
2010 | Conference Paper | IST-REx-ID: 11838 | OA
Dütting P, Henzinger MH, Weber I. Sponsored search, market equilibria, and the Hungarian Method. In: 27th International Symposium on Theoretical Aspects of Computer Science. Vol 5. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2010:287-298. doi:10.4230/LIPICS.STACS.2010.2463
[Published Version] View | Files available | DOI | Download Published Version (ext.) | arXiv
 
[60]
2010 | Conference Paper | IST-REx-ID: 11863
Dütting P, Henzinger MH, Weber I. How much is your personal recommendation worth? In: Proceedings of the 19th International Conference on World Wide Web . Association for Computing Machinery; 2010:1085-1086. doi:10.1145/1772690.1772816
View | DOI
 
[59]
2010 | Journal Article | IST-REx-ID: 11885
Henzinger MH, Suñol J, Weber I. The stability of the h-index. Scientometrics. 2010;84(2):465-479. doi:10.1007/s11192-009-0098-7
View | DOI
 
[58]
2009 | Conference Paper | IST-REx-ID: 11799
Dütting P, Henzinger MH, Weber I. Bidder optimal assignments for general utilities. In: 5th International Workshop on Internet and Network Economics. Vol 5929. Springer Nature; 2009:575-582. doi:10.1007/978-3-642-10841-9_58
View | Files available | DOI
 
[57]
2009 | Conference Paper | IST-REx-ID: 11912 | OA
Baykan Eda, Henzinger MH, Keller SF, de Castelberg S, Kinzler M. A comparison of techniques for sampling web pages. In: 26th International Symposium on Theoretical Aspects of Computer Science. Vol 3. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2009:13-30. doi:10.4230/LIPICS.STACS.2009.1809
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[56]
2009 | Conference Paper | IST-REx-ID: 11905
Baykan E, Henzinger MH, Marian L, Weber I. Purely URL-based topic classification. In: 18th International World Wide Web Conference. Association for Computing Machinery; 2009:1109-1110. doi:10.1145/1526709.1526880
View | DOI
 
[55]
2009 | Conference Paper | IST-REx-ID: 11906
Abdel Hamid O, Behzadi B, Christoph S, Henzinger MH. Detecting the origin of text segments efficiently. In: 18th International World Wide Web Conference. Association for Computing Machinery; 2009:61-70. doi:10.1145/1526709.1526719
View | DOI
 
[54]
2008 | Journal Article | IST-REx-ID: 11878
Baykan E, Henzinger MH, Weber I. Web page language identification based on URLs. Proceedings of the VLDB Endowment. 2008;1(1):176-187. doi:10.14778/1453856.1453880
View | DOI
 
[53]
2007 | Journal Article | IST-REx-ID: 11884
Henzinger MH. Search technologies for the internet. Science. 2007;317(5837):468-471. doi:10.1126/science.1126557
View | DOI | PubMed | Europe PMC
 
[52]
2007 | Conference Paper | IST-REx-ID: 11924
Henzinger MH. Combinatorial algorithms for web search engines: three success stories. In: 18th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial & Applied Mathematics; 2007:1022-1026.
View
 
[51]
2006 | Conference Paper | IST-REx-ID: 11929
Henzinger MH. Finding near-duplicate web pages: A large-scale evaluation of algorithms. In: 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Association for Computing Machinery; 2006:284-291. doi:10.1145/1148170.1148222
View | DOI
 
[50]
2005 | Conference Paper | IST-REx-ID: 11698
Henzinger MH. Hyperlink analysis on the world wide web. In: Proceedings of the 16th ACM Conference on Hypertext and Hypermedia. Association for Computing Machinery; 2005:1-3. doi:10.1145/1083356.1083357
View | DOI
 
[49]
2005 | Journal Article | IST-REx-ID: 11904
Henzinger MH, Chang B-W, Milch B, Brin S. Query-free news search. World Wide Web. 2005;8(2):101-126. doi:10.1007/s11280-004-4870-6
View | Files available | DOI
 
[48]
2005 | Journal Article | IST-REx-ID: 11763 | OA
Goel A, Henzinger MH, Plotkin S. An online throughput-competitive algorithm for multicast routing and admission control. Journal of Algorithms. 2005;55(1):1-20. doi:10.1016/j.jalgor.2004.11.001
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[47]
2004 | Journal Article | IST-REx-ID: 11762 | OA
Henzinger MH. Algorithmic challenges in web search engines. Internet Mathematics. 2004;1(1):115-123. doi:10.1080/15427951.2004.10129079
[Published Version] View | DOI | Download Published Version (ext.)
 
[46]
2004 | Conference Paper | IST-REx-ID: 11801
Henzinger MH. Algorithmic aspects of web search engines. In: 2th Annual European Symposium on Algorithms. Vol 3221. Springer Nature; 2004:3. doi:10.1007/978-3-540-30140-0_2
View | DOI
 
[45]
2004 | Conference Paper | IST-REx-ID: 11800
Henzinger MH. The past, present, and future of web search engines. In: 31st International Colloquium on Automata, Languages and Programming. Vol 3142. Springer Nature; 2004:3. doi:10.1007/978-3-540-27836-8_2
View | DOI
 
[44]
2004 | Conference Paper | IST-REx-ID: 11859
Henzinger MH. The past, present, and future of web information retrieval. In: SPIE Proceedings. Vol 5296. Society of Photo-Optical Instrumentation Engineers; 2004:23-26. doi:10.1117/12.537534
View | DOI
 
[43]
2004 | Journal Article | IST-REx-ID: 11877 | OA
Henzinger MH, Lawrence S. Extracting knowledge from the World Wide Web. Proceedings of the National Academy of Sciences. 2004;101(suppl_1):5186-5191. doi:10.1073/pnas.0307528100
[Published Version] View | DOI | Download Published Version (ext.) | PubMed | Europe PMC
 
[42]
2003 | Journal Article | IST-REx-ID: 11766 | OA
Henzinger MH, Leonardi S. Scheduling multicasts on unit-capacity trees and meshes. Journal of Computer and System Sciences. 2003;66(3):567-611. doi:10.1016/s0022-0000(03)00043-6
[Published Version] View | DOI | Download Published Version (ext.)
 
[41]
2003 | Journal Article | IST-REx-ID: 11764
Goel A, Henzinger MH, Plotkin S, Tardos E. Scheduling data transfers in a network and the set scheduling problem. Journal of Algorithms. 2003;48(2):314-332. doi:10.1016/s0196-6774(03)00054-3
View | DOI
 
[40]
2003 | Conference Paper | IST-REx-ID: 11897
Bharat K, Henzinger MH. Improved algorithms for topic distillation in a hyperlinked environment. In: 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Association for Computing Machinery; 2003:104–111. doi:10.1145/290941.290972
View | DOI
 
[39]
2003 | Conference Paper | IST-REx-ID: 11860
Henzinger MH, Chang B-W, Milch B, Brin S. Query-free news search. In: Proceedings of the 12th International Conference on World Wide Web. Association for Computing Machinery; 2003. doi:10.1145/775152.775154
View | Files available | DOI
 
[38]
2003 | Conference Paper | IST-REx-ID: 11909 | OA
Henzinger MH, Motwani R, Silverstein C. Challenges in web search engines. In: 18th International Joint Conference on Artificial Intelligence. Association for Computing Machinery; 2003:1573-1579.
[Published Version] View | Download Published Version (ext.)
 
[37]
2001 | Journal Article | IST-REx-ID: 11892
Henzinger MH, King V. Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. 2001;31(2):364-374. doi:10.1137/s0097539797327209
View | DOI
 
[36]
2001 | Conference Paper | IST-REx-ID: 11914
Bharat K, Chang B-W, Henzinger MH, Ruhl M. Who links to whom: Mining linkage between Web sites. In: 1st IEEE International Conference on Data Mining. Institute of Electrical and Electronics Engineers; 2001:51-58. doi:10.1109/ICDM.2001.989500
View | DOI
 
[35]
2001 | Journal Article | IST-REx-ID: 11755
Henzinger MH. Hyperlink analysis for the Web. IEEE Internet Computing. 2001;5(1):45-50. doi:10.1109/4236.895141
View | DOI | WoS
 
[34]
2000 | Journal Article | IST-REx-ID: 11683
Henzinger MH, Rao S, Gabow HN. Computing vertex connectivity: New bounds from old techniques. Journal of Algorithms. 2000;34(2):222-250. doi:10.1006/jagm.1999.1055
View | DOI
 
[33]
2000 | Journal Article | IST-REx-ID: 11685
Henzinger MH, Heydon A, Mitzenmacher M, Najork M. On near-uniform URL sampling. Computer Networks. 2000;33(1-6):295-308. doi:10.1016/s1389-1286(00)00055-4
View | DOI
 
[32]
2000 | Journal Article | IST-REx-ID: 11694
Albers S, Henzinger MH. Exploring unknown environments. SIAM Journal on Computing. 2000;29(4):1164-1188. doi:10.1137/s009753979732428x
View | DOI
 
[31]
2000 | Journal Article | IST-REx-ID: 11770 | OA
Bharat K, Broder A, Dean J, Henzinger MH. A comparison of techniques to find mirrored hosts on the WWW. Journal of the American Society for Information Science. 2000;51(12):1114-1122. doi:10.1002/1097-4571(2000)9999:9999<::aid-asi1025>3.0.co;2-0
[Published Version] View | DOI | Download Published Version (ext.)
 
[30]
2000 | Conference Paper | IST-REx-ID: 11802
Henzinger MH. Web information retrieval - an algorithmic perspective. In: 8th Annual European Symposium on Algorithms. Vol 1879. Springer Nature; 2000:1–8. doi:10.1007/3-540-45253-2_1
View | DOI
 
[29]
2000 | Journal Article | IST-REx-ID: 11893
Henzinger MH. Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. 2000;29(6):1761-1815. doi:10.1137/s0097539794263907
View | DOI
 
[28]
1999 | Conference Paper | IST-REx-ID: 11691
Goel A, Henzinger MH, Plotkin S, Tardos E. Scheduling data transfers in a network and the set scheduling problem. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 1999:189-197. doi:10.1145/301250.301300
View | DOI
 
[27]
1999 | Journal Article | IST-REx-ID: 11687
Dean J, Henzinger MH. Finding related pages in the world wide Web. Computer Networks. 1999;31(11-16):1467-1479. doi:10.1016/s1389-1286(99)00022-5
View | DOI
 
[26]
1999 | Journal Article | IST-REx-ID: 11688
Henzinger MH, Heydon A, Mitzenmacher M, Najork M. Measuring index quality using random walks on the web. Computer Networks. 1999;31(11-16):1291-1303. doi:10.1016/s1389-1286(99)00016-x
View | DOI
 
[25]
1999 | Journal Article | IST-REx-ID: 11769
Henzinger MH, King V. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM. 1999;46(4):502-516. doi:10.1145/320211.320215
View | DOI
 
[24]
1999 | Journal Article | IST-REx-ID: 11895 | OA
Silverstein C, Marais H, Henzinger MH, Moricz M. Analysis of a very large web search engine query log. ACM SIGIR Forum. 1999;33(1):6-12. doi:10.1145/331403.331405
[Published Version] View | DOI | Download Published Version (ext.)
 
[23]
1999 | Journal Article | IST-REx-ID: 11679
Henzinger MH, King V, Warnow T. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica. 1999;24:1-13. doi:10.1007/pl00009268
View | Files available | DOI
 
[22]
1999 | Conference Paper | IST-REx-ID: 11925
Henzinger MH, Leonardi  S. Scheduling multicasts on unit-capacity trees and meshes. In: 10th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial & Applied Mathematics; 1999:438-447.
View
 
[21]
1998 | Conference Paper | IST-REx-ID: 11682
Agarwal PK, EppsteinL. J. Guibas D, Henzinger MH. Parametric and kinetic minimum spanning trees. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science. ; 1998:596-605. doi:10.1109/SFCS.1998.743510
View | DOI
 
[20]
1998 | Journal Article | IST-REx-ID: 11681
Henzinger MH, Fredman ML. Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica. 1998;22(3):351-362. doi:10.1007/pl00009228
View | DOI
 
[19]
1998 | Conference Paper | IST-REx-ID: 11926
Goel A, Henzinger MH, Plotkin S. An online throughput-competitive algorithm for multicast routing and admission control. In: 9th Annual ACM SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 1998:97-106.
View | Files available
 
[18]
1998 | Journal Article | IST-REx-ID: 11680
Alberts D, Henzinger MH. Average-case analysis of dynamic graph algorithms. Algorithmica. 1998;20:31-60. doi:10.1007/pl00009186
View | Files available | DOI
 
[17]
1997 | Journal Article | IST-REx-ID: 11666
Anderson JM, Berc LM, Dean J, et al. Continuous profiling: Where have all the cycles gone? ACM Transactions on Computer Systems. 1997;15(4):357-390. doi:10.1145/265924.265925
View | DOI
 
[16]
1997 | Journal Article | IST-REx-ID: 11767 | OA
Henzinger MH, Klein P, Rao S, Subramanian S. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences. 1997;55(1):3-23. doi:10.1006/jcss.1997.1493
[Published Version] View | DOI | Download Published Version (ext.)
 
[15]
1997 | Journal Article | IST-REx-ID: 11765
Henzinger MH. A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. Journal of Algorithms. 1997;24(1):194-220. doi:10.1006/jagm.1997.0855
View | DOI
 
[14]
1997 | Conference Paper | IST-REx-ID: 11803
Henzinger MH, King V. Maintaining minimum spanning trees in dynamic graphs. In: 24th International Colloquium on Automata, Languages and Programming. Vol 1256. Springer Nature; 1997:594–604. doi:10.1007/3-540-63165-8_214
View | DOI
 
[13]
1997 | Journal Article | IST-REx-ID: 11849 | OA
Anderson JM, Berc LM, Dean J, et al. Continuous profiling: Where have all the cycles gone? ACM SIGOPS Operating Systems Review. 1997;31(5):1-14. doi:10.1145/269005.266637
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[12]
1997 | Journal Article | IST-REx-ID: 11883
Henzinger MH, Thorup M. Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Random Structures and Algorithms. 1997;11(4):369-379. doi:10.1002/(sici)1098-2418(199712)11:4<369::aid-rsa5>3.0.co;2-x
View | DOI
 
[11]
1996 | Journal Article | IST-REx-ID: 11761
Henzinger MH, Williamson DP. On the number of small cuts in a graph. Information Processing Letters. 1996;59(1):41-44. doi:10.1016/0020-0190(96)00079-8
View | DOI
 
[10]
1996 | Conference Paper | IST-REx-ID: 11804
Henzinger MH, Telle JA. Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning. In: 5th Scandinavian Workshop on Algorithm Theory. Vol 1097. Springer Nature; 1996:16–27. doi:10.1007/3-540-61422-2_117
View | DOI
 
[9]
1996 | Conference Paper | IST-REx-ID: 11910
Henzinger MH, Thorup M. Improved sampling with applications to dynamic graph algorithms. In: 23rd International Colloquium on Automata, Languages, and Programming. Vol 1099. Springer Nature; 1996:290-299. doi:10.1007/3-540-61440-0_136
View | DOI
 
[8]
1996 | Conference Paper | IST-REx-ID: 11927 | OA
Henzinger MH, King V, Warnow T. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. In: 7th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 1996:333-340.
[Published Version] View | Files available | Download Published Version (ext.)
 
[7]
1995 | Journal Article | IST-REx-ID: 11677
Henzinger MH. Fully dynamic biconnectivity in graphs. Algorithmica. 1995;13(6):503-538. doi:10.1007/bf01189067
View | DOI
 
[6]
1995 | Conference Paper | IST-REx-ID: 11684
Henzinger MH, King V. Fully dynamic biconnectivity and transitive closure. In: Proceedings of IEEE 36th Annual Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 1995:664-672. doi:10.1109/SFCS.1995.492668
View | DOI
 
[5]
1995 | Conference Paper | IST-REx-ID: 11806
Henzinger MH. Approximating minimum cuts under insertions. In: 22nd International Colloquium on Automata, Languages and Programming. Vol 944. Springer Nature; 1995:280–291. doi:10.1007/3-540-60084-1_81
View | DOI
 
[4]
1995 | Conference Paper | IST-REx-ID: 11805
Henzinger MH, Poutré H. Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. In: 3rd Annual European Symposium on Algorithms. Vol 979. Springer Nature; 1995:171–184. doi:10.1007/3-540-60313-1_142
View | DOI
 
[3]
1995 | Conference Paper | IST-REx-ID: 11928 | OA
Alberts D, Henzinger MH. Average case analysis of dynamic graph algorithms. In: 6th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 1995:312-321.
[Published Version] View | Files available | Download Published Version (ext.)
 
[2]
1995 | Conference Paper | IST-REx-ID: 4498
Henzinger MH, Henzinger TA, Kopke P. Computing simulations on finite and infinite graphs. In: Proceedings of IEEE 36th Annual Foundations of Computer Science. IEEE; 1995:453-462. doi:10.1109/SFCS.1995.492576
View | DOI
 
[1]
1994 | Conference Paper | IST-REx-ID: 11857
Henzinger MH. Fully dynamic cycle-equivalence in graphs. In: 35th Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 1994:744-755. doi:10.1109/sfcs.1994.365718
View | DOI
 
Marked Publication(s)

Search

Filter Publications