Monika Henzinger

213 Publications

Mark all

[213]
2025 | Published | Conference Paper | IST-REx-ID: 19038 | OA
Henzinger M, Upadhyay J. 2025. Improved differentially private continual observation using group algebra. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 5, 2951–2970.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[212]
2025 | Published | Journal Article | IST-REx-ID: 15121 | OA
Zheng DW, Henzinger M. 2025. Multiplicative auction algorithm for approximate maximum weight bipartite matching. Mathematical Programming. 210, 881–894.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | WoS | arXiv
 
[211]
2025 | Published | Conference Paper | IST-REx-ID: 19858 | OA
El-Hayek A, Hanauer K, Henzinger M. 2025. On b-matching and fully-dynamic maximum k-edge coloring. 4th Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 330, 4.
[Published Version] View | Files available | DOI | arXiv
 
[210]
2025 | Published | Conference Paper | IST-REx-ID: 19982 | OA
El-Hayek A, Henzinger M, Li J. 2025. Fully dynamic approximate minimum cut in subpolynomial time per operation. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 750–784.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[209]
2024 | Published | Conference Paper | IST-REx-ID: 18557 | OA
El-Hayek A, Henzinger M, Schmid S. 2024. Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. 38th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 319, 21.
[Published Version] View | Files available | DOI | arXiv
 
[208]
2024 | Published | Conference Paper | IST-REx-ID: 18156 | OA
Henzinger M, Sricharan AR, Steiner TA. 2024. Private counting of distinct elements in the turnstile model and extensions. International Conference on Approximation Algorithms for Combinatorial Optimization Problems . APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems, LIPIcs, vol. 317, 40.
[Published Version] View | Files available | DOI | arXiv
 
[207]
2024 | Published | Conference Paper | IST-REx-ID: 18308 | OA
La Tour MD, Henzinger M, Saulpic D. 2024. Fully dynamic k-means coreset in near-optimal update time. 32nd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 308, 100.
[Published Version] View | Files available | DOI | arXiv
 
[206]
2024 | Published | Conference Paper | IST-REx-ID: 18115 | OA
Axiotis K, Cohen-Addad V, Henzinger M, Jerome S, Mirrokni V, Saulpic D, Woodruff DP, Wunder M. 2024. Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond. Proceedings of the 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 2086–2107.
[Published Version] View | Download Published Version (ext.) | arXiv
 
[205]
2024 | Published | Conference Paper | IST-REx-ID: 15253 | OA
Henzinger M, Upadhyay J, Upadhyay S. 2024. A unifying framework for differentially private sums under continual observation. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2024, 995–1018.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[204]
2024 | Published | Conference Paper | IST-REx-ID: 14769 | OA
Henzinger M, Saulpic D, Sidl L. 2024. Experimental evaluation of fully dynamic k-means via coresets. 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments. ALENEX: Workshop on Algorithm Engineering and Experiments, 220–233.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[203]
2024 | Published | Conference Paper | IST-REx-ID: 18116 | OA
La Tour MD, Henzinger M, Saulpic D. 2024. Making old things new: A unified algorithm for differentially private clustering. Proceedings of the 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 12046–12086.
[Published Version] View | Download Published Version (ext.) | arXiv
 
[202]
2024 | Published | Conference Paper | IST-REx-ID: 18928 | OA
Henzinger M, Saha B, Seybold MP, Ye C. 2024. On the complexity of algorithms with predictions for dynamic graph problems. 15th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 287, 62:1-62:25.
[Published Version] View | Files available | DOI | arXiv
 
[201]
2024 | Published | Conference Paper | IST-REx-ID: 15093 | OA
Cultrera di Montesano S, Edelsbrunner H, Henzinger M, Ost L. 2024. Dynamically maintaining the persistent homology of time series. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SODA: Symposium on Discrete Algorithms, 243–295.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[200]
2024 | Published | Conference Paper | IST-REx-ID: 19512 | OA
Andersson JD, Henzinger M, Pagh R, Steiner TA, Upadhyay J. 2024. Continual counting with gradual privacy expiration. 38th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 37.
[Preprint] View | Download Preprint (ext.) | arXiv
 
[199]
2024 | Published | Conference Paper | IST-REx-ID: 18503 | OA
Henzinger M, Li J, Rao S, Wang D. 2024. Deterministic near-linear time minimum cut in weighted graphs. 35th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 3089–3139.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[198]
2024 | Published | Conference Paper | IST-REx-ID: 15008 | OA
Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. 2024. Electrical flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 287, 55.
[Published Version] View | Files available | DOI | arXiv
 
[197]
2024 | Published | Conference Paper | IST-REx-ID: 18906 | OA
Hanauer K, Henzinger M, Münk R, Räcke H, Vötsch M. 2024. Expander hierarchies for normalized cuts on graphs. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. KDD: Knowledge Discovery and Data Mining, 1016–1027.
[Published Version] View | Files available | DOI
 
[196]
2023 | Published | Journal Article | IST-REx-ID: 14043 | OA
Henzinger M, Jin B, Peng R, Williamson DP. 2023. A combinatorial cut-toggling algorithm for solving Laplacian linear systems. Algorithmica. 85, 2680–3716.
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[195]
2023 | Published | Conference Paper | IST-REx-ID: 15364 | OA
Charikar M, Hu L, Henzinger M, Vötsch M, Waingarten E. 2023. Simple, scalable and effective clustering via one-dimensional projections. 37th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, NeurIPS, vol. 36.
[Published Version] View | Files available | arXiv
 
[194]
2023 | Published | Journal Article | IST-REx-ID: 14558
Bhattacharya S, Henzinger M, Nanongkai D, Wu X. 2023. Deterministic near-optimal approximation algorithms for dynamic set cover. SIAM Journal on Computing. 52(5), 1132–1192.
View | DOI
 
[193]
2023 | Published | Conference Paper | IST-REx-ID: 14462 | OA
Fichtenberger H, Henzinger M, Upadhyay J. 2023. Constant matters: Fine-grained error bound on differentially private continual observation. Proceedings of the 40th International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 202, 10072–10092.
[Published Version] View | Download Published Version (ext.) | arXiv
 
[192]
2023 | Published | Conference Paper | IST-REx-ID: 13236 | OA
Zheng DW, Henzinger M. 2023. Multiplicative auction algorithm for approximate maximum weight bipartite matching. International Conference on Integer Programming and Combinatorial Optimization. IPCO: Integer Programming and Combinatorial Optimization, LNCS, vol. 13904, 453–465.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[191]
2023 | Published | Conference Paper | IST-REx-ID: 14085 | OA
Goranci G, Henzinger M. 2023. Efficient data structures for incremental exact and approximate maximum flow. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 69.
[Published Version] View | Files available | DOI | arXiv
 
[190]
2023 | Published | Conference Paper | IST-REx-ID: 12760 | OA
Henzinger M, Neumann S, Räcke H, Schmid S. 2023. Dynamic maintenance of monotone dynamic programs and applications. 40th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 254, 36.
[Published Version] View | Files available | DOI | arXiv
 
[189]
2023 | Published | Conference Paper | IST-REx-ID: 14086 | OA
Henzinger M, Liu P, Vondrák J, Zheng DW. 2023. Faster submodular maximization for several classes of matroids. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 74.
[Published Version] View | Files available | DOI | arXiv
 
[188]
2022 | Submitted | Preprint | IST-REx-ID: 14236 | OA
Goranci G, Henzinger M. Incremental approximate maximum flow in m1/2+o(1) update time. arXiv, 2211.09606.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[187]
2022 | Published | Journal Article | IST-REx-ID: 11662
Henzinger M, Peng P. 2022. Constant-time Dynamic (Δ +1)-Coloring. ACM Transactions on Algorithms. 18(2), 16.
View | DOI
 
[186]
2022 | Published | Conference Paper | IST-REx-ID: 11808 | OA
Hanauer K, Henzinger M, Schulz C. 2022. Recent advances in fully dynamic graph algorithms. 1st Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221, 1.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[185]
2022 | Published | Conference Paper | IST-REx-ID: 11812 | OA
Hanauer K, Henzinger M, Hua QC. 2022. Fully dynamic four-vertex subgraph counting. 1st Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221, 18.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[184]
2022 | Published | Conference Paper | IST-REx-ID: 11918
Henzinger M, Lincoln A, Saha B. 2022. The complexity of average-case dynamic subgraph counting. 33rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 459–498.
View | DOI
 
[183]
2022 | Published | Conference Paper | IST-REx-ID: 11930 | OA
Henzinger M, Noe A, Schulz C. 2022. Practical fully dynamic minimum cut algorithms. 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 13–26.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[182]
2022 | Published | Book Chapter | IST-REx-ID: 20062
Henzinger M. 2022.Fine-Grained Complexity Lower Bounds for Problems in Computer Aided Verification. In: Principles of Systems Design. vol. 13660, 292–305.
View | DOI
 
[181]
2021 | Published | Conference Paper | IST-REx-ID: 11649 | OA
Henzinger M, Paz A, Schmid S. 2021. On the complexity of weight-dynamic network algorithms. IFIP Networking Conference. IFIP: Networking.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[180]
2021 | Published | Journal Article | IST-REx-ID: 11663 | OA
Bernstein A, Forster S, Henzinger M. 2021. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms. 17(4), 29.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[179]
2021 | Published | Journal Article | IST-REx-ID: 11756 | OA
Henzinger M, Peng P. 2021. Constant-time dynamic weight approximation for minimum spanning forest. Information and Computation. 281(12), 104805.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[178]
2021 | Published | Conference Paper | IST-REx-ID: 11771 | OA
Henzinger M, Wu X. 2021. Upper and lower bounds for fully retroactive graph problems. 17th International Symposium on Algorithms and Data Structures. WADS: Workshop on Algorithms and Data Structures, LNCS, vol. 12808, 471–484.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[177]
2021 | Published | Conference Paper | IST-REx-ID: 11814 | OA
Fichtenberger H, Henzinger M, Ost W. 2021. Differentially private algorithms for graphs under continual observation. 29th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 204, 42.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[176]
2021 | Published | Journal Article | IST-REx-ID: 11886 | OA
Henzinger M, Krinninger S, Nanongkai D. 2021. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. 50(3), STOC16-98-STOC16-137.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[175]
2021 | Published | Conference Paper | IST-REx-ID: 11919 | OA
Bergamaschi T, Henzinger M, Gutenberg MP, Williams VV, Wein N. 2021. New techniques and fine-grained hardness for dynamic near-additive spanners. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1836–1855.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[174]
2021 | Published | Conference Paper | IST-REx-ID: 11920 | OA
Bhattacharya S, Henzinger M, Nanongkai D, Wu X. 2021. Dynamic set cover: Improved amortized and worst-case update time. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 2537–2549.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[173]
2021 | Published | Conference Paper | IST-REx-ID: 11923 | OA
Henzinger M, Neumann S, Räcke H, Schmid S. 2021. Tight bounds for online graph partitioning. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 2799–2818.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[172]
2021 | Published | Conference Paper | IST-REx-ID: 11931 | OA
Goranci G, Henzinger M, Leniowski D, Schulz C, Svozil A. 2021. Fully dynamic k-center clustering in low dimensional metrics. 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 143–153.
[Published Version] View | DOI | Download Published Version (ext.)
 
[171]
2021 | Published | Conference Paper | IST-REx-ID: 10054 | OA
Chatterjee K, Henzinger M, Kale SS, Svozil A. 2021. Faster algorithms for bounded liveness in graphs and game graphs. 48th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 198, 124.
[Published Version] View | Files available | DOI
 
[170]
2021 | Published | Conference Paper | IST-REx-ID: 10002 | OA
Chatterjee K, Dvorak W, Henzinger M, Svozil A. 2021. Symbolic time and space tradeoffs for probabilistic verification. Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 1–13.
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[169]
2021 | Published | Journal Article | IST-REx-ID: 9293 | OA
Chatterjee K, Dvořák W, Henzinger M, Svozil A. 2021. Algorithms and conditional lower bounds for planning problems. Artificial Intelligence. 297(8), 103499.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | WoS | arXiv
 
[168]
2020 | Published | Journal Article | IST-REx-ID: 11674 | OA
Henzinger M, Leniowski D, Mathieu C. 2020. Dynamic clustering to minimize the sum of radii. Algorithmica. 82(11), 3183–3194.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[167]
2020 | Published | Journal Article | IST-REx-ID: 11675 | OA
Bhattacharya S, Chakrabarty D, Henzinger M. 2020. Deterministic dynamic matching in O(1) update time. Algorithmica. 82(4), 1057–1080.
[Published Version] View | DOI | Download Published Version (ext.)
 
[166]
2020 | Published | Conference Paper | IST-REx-ID: 11816 | OA
Henzinger M, Shahbaz K, Paul R, Schulz C. 2020. Dynamic matching algorithms in practice. 8th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 58.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[165]
2020 | Published | Conference Paper | IST-REx-ID: 11818 | OA
Henzinger M, Kale S. 2020. Fully-dynamic coresets. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 57.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[164]
2020 | Published | Conference Paper | IST-REx-ID: 11819 | OA
Henzinger M, Noe A, Schulz C, Strash D. 2020. Finding all global minimum cuts in practice. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 59.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[163]
2020 | Published | Conference Paper | IST-REx-ID: 11822 | OA
Hanauer K, Henzinger M, Schulz C. 2020. Faster fully dynamic transitive closure in practice. 18th International Symposium on Experimental Algorithms. SEA: Symposium on Experimental Algorithms, LIPIcs, vol. 160, 14.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[162]
2020 | Published | Conference Paper | IST-REx-ID: 11824 | OA
Henzinger M, Neumann S, Wiese A. 2020. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 51.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[161]
2020 | Published | Conference Paper | IST-REx-ID: 11825 | OA
Henzinger M, Peng P. 2020. Constant-time dynamic (Δ+1)-coloring. 37th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 154, 53.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[160]
2020 | Published | Conference Paper | IST-REx-ID: 11852 | OA
Chen L, Goranci G, Henzinger M, Peng R, Saranurak T. 2020. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. 61st Annual Symposium on Foundations of Computer Science. FOCS: Annual Symposium on Foundations of Computer Science, 1135–1146.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[159]
2020 | Published | Conference Paper | IST-REx-ID: 11880 | OA
Hanauer K, Henzinger M, Schulz C. 2020. Fully dynamic single-source reachability in practice: An experimental study. 2020 Symposium on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 106–119.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[158]
2020 | Published | Conference Paper | IST-REx-ID: 11881 | OA
Henzinger M, Noe A, Schulz C. 2020. Shared-memory branch-and-reduce for multiterminal cuts. 2020 Symposium on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 42–55.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[157]
2020 | Published | Journal Article | IST-REx-ID: 11889
Henzinger M, Rao S, Wang D. 2020. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. 49(1), 1–36.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[156]
2020 | Published | Journal Article | IST-REx-ID: 11894 | OA
Goranci G, Henzinger M, Peng P. 2020. Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics. 34(1), 130–162.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[155]
2019 | Published | Conference Paper | IST-REx-ID: 11826 | OA
Ancona B, Henzinger M, Roditty L, Williams VV, Wein N. 2019. Algorithms and hardness for diameter in dynamic graphs. 46th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 132, 13.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[154]
2019 | Published | Book Chapter | IST-REx-ID: 11847
Biedermann S, Henzinger M, Schulz C, Schuster B. 2019.Vienna Graph Clustering. In: Protein-Protein Interaction Networks. Methods in Molecular Biology, vol. 2074, 215–231.
View | DOI | PubMed | Europe PMC
 
[153]
2019 | Published | Conference Paper | IST-REx-ID: 11850 | OA
Henzinger M, Neumann S, Schmid S. 2019. Efficient distributed workload (re-)embedding. SIGMETRICS’19: International Conference on Measurement and Modeling of Computer Systems. SIGMETRICS: International Conference on Measurement and Modeling of Computer Systems, 43–44.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[152]
2019 | Published | Conference Paper | IST-REx-ID: 11851
Henzinger M, Noe A, Schulz C. 2019. Shared-memory exact minimum cuts. 33rd International Parallel and Distributed Processing Symposium. IPDPS: International Parallel and Distributed Processing Symposium, 8820968.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[151]
2019 | Published | Conference Paper | IST-REx-ID: 11853 | OA
Bhattacharya S, Henzinger M, Nanongkai D. 2019. A new deterministic algorithm for dynamic set cover. 60th Annual Symposium on Foundations of Computer Science. FOCS: Annual Symposium on Foundations of Computer Science, 406–423.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[150]
2019 | Published | Conference Paper | IST-REx-ID: 11865 | OA
Daga M, Henzinger M, Nanongkai D, Saranurak T. 2019. Distributed edge connectivity in sublinear time. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 343–354.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[149]
2019 | Published | Conference Paper | IST-REx-ID: 11871 | OA
Bernstein A, Forster S, Henzinger M. 2019. A deamortization approach for dynamic spanner and dynamic maximal matching. 30th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1899–1918.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[148]
2019 | Published | Journal Article | IST-REx-ID: 11898 | OA
Bhattacharya S, Henzinger M, Neumann S. 2019. New amortized cell-probe lower bounds for dynamic problems. Theoretical Computer Science. 779, 72–87.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[147]
2019 | Published | Conference Paper | IST-REx-ID: 6887 | OA
Chatterjee K, Dvorák W, Henzinger M, Svozil A. 2019. Near-linear time algorithms for Streett objectives in graphs and MDPs. Leibniz International Proceedings in Informatics. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 140, 7.
[Published Version] View | Files available | DOI
 
[146]
2018 | Published | Journal Article | IST-REx-ID: 11657 | OA
Henzinger M, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms. ACM Journal of Experimental Algorithmics. 23, 1–22.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[145]
2018 | Published | Journal Article | IST-REx-ID: 11664 | OA
Goranci G, Henzinger M, Thorup M. 2018. Incremental exact min-cut in polylogarithmic amortized update time. ACM Transactions on Algorithms. 14(2), 17.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[144]
2018 | Published | Journal Article | IST-REx-ID: 11667 | OA
Dütting P, Henzinger M, Starnberger M. 2018. Valuation compressions in VCG-based combinatorial auctions. ACM Transactions on Economics and Computation. 6(2), 5.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[143]
2018 | Published | Journal Article | IST-REx-ID: 11757 | OA
Bhattacharya S, Henzinger M, Italiano G. 2018. Dynamic algorithms via the primal-dual method. Information and Computation. 261(08), 219–239.
[Published Version] View | DOI | Download Published Version (ext.)
 
[142]
2018 | Published | Journal Article | IST-REx-ID: 11768 | OA
Henzinger M, Krinninger S, Nanongkai D. 2018. Decremental single-source shortest paths on undirected graphs in near-linear total update time. Journal of the ACM. 65(6), 1–40.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[141]
2018 | Published | Conference Paper | IST-REx-ID: 11827 | OA
Goranci G, Henzinger M, Leniowski D. 2018. A tree structure for dynamic facility location. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 39.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[140]
2018 | Published | Conference Paper | IST-REx-ID: 11828 | OA
Goranci G, Henzinger M, Peng P. 2018. Dynamic effective resistances and approximate schur complement on separable graphs. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 40.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[139]
2018 | Published | Conference Paper | IST-REx-ID: 11872 | OA
Bhattacharya S, Chakrabarty D, Henzinger M, Nanongkai D. 2018. Dynamic algorithms for graph coloring. 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1–20.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[138]
2018 | Published | Conference Paper | IST-REx-ID: 11882 | OA
Henzinger M, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms. 20th Workshop on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 48–61.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[137]
2018 | Published | Journal Article | IST-REx-ID: 11890 | OA
Bhattacharya S, Henzinger M, Italiano GF. 2018. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 47(3), 859–887.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[136]
2018 | Published | Conference Paper | IST-REx-ID: 11911 | OA
Biedermann S, Henzinger M, Schulz C, Schuster B. 2018. Memetic graph clustering. 17th International Symposium on Experimental Algorithms. SEA: Symposium on Experimental Algorithms, LIPIcs, vol. 103, 3.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[135]
2018 | Published | Conference Paper | IST-REx-ID: 310 | OA
Chatterjee K, Dvorák W, Henzinger M, Loitzenbauer V. 2018. Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety, and diameter. SODA: Symposium on Discrete Algorithms, 2341–2356.
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[134]
2018 | Published | Conference Paper | IST-REx-ID: 141 | OA
Chatterjee K, Henzinger M, Loitzenbauer V, Oraee S, Toman V. 2018. Symbolic algorithms for graphs and Markov decision processes with fairness objectives. CAV: Computer Aided Verification, LNCS, vol. 10982, 178–197.
[Published Version] View | Files available | DOI | WoS
 
[133]
2018 | Published | Conference Paper | IST-REx-ID: 10883 | OA
Chatterjee K, Dvořák W, Henzinger M, Svozil A. 2018. Quasipolynomial set-based symbolic algorithms for parity games. 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning. LPAR: Logic for Programming, Artificial Intelligence and Reasoning, EPiC Series in Computing, vol. 57, 233–253.
[Published Version] View | Files available | DOI | arXiv
 
[132]
2018 | Published | Conference Paper | IST-REx-ID: 35 | OA
Chatterjee K, Dvorák W, Henzinger M, Svozil A. 2018. Algorithms and conditional lower bounds for planning problems. 28th International Conference on Automated Planning and Scheduling . ICAPS: International Conference on Automated Planning and Scheduling.
[Preprint] View | Files available | Download Preprint (ext.) | WoS | arXiv
 
[131]
2017 | Published | Conference Paper | IST-REx-ID: 11651 | OA
Wang D, Fountoulakis K, Henzinger M, Mahoney MW, Rao Satish. 2017. Capacity releasing diffusion for speed and locality. Proceedings of the 34th International Conference on Machine Learning. International Conference on Machine Learning, PMLR, vol. 70, 3598–3607.
[Published Version] View | Download Published Version (ext.) | arXiv
 
[130]
2017 | Published | Journal Article | IST-REx-ID: 11665 | OA
Henzinger M, Krinninger S, Nanongkai D. 2017. Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks. ACM Transactions on Algorithms. 13(4), 51.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[129]
2017 | Published | Journal Article | IST-REx-ID: 11676 | OA
Dvořák W, Henzinger M, Williamson DP. 2017. Maximizing a submodular function with viability constraints. Algorithmica. 77(1), 152–172.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[128]
2017 | Published | Conference Paper | IST-REx-ID: 11772
Henzinger M. 2017. The state of the art in dynamic graph algorithms. 44th International Conference on Current Trends in Theory and Practice of Computer Science. SOFSEM: Theory and Practice of Computer Science, LNCS, vol. 10706, 40–44.
View | DOI
 
[127]
2017 | Published | Conference Paper | IST-REx-ID: 11829 | OA
Henzinger M, Lincoln A, Neumann S, Vassilevska Williams V. 2017. Conditional hardness for sensitivity problems. 8th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science Conference, LIPIcs, vol. 67, 26.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[126]
2017 | Published | Conference Paper | IST-REx-ID: 11831 | OA
Goranci G, Henzinger M, Peng P. 2017. Improved guarantees for vertex sparsification in planar graphs. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 44.
[Published Version] View | Files available | DOI | Download Published Version (ext.) | arXiv
 
[125]
2017 | Published | Conference Paper | IST-REx-ID: 11832 | OA
Henzinger M, Leniowski D, Mathieu C. 2017. Dynamic clustering to minimize the sum of radii. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 48.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[124]
2017 | Published | Conference Paper | IST-REx-ID: 11833 | OA
Goranci G, Henzinger M, Peng P. 2017. The power of vertex sparsifiers in dynamic graph algorithms. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 45.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[123]
2017 | Published | Conference Paper | IST-REx-ID: 11873 | OA
Henzinger M, Rao S, Wang D. 2017. Local flow partitioning for faster edge connectivity. 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1919–1938.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[122]
2017 | Published | Conference Paper | IST-REx-ID: 11874 | OA
Bhattacharya S, Henzinger M, Nanongkai D. 2017. Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 0, 470–489.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[121]
2017 | Published | Journal Article | IST-REx-ID: 11903 | OA
Bhattacharya S, Dvořák W, Henzinger M, Starnberger M. 2017. Welfare maximization with friends-of-friends network externalities. Theory of Computing Systems. 61(4), 948–986.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[120]
2017 | Published | Conference Paper | IST-REx-ID: 12571 | OA
Bhattacharya S, Chakrabarty D, Henzinger M. 2017. Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. 19th International Conference on Integer Programming and Combinatorial Optimization. IPCO: Integer Programming and Combinatorial Optimization, LNCS, vol. 10328, 86–98.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[119]
2017 | Published | Journal Article | IST-REx-ID: 464 | OA
Chatterjee K, Henzinger M, Loitzenbauer V. 2017. Improved algorithms for parity and Streett objectives. Logical Methods in Computer Science. 13(3), 26.
[Published Version] View | Files available | DOI | arXiv
 
[118]
2017 | Published | Conference Paper | IST-REx-ID: 6519 | OA
Chatterjee K, Dvorák W, Henzinger M, Loitzenbauer V. 2017. Improved set-based symbolic algorithms for parity games. CSL: Conference on Computer Science Logic vol. 82, 18.
[Published Version] View | Files available | DOI
 
[117]
2017 | Published | Conference Paper | IST-REx-ID: 552 | OA
Chatterjee K, Henzinger M, Svozil A. 2017. Faster algorithms for mean-payoff parity games. Leibniz International Proceedings in Informatics. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 83, 39.
[Published Version] View | Files available | DOI
 
[116]
2016 | Published | Conference Paper | IST-REx-ID: 11834 | OA
Goranci G, Henzinger M, Thorup M. 2016. Incremental exact min-cut in poly-logarithmic amortized update time. 24th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 57, 46.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[115]
2016 | Published | Conference Paper | IST-REx-ID: 11835 | OA
Henzinger M, Neumann S. 2016. Incremental and fully dynamic subgraph connectivity for emergency planning. 24th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 57, 48.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[114]
2016 | Published | Conference Paper | IST-REx-ID: 11836 | OA
Cheung YK, Goranci G, Henzinger M. 2016. Graph minors for preserving terminal distances approximately - lower and upper bounds. 43rd International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 55, 131.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[113]
2016 | Published | Conference Paper | IST-REx-ID: 11866 | OA
Henzinger M, Krinninger S, Nanongkai D. 2016. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 489–498.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[112]
2016 | Published | Conference Paper | IST-REx-ID: 11867 | OA
Bhattacharya S, Henzinger M, Nanongkai D. 2016. New deterministic approximation algorithms for fully dynamic matching. 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 398–411.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[111]
2016 | Published | Journal Article | IST-REx-ID: 11891 | OA
Henzinger M, Krinninger S, Nanongkai D. 2016. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing. 45(3), 947–1006.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[110]
2016 | Published | Conference Paper | IST-REx-ID: 1140 | OA
Chatterjee K, Dvoák W, Henzinger M, Loitzenbauer V. 2016. Model and objective separation with conditional lower bounds: disjunction is harder than conjunction. Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, Proceedings Symposium on Logic in Computer Science, , 197–206.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[109]
2016 | Published | Conference Paper | IST-REx-ID: 1068 | OA
Chatterjee K, Dvorák W, Henzinger M, Loitzenbauer V. 2016. Conditionally optimal algorithms for generalized Büchi Games. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 58, 25.
[Published Version] View | Files available | DOI
 
[108]
2015 | Published | Journal Article | IST-REx-ID: 11668 | OA
Colini-Baldeschi R, Leonardi S, Henzinger M, Starnberger M. 2015. On multiple keyword sponsored search auctions with budgets. ACM Transactions on Economics and Computation. 4(1), 2.
[Submitted Version] View | DOI | Download Submitted Version (ext.)
 
[107]
2015 | Published | Journal Article | IST-REx-ID: 11669 | OA
Dütting P, Henzinger M, Starnberger M. 2015. Auctions for heterogeneous items and budget limits. ACM Transactions on Economics and Computation. 4(1), 4.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[106]
2015 | Published | Journal Article | IST-REx-ID: 11670
Dütting P, Henzinger M, Weber I. 2015. An expressive mechanism for auctions on the web. ACM Transactions on Economics and Computation. 4(1), 1.
View | DOI
 
[105]
2015 | Published | Conference Paper | IST-REx-ID: 11773 | OA
Ben-Zwi O, Henzinger M, Loitzenbauer V. 2015. Ad exchange: Envy-free auctions with mediators. 11th International Conference on Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 9470, 104–117.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[104]
2015 | Published | Conference Paper | IST-REx-ID: 11774 | OA
Cheung YK, Henzinger M, Hoefer M, Starnberger M. 2015. Combinatorial auctions with conflict-based externalities. 11th International Conference on Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 9470, 230–243.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[103]
2015 | Published | Conference Paper | IST-REx-ID: 11785 | OA
Henzinger M, Krinninger S, Nanongkai D. 2015. Improved algorithms for decremental single-source reachability on directed graphs. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 725–736.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[102]
2015 | Published | Conference Paper | IST-REx-ID: 11786 | OA
Bhattacharya S, Henzinger M, Italiano GF. 2015. Design of dynamic algorithms via primal-dual method. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 206–218.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[101]
2015 | Published | Conference Paper | IST-REx-ID: 11787 | OA
Henzinger M, Krinninger S, Loitzenbauer V. 2015. Finding 2-edge and 2-vertex strongly connected components in quadratic time. 2nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 713–724.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[100]
2015 | Published | Conference Paper | IST-REx-ID: 11788 | OA
Dvořák W, Henzinger M. 2015. Online ad assignment with an ad exchange. 12th International Workshop of Approximation and Online Algorithms. WAOA: International Workshop on Approximation and Online Algorithms, LNCS, vol. 8952, 156–167.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[99]
2015 | Published | Conference Paper | IST-REx-ID: 11837 | OA
Bhattacharya S, Dvorák W, Henzinger M, Starnberger Martin. 2015. Welfare maximization with friends-of-friends network externalities. 32nd International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 30, 90–102.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[98]
2015 | Published | Journal Article | IST-REx-ID: 11845 | OA
Chernomor O, Minh BQ, Forest F, Klaere S, Ingram T, Henzinger M, von Haeseler A. 2015. Split diversity in constrained conservation prioritization using integer linear programming. Methods in Ecology and Evolution. 6(1), 83–91.
[Published Version] View | Files available | DOI | PubMed | Europe PMC
 
[97]
2015 | Published | Conference Paper | IST-REx-ID: 11868 | OA
Henzinger M, Krinninger S, Nanongkai D, Saranurak T. 2015. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. 47th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 21–30.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[96]
2015 | Published | Conference Paper | IST-REx-ID: 11869 | OA
Bhattacharya S, Henzinger M, Nanongkai D, Tsourakakis C. 2015. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. 47th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 173–182.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[95]
2015 | Published | Journal Article | IST-REx-ID: 11901 | OA
Henzinger M, Loitzenbauer V. 2015. Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. 573, 1–15.
View | DOI | Download None (ext.)
 
[94]
2015 | Published | Conference Paper | IST-REx-ID: 1661 | OA
Chatterjee K, Henzinger M, Loitzenbauer V. 2015. Improved algorithms for one-pair and k-pair Streett objectives. Proceedings - Symposium on Logic in Computer Science. LICS: Logic in Computer Science vol. 2015–July, 7174888.
[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.)
 
[93]
2014 | Published | Conference Paper | IST-REx-ID: 11789 | OA
Charikar M, Henzinger M, Nguyễn HL. 2014. Online bipartite matching with decomposable weights. 22nd Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LNCS, vol. 8737, 260–271.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[92]
2014 | Published | Conference Paper | IST-REx-ID: 11790
Cigler L, Dvořák W, Henzinger M, Starnberger M. 2014. Limiting price discrimination when selling products with positive network externalities. 10th International Conference of Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 8877, 44–57.
View | DOI
 
[91]
2014 | Published | Conference Paper | IST-REx-ID: 11855 | OA
Henzinger M, Krinninger S, Nanongkai D. 2014. Decremental single-source shortest paths on undirected graphs in near-linear total update time. 55th Annual Symposium on Foundations of Computer Science. FOCS: Annual Symposium on Foundations of Computer Science, 146–155.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[90]
2014 | Published | Conference Paper | IST-REx-ID: 11870 | OA
Henzinger M, Krinninger S, Nanongkai D. 2014. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. 46th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 674–683.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[89]
2014 | Published | Conference Paper | IST-REx-ID: 11875 | OA
Bhattacharya S, Henzinger M, Italiano GF. 2014. Deterministic fully dynamic data structures for vertex cover and matching. 26th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 785–804.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[88]
2014 | Published | Conference Paper | IST-REx-ID: 11876 | OA
Henzinger M, Krinninger S, Nanongkai D. 2014. A subquadratic-time algorithm for decremental single-source shortest paths. 25th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1053–1072.
[Published Version] View | DOI | Download Published Version (ext.)
 
[87]
2014 | Published | Journal Article | IST-REx-ID: 1375 | OA
Chatterjee K, Henzinger M, Krinninger S, Loitzenbauer V, Raskin M. 2014. Approximating the minimum cycle mean. Theoretical Computer Science. 547(C), 104–116.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[86]
2014 | Published | Journal Article | IST-REx-ID: 535 | OA
Chatterjee K, Henzinger M, Krinninger S, Nanongkai D. 2014. Polynomial-time algorithms for energy games with special weight structures. Algorithmica. 70(3), 457–492.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[85]
2014 | Published | Journal Article | IST-REx-ID: 2141 | OA
Chatterjee K, Henzinger M. 2014. Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition. Journal of the ACM. 61(3), a15.
[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.)
 
[84]
2013 | Published | Journal Article | IST-REx-ID: 11671
Baykan E, Weber I, Henzinger M. 2013. A comprehensive study of techniques for URL-based web page language classification. ACM Transactions on the Web. 7(1), 3.
View | DOI
 
[83]
2013 | Published | Journal Article | IST-REx-ID: 11758
Aceto L, Henzinger M, Sgall J. 2013. 38th International Colloquium on Automata, Languages and Programming. Information and Computation. 222(1), 1.
View | DOI
 
[82]
2013 | Published | Journal Article | IST-REx-ID: 11759 | OA
Dütting P, Henzinger M, Weber I. 2013. Sponsored search, market equilibria, and the Hungarian Method. Information Processing Letters. 113(3), 67–73.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[81]
2013 | Published | Conference Paper | IST-REx-ID: 11791 | OA
Dütting P, Henzinger M, Starnberger M. 2013. Valuation compressions in VCG-based combinatorial auctions. 9th International Conference on Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 8289, 146–159.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[80]
2013 | Published | Conference Paper | IST-REx-ID: 11792 | OA
Dvořák W, Henzinger M, Williamson DP. 2013. Maximizing a submodular function with viability constraints. 21st Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 8125, 409–420.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[79]
2013 | Published | Conference Paper | IST-REx-ID: 11793 | OA
Henzinger M, Krinninger S, Nanongkai D. 2013. Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks. 40th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 7966, 607–619.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[78]
2013 | Published | Conference Paper | IST-REx-ID: 11856 | OA
Henzinger M, Krinninger S, Nanongkai D. 2013. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. 54th Annual Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science, 538–547.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[77]
2013 | Published | Journal Article | IST-REx-ID: 11902
Dütting P, Henzinger M, Weber I. 2013. Bidder optimal assignments for general utilities. Theoretical Computer Science. 478(3), 22–32.
View | Files available | DOI
 
[76]
2013 | Published | Journal Article | IST-REx-ID: 2831 | OA
Chatterjee K, Henzinger M, Joglekar M, Shah N. 2013. Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. Formal Methods in System Design. 42(3), 301–327.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[75]
2012 | Published | Conference Paper | IST-REx-ID: 11656
Dütting P, Henzinger M, Weber I. 2012. Maximizing revenue from strategic recommendations under decaying trust. Proceedings of the 21st ACM international conference on Information and knowledge management. CIKM: Conference on Information and Knowledge Management, 2268–2286.
View | DOI
 
[74]
2012 | Published | Conference Paper | IST-REx-ID: 11794 | OA
Dütting P, Henzinger M, Starnberger M. 2012. Auctions with heterogeneous items and budget limits. 8th International Workshop on Internet and Network Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 7695, 44–57.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[73]
2012 | Published | Conference Paper | IST-REx-ID: 11795
Colini-Baldeschi R, Henzinger M, Leonardi S, Starnberger M. 2012. On multiple keyword sponsored search auctions with budgets. 39th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 7392, 1–12.
View | Files available | DOI
 
[72]
2012 | Published | Conference Paper | IST-REx-ID: 10905 | OA
Chatterjee K, Henzinger M, Krinninger S, Nanongkai D. 2012. Polynomial-time algorithms for energy games with special weight structures. Algorithms – ESA 2012. ESA: European Symposium on Algorithms, LNCS, vol. 7501, 301–312.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[71]
2012 | Published | Conference Paper | IST-REx-ID: 3165 | OA
Chatterjee K, Henzinger M. 2012. An O(n2) time algorithm for alternating Büchi games. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1386–1399.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[70]
2011 | Published | Journal Article | IST-REx-ID: 11673
Baykan E, Henzinger M, Marian L, Weber I. 2011. A comprehensive study of features and algorithms for URL-based topic classification. ACM Transactions on the Web. 5(3), 15.
View | DOI
 
[69]
2011 | Published | Journal Article | IST-REx-ID: 11760
Dütting P, Henzinger M, Weber I. 2011. Offline file assignments for online load balancing. Information Processing Letters. 111(4), 178–183.
View | DOI
 
[68]
2011 | Published | Conference Paper | IST-REx-ID: 11796
Henzinger M, Vidali A. 2011. Multi-parameter mechanism design under budget and matroid constraints. 19th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 6942, 192–202.
View | DOI
 
[67]
2011 | Published | Conference Paper | IST-REx-ID: 11864
Dütting P, Henzinger M, Weber I. 2011. An expressive mechanism for auctions on the web. Proceedings of the 20th international conference on World wide web. WWW: International Conference on World Wide Web, 127–136.
View | DOI
 
[66]
2011 | Published | Conference Paper | IST-REx-ID: 3343 | OA
Chatterjee K, Henzinger M. 2011. Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification. SODA: Symposium on Discrete Algorithms, 1318–1336.
[Submitted Version] View | DOI | Download Submitted Version (ext.)
 
[65]
2011 | Published | Conference Paper | IST-REx-ID: 3342 | OA
Chatterjee K, Henzinger M, Joglekar M, Nisarg S. 2011. Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. CAV: Computer Aided Verification, LNCS, vol. 6806, 260–276.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[64]
2011 | Published | Technical Report | IST-REx-ID: 5379 | OA
Chatterjee K, Henzinger M. 2011. An O(n2) time algorithm for alternating Büchi games, IST Austria, 20p.
[Published Version] View | Files available | DOI
 
[63]
2010 | Published | Conference Paper | IST-REx-ID: 11797 | OA
Feldman J, Henzinger M, Korula N, Mirrokni VS, Stein C. 2010. Online stochastic packing applied to display ad allocation. 18th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 6346, 182–194.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[62]
2010 | Published | Conference Paper | IST-REx-ID: 11798
Dütting P, Henzinger M. 2010. Mechanisms for the marriage and the assignment game. 7th International Conference on Algorithms and Complexity. CIAC: International Conference on Algorithms and Complexity, LNCS, vol. 6078, 6–12.
View | DOI
 
[61]
2010 | Published | Conference Paper | IST-REx-ID: 11838 | OA
Dütting P, Henzinger M, Weber I. 2010. Sponsored search, market equilibria, and the Hungarian Method. 27th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 5, 287–298.
[Published Version] View | Files available | DOI | Download Published Version (ext.) | arXiv
 
[60]
2010 | Published | Conference Paper | IST-REx-ID: 11863
Dütting P, Henzinger M, Weber I. 2010. How much is your personal recommendation worth? Proceedings of the 19th international conference on World wide web . WWW: International Conference on World Wide Web, 1085–1086.
View | DOI
 
[59]
2010 | Published | Journal Article | IST-REx-ID: 11885
Henzinger M, Suñol J, Weber I. 2010. The stability of the h-index. Scientometrics. 84(2), 465–479.
View | DOI
 
[58]
2009 | Published | Conference Paper | IST-REx-ID: 11799
Dütting P, Henzinger M, Weber I. 2009. Bidder optimal assignments for general utilities. 5th International Workshop on Internet and Network Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 5929, 575–582.
View | Files available | DOI
 
[57]
2009 | Published | Conference Paper | IST-REx-ID: 11905
Baykan E, Henzinger M, Marian L, Weber I. 2009. Purely URL-based topic classification. 18th International World Wide Web Conference. WWW: Conference on World Wide Web, 1109–1110.
View | DOI
 
[56]
2009 | Published | Conference Paper | IST-REx-ID: 11906
Abdel Hamid O, Behzadi B, Christoph S, Henzinger M. 2009. Detecting the origin of text segments efficiently. 18th International World Wide Web Conference. WWW: International Conference on World Wide Web, 61–70.
View | DOI
 
[55]
2009 | Published | Conference Paper | IST-REx-ID: 11912 | OA
Baykan Eda, Henzinger M, Keller SF, de Castelberg S, Kinzler M. 2009. A comparison of techniques for sampling web pages. 26th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 3, 13–30.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[54]
2008 | Published | Journal Article | IST-REx-ID: 11878
Baykan E, Henzinger M, Weber I. 2008. Web page language identification based on URLs. Proceedings of the VLDB Endowment. 1(1), 176–187.
View | DOI
 
[53]
2007 | Published | Journal Article | IST-REx-ID: 11884
Henzinger M. 2007. Search technologies for the internet. Science. 317(5837), 468–471.
View | DOI | PubMed | Europe PMC
 
[52]
2007 | Published | Conference Paper | IST-REx-ID: 11924
Henzinger M. 2007. Combinatorial algorithms for web search engines: three success stories. 18th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1022–1026.
View
 
[51]
2006 | Published | Conference Paper | IST-REx-ID: 11929
Henzinger M. 2006. Finding near-duplicate web pages: A large-scale evaluation of algorithms. 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. SIGIR: International Conference on Research and Development in Information Retrieval, 284–291.
View | DOI
 
[50]
2005 | Published | Conference Paper | IST-REx-ID: 11698
Henzinger M. 2005. Hyperlink analysis on the world wide web. Proceedings of the 16th ACM conference on Hypertext and hypermedia. HYPERTEXT: Conference on Hypertext and Hypermedia, 1–3.
View | DOI
 
[49]
2005 | Published | Journal Article | IST-REx-ID: 11763 | OA
Goel A, Henzinger M, Plotkin S. 2005. An online throughput-competitive algorithm for multicast routing and admission control. Journal of Algorithms. 55(1), 1–20.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[48]
2005 | Published | Journal Article | IST-REx-ID: 11904
Henzinger M, Chang B-W, Milch B, Brin S. 2005. Query-free news search. World Wide Web. 8(2), 101–126.
View | Files available | DOI
 
[47]
2004 | Published | Journal Article | IST-REx-ID: 11762 | OA
Henzinger M. 2004. Algorithmic challenges in web search engines. Internet Mathematics. 1(1), 115–123.
[Published Version] View | DOI | Download Published Version (ext.)
 
[46]
2004 | Published | Conference Paper | IST-REx-ID: 11800
Henzinger M. 2004. The past, present, and future of web search engines. 31st International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 3142, 3.
View | DOI
 
[45]
2004 | Published | Conference Paper | IST-REx-ID: 11801
Henzinger M. 2004. Algorithmic aspects of web search engines. 2th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 3221, 3.
View | DOI
 
[44]
2004 | Published | Conference Paper | IST-REx-ID: 11859
Henzinger M. 2004. The past, present, and future of web information retrieval. SPIE Proceedings. Document Recognition and Retrieval XI vol. 5296, 23–26.
View | DOI
 
[43]
2004 | Published | Journal Article | IST-REx-ID: 11877 | OA
Henzinger M, Lawrence S. 2004. Extracting knowledge from the World Wide Web. Proceedings of the National Academy of Sciences. 101(suppl_1), 5186–5191.
[Published Version] View | DOI | Download Published Version (ext.) | PubMed | Europe PMC
 
[42]
2003 | Published | Journal Article | IST-REx-ID: 11764
Goel A, Henzinger M, Plotkin S, Tardos E. 2003. Scheduling data transfers in a network and the set scheduling problem. Journal of Algorithms. 48(2), 314–332.
View | DOI
 
[41]
2003 | Published | Journal Article | IST-REx-ID: 11766 | OA
Henzinger M, Leonardi S. 2003. Scheduling multicasts on unit-capacity trees and meshes. Journal of Computer and System Sciences. 66(3), 567–611.
[Published Version] View | DOI | Download Published Version (ext.)
 
[40]
2003 | Published | Conference Paper | IST-REx-ID: 11860
Henzinger M, Chang B-W, Milch B, Brin S. 2003. Query-free news search. Proceedings of the 12th international conference on World Wide Web. WWW: International Conference on World Wide Web, 1–10.
View | Files available | DOI
 
[39]
2003 | Published | Conference Paper | IST-REx-ID: 11897
Bharat K, Henzinger M. 2003. Improved algorithms for topic distillation in a hyperlinked environment. 21st annual international ACM SIGIR conference on Research and development in information retrieval. SIGIR: International Conference on Research and Development in Information Retrieval, 104–111.
View | DOI
 
[38]
2003 | Published | Conference Paper | IST-REx-ID: 11909 | OA
Henzinger M, Motwani R, Silverstein C. 2003. Challenges in web search engines. 18th International Joint Conference on Artificial Intelligence. IJCAI: International Joint Conference on Artificial Intelligence, 1573–1579.
[Published Version] View | Download Published Version (ext.)
 
[37]
2001 | Published | Journal Article | IST-REx-ID: 11755
Henzinger M. 2001. Hyperlink analysis for the Web. IEEE Internet Computing. 5(1), 45–50.
View | DOI | WoS
 
[36]
2001 | Published | Journal Article | IST-REx-ID: 11892
Henzinger M, King V. 2001. Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. 31(2), 364–374.
View | DOI
 
[35]
2001 | Published | Conference Paper | IST-REx-ID: 11914
Bharat K, Chang B-W, Henzinger M, Ruhl M. 2001. Who links to whom: Mining linkage between Web sites. 1st IEEE International Conference on Data Mining. ICMD: International Conference on Data Mining, 51–58.
View | DOI
 
[34]
2000 | Published | Journal Article | IST-REx-ID: 11683
Henzinger M, Rao S, Gabow HN. 2000. Computing vertex connectivity: New bounds from old techniques. Journal of Algorithms. 34(2), 222–250.
View | DOI
 
[33]
2000 | Published | Journal Article | IST-REx-ID: 11685
Henzinger M, Heydon A, Mitzenmacher M, Najork M. 2000. On near-uniform URL sampling. Computer Networks. 33(1–6), 295–308.
View | DOI
 
[32]
2000 | Published | Journal Article | IST-REx-ID: 11694
Albers S, Henzinger M. 2000. Exploring unknown environments. SIAM Journal on Computing. 29(4), 1164–1188.
View | DOI
 
[31]
2000 | Published | Journal Article | IST-REx-ID: 11770 | OA
Bharat K, Broder A, Dean J, Henzinger M. 2000. A comparison of techniques to find mirrored hosts on the WWW. Journal of the American Society for Information Science. 51(12), 1114–1122.
[Published Version] View | DOI | Download Published Version (ext.)
 
[30]
2000 | Published | Conference Paper | IST-REx-ID: 11802
Henzinger M. 2000. Web information retrieval - an algorithmic perspective. 8th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 1879, 1–8.
View | DOI
 
[29]
2000 | Published | Journal Article | IST-REx-ID: 11893
Henzinger M. 2000. Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. 29(6), 1761–1815.
View | DOI
 
[28]
1999 | Published | Journal Article | IST-REx-ID: 11679
Henzinger M, King V, Warnow T. 1999. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica. 24, 1–13.
View | Files available | DOI
 
[27]
1999 | Published | Journal Article | IST-REx-ID: 11687
Dean J, Henzinger M. 1999. Finding related pages in the world wide Web. Computer Networks. 31(11–16), 1467–1479.
View | DOI
 
[26]
1999 | Published | Journal Article | IST-REx-ID: 11688
Henzinger M, Heydon A, Mitzenmacher M, Najork M. 1999. Measuring index quality using random walks on the web. Computer Networks. 31(11–16), 1291–1303.
View | DOI
 
[25]
1999 | Published | Conference Paper | IST-REx-ID: 11691
Goel A, Henzinger M, Plotkin S, Tardos E. 1999. Scheduling data transfers in a network and the set scheduling problem. Proceedings of the 31st annual ACM symposium on Theory of computing. STOC: Symposium on Theory of Computing, 189–197.
View | DOI
 
[24]
1999 | Published | Journal Article | IST-REx-ID: 11769
Henzinger M, King V. 1999. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM. 46(4), 502–516.
View | DOI
 
[23]
1999 | Published | Journal Article | IST-REx-ID: 11895 | OA
Silverstein C, Marais H, Henzinger M, Moricz M. 1999. Analysis of a very large web search engine query log. ACM SIGIR Forum. 33(1), 6–12.
[Published Version] View | DOI | Download Published Version (ext.)
 
[22]
1999 | Published | Conference Paper | IST-REx-ID: 11925
Henzinger M, Leonardi  S. 1999. Scheduling multicasts on unit-capacity trees and meshes. 10th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 438–447.
View
 
[21]
1998 | Published | Journal Article | IST-REx-ID: 11680
Alberts D, Henzinger M. 1998. Average-case analysis of dynamic graph algorithms. Algorithmica. 20, 31–60.
View | Files available | DOI
 
[20]
1998 | Published | Journal Article | IST-REx-ID: 11681
Henzinger M, Fredman ML. 1998. Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica. 22(3), 351–362.
View | DOI
 
[19]
1998 | Published | Conference Paper | IST-REx-ID: 11682
Agarwal PK, EppsteinL. J. Guibas D, Henzinger M. 1998. Parametric and kinetic minimum spanning trees. Proceedings of the 39th Annual Symposium on Foundations of Computer Science. Annual IEEE Symposium on Foundations of Computer Science, 596–605.
View | DOI
 
[18]
1998 | Published | Conference Paper | IST-REx-ID: 11926
Goel A, Henzinger M, Plotkin S. 1998. An online throughput-competitive algorithm for multicast routing and admission control. 9th Annual ACM SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 97–106.
View | Files available
 
[17]
1997 | Published | Journal Article | IST-REx-ID: 11666
Anderson JM, Berc LM, Dean J, Ghemawat S, Henzinger M, Leung S-TA, Sites RL, Vandevoorde MT, Waldspurger CA, Weihl WE. 1997. Continuous profiling: Where have all the cycles gone? ACM Transactions on Computer Systems. 15(4), 357–390.
View | DOI
 
[16]
1997 | Published | Journal Article | IST-REx-ID: 11765
Henzinger M. 1997. A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. Journal of Algorithms. 24(1), 194–220.
View | DOI
 
[15]
1997 | Published | Journal Article | IST-REx-ID: 11767 | OA
Henzinger M, Klein P, Rao S, Subramanian S. 1997. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences. 55(1), 3–23.
[Published Version] View | DOI | Download Published Version (ext.)
 
[14]
1997 | Published | Conference Paper | IST-REx-ID: 11803
Henzinger M, King V. 1997. Maintaining minimum spanning trees in dynamic graphs. 24th International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 1256, 594–604.
View | DOI
 
[13]
1997 | Published | Journal Article | IST-REx-ID: 11849 | OA
Anderson JM, Berc LM, Dean J, Ghemawat S, Henzinger M, Leung S-TA, Sites RL, Vandevoorde MT, Waldspurger CA, Weihl WE. 1997. Continuous profiling: Where have all the cycles gone? ACM SIGOPS Operating Systems Review. 31(5), 1–14.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[12]
1997 | Published | Journal Article | IST-REx-ID: 11883
Henzinger M, Thorup M. 1997. Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Random Structures and Algorithms. 11(4), 369–379.
View | DOI
 
[11]
1996 | Published | Journal Article | IST-REx-ID: 11761
Henzinger M, Williamson DP. 1996. On the number of small cuts in a graph. Information Processing Letters. 59(1), 41–44.
View | DOI
 
[10]
1996 | Published | Conference Paper | IST-REx-ID: 11804
Henzinger M, Telle JA. 1996. Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning. 5th Scandinavian Workshop on Algorithm Theory. SWAT: Scandinavian Workshop on Algorithm Theory, LNCS, vol. 1097, 16–27.
View | DOI
 
[9]
1996 | Published | Conference Paper | IST-REx-ID: 11910
Henzinger M, Thorup M. 1996. Improved sampling with applications to dynamic graph algorithms. 23rd International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 1099, 290–299.
View | DOI
 
[8]
1996 | Published | Conference Paper | IST-REx-ID: 11927 | OA
Henzinger M, King V, Warnow T. 1996. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. 7th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 333–340.
[Published Version] View | Files available | Download Published Version (ext.)
 
[7]
1995 | Published | Journal Article | IST-REx-ID: 11677
Henzinger M. 1995. Fully dynamic biconnectivity in graphs. Algorithmica. 13(6), 503–538.
View | DOI
 
[6]
1995 | Published | Conference Paper | IST-REx-ID: 11684
Henzinger M, King V. 1995. Fully dynamic biconnectivity and transitive closure. Proceedings of IEEE 36th Annual Foundations of Computer Science. Foundations of Computer Science, 664–672.
View | DOI
 
[5]
1995 | Published | Conference Paper | IST-REx-ID: 11805
Henzinger M, Poutré H. 1995. Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. 3rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 979, 171–184.
View | DOI
 
[4]
1995 | Published | Conference Paper | IST-REx-ID: 11806
Henzinger M. 1995. Approximating minimum cuts under insertions. 22nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 944, 280–291.
View | DOI
 
[3]
1995 | Published | Conference Paper | IST-REx-ID: 11928 | OA
Alberts D, Henzinger M. 1995. Average case analysis of dynamic graph algorithms. 6th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 312–321.
[Published Version] View | Files available | Download Published Version (ext.)
 
[2]
1995 | Published | Conference Paper | IST-REx-ID: 4498
Henzinger M, Henzinger TA, Kopke P. 1995. Computing simulations on finite and infinite graphs. Proceedings of IEEE 36th Annual Foundations of Computer Science. FOCS: Foundations of Computer Science, 453–462.
View | DOI
 
[1]
1994 | Published | Conference Paper | IST-REx-ID: 11857
Henzinger M. 1994. Fully dynamic cycle-equivalence in graphs. 35th Annual Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science, 744–755.
View | DOI
 
Marked Publication(s)

Search

Filter Publications

Display / Sort

Citation Style: ISTA Annual Report

Export / Embed

Grants


213 Publications

Mark all

[213]
2025 | Published | Conference Paper | IST-REx-ID: 19038 | OA
Henzinger M, Upadhyay J. 2025. Improved differentially private continual observation using group algebra. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 5, 2951–2970.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[212]
2025 | Published | Journal Article | IST-REx-ID: 15121 | OA
Zheng DW, Henzinger M. 2025. Multiplicative auction algorithm for approximate maximum weight bipartite matching. Mathematical Programming. 210, 881–894.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | WoS | arXiv
 
[211]
2025 | Published | Conference Paper | IST-REx-ID: 19858 | OA
El-Hayek A, Hanauer K, Henzinger M. 2025. On b-matching and fully-dynamic maximum k-edge coloring. 4th Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 330, 4.
[Published Version] View | Files available | DOI | arXiv
 
[210]
2025 | Published | Conference Paper | IST-REx-ID: 19982 | OA
El-Hayek A, Henzinger M, Li J. 2025. Fully dynamic approximate minimum cut in subpolynomial time per operation. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 750–784.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[209]
2024 | Published | Conference Paper | IST-REx-ID: 18557 | OA
El-Hayek A, Henzinger M, Schmid S. 2024. Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. 38th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 319, 21.
[Published Version] View | Files available | DOI | arXiv
 
[208]
2024 | Published | Conference Paper | IST-REx-ID: 18156 | OA
Henzinger M, Sricharan AR, Steiner TA. 2024. Private counting of distinct elements in the turnstile model and extensions. International Conference on Approximation Algorithms for Combinatorial Optimization Problems . APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems, LIPIcs, vol. 317, 40.
[Published Version] View | Files available | DOI | arXiv
 
[207]
2024 | Published | Conference Paper | IST-REx-ID: 18308 | OA
La Tour MD, Henzinger M, Saulpic D. 2024. Fully dynamic k-means coreset in near-optimal update time. 32nd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 308, 100.
[Published Version] View | Files available | DOI | arXiv
 
[206]
2024 | Published | Conference Paper | IST-REx-ID: 18115 | OA
Axiotis K, Cohen-Addad V, Henzinger M, Jerome S, Mirrokni V, Saulpic D, Woodruff DP, Wunder M. 2024. Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond. Proceedings of the 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 2086–2107.
[Published Version] View | Download Published Version (ext.) | arXiv
 
[205]
2024 | Published | Conference Paper | IST-REx-ID: 15253 | OA
Henzinger M, Upadhyay J, Upadhyay S. 2024. A unifying framework for differentially private sums under continual observation. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2024, 995–1018.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[204]
2024 | Published | Conference Paper | IST-REx-ID: 14769 | OA
Henzinger M, Saulpic D, Sidl L. 2024. Experimental evaluation of fully dynamic k-means via coresets. 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments. ALENEX: Workshop on Algorithm Engineering and Experiments, 220–233.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[203]
2024 | Published | Conference Paper | IST-REx-ID: 18116 | OA
La Tour MD, Henzinger M, Saulpic D. 2024. Making old things new: A unified algorithm for differentially private clustering. Proceedings of the 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 12046–12086.
[Published Version] View | Download Published Version (ext.) | arXiv
 
[202]
2024 | Published | Conference Paper | IST-REx-ID: 18928 | OA
Henzinger M, Saha B, Seybold MP, Ye C. 2024. On the complexity of algorithms with predictions for dynamic graph problems. 15th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 287, 62:1-62:25.
[Published Version] View | Files available | DOI | arXiv
 
[201]
2024 | Published | Conference Paper | IST-REx-ID: 15093 | OA
Cultrera di Montesano S, Edelsbrunner H, Henzinger M, Ost L. 2024. Dynamically maintaining the persistent homology of time series. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SODA: Symposium on Discrete Algorithms, 243–295.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[200]
2024 | Published | Conference Paper | IST-REx-ID: 19512 | OA
Andersson JD, Henzinger M, Pagh R, Steiner TA, Upadhyay J. 2024. Continual counting with gradual privacy expiration. 38th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 37.
[Preprint] View | Download Preprint (ext.) | arXiv
 
[199]
2024 | Published | Conference Paper | IST-REx-ID: 18503 | OA
Henzinger M, Li J, Rao S, Wang D. 2024. Deterministic near-linear time minimum cut in weighted graphs. 35th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 3089–3139.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[198]
2024 | Published | Conference Paper | IST-REx-ID: 15008 | OA
Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. 2024. Electrical flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 287, 55.
[Published Version] View | Files available | DOI | arXiv
 
[197]
2024 | Published | Conference Paper | IST-REx-ID: 18906 | OA
Hanauer K, Henzinger M, Münk R, Räcke H, Vötsch M. 2024. Expander hierarchies for normalized cuts on graphs. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. KDD: Knowledge Discovery and Data Mining, 1016–1027.
[Published Version] View | Files available | DOI
 
[196]
2023 | Published | Journal Article | IST-REx-ID: 14043 | OA
Henzinger M, Jin B, Peng R, Williamson DP. 2023. A combinatorial cut-toggling algorithm for solving Laplacian linear systems. Algorithmica. 85, 2680–3716.
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[195]
2023 | Published | Conference Paper | IST-REx-ID: 15364 | OA
Charikar M, Hu L, Henzinger M, Vötsch M, Waingarten E. 2023. Simple, scalable and effective clustering via one-dimensional projections. 37th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, NeurIPS, vol. 36.
[Published Version] View | Files available | arXiv
 
[194]
2023 | Published | Journal Article | IST-REx-ID: 14558
Bhattacharya S, Henzinger M, Nanongkai D, Wu X. 2023. Deterministic near-optimal approximation algorithms for dynamic set cover. SIAM Journal on Computing. 52(5), 1132–1192.
View | DOI
 
[193]
2023 | Published | Conference Paper | IST-REx-ID: 14462 | OA
Fichtenberger H, Henzinger M, Upadhyay J. 2023. Constant matters: Fine-grained error bound on differentially private continual observation. Proceedings of the 40th International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 202, 10072–10092.
[Published Version] View | Download Published Version (ext.) | arXiv
 
[192]
2023 | Published | Conference Paper | IST-REx-ID: 13236 | OA
Zheng DW, Henzinger M. 2023. Multiplicative auction algorithm for approximate maximum weight bipartite matching. International Conference on Integer Programming and Combinatorial Optimization. IPCO: Integer Programming and Combinatorial Optimization, LNCS, vol. 13904, 453–465.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[191]
2023 | Published | Conference Paper | IST-REx-ID: 14085 | OA
Goranci G, Henzinger M. 2023. Efficient data structures for incremental exact and approximate maximum flow. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 69.
[Published Version] View | Files available | DOI | arXiv
 
[190]
2023 | Published | Conference Paper | IST-REx-ID: 12760 | OA
Henzinger M, Neumann S, Räcke H, Schmid S. 2023. Dynamic maintenance of monotone dynamic programs and applications. 40th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 254, 36.
[Published Version] View | Files available | DOI | arXiv
 
[189]
2023 | Published | Conference Paper | IST-REx-ID: 14086 | OA
Henzinger M, Liu P, Vondrák J, Zheng DW. 2023. Faster submodular maximization for several classes of matroids. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 74.
[Published Version] View | Files available | DOI | arXiv
 
[188]
2022 | Submitted | Preprint | IST-REx-ID: 14236 | OA
Goranci G, Henzinger M. Incremental approximate maximum flow in m1/2+o(1) update time. arXiv, 2211.09606.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[187]
2022 | Published | Journal Article | IST-REx-ID: 11662
Henzinger M, Peng P. 2022. Constant-time Dynamic (Δ +1)-Coloring. ACM Transactions on Algorithms. 18(2), 16.
View | DOI
 
[186]
2022 | Published | Conference Paper | IST-REx-ID: 11808 | OA
Hanauer K, Henzinger M, Schulz C. 2022. Recent advances in fully dynamic graph algorithms. 1st Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221, 1.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[185]
2022 | Published | Conference Paper | IST-REx-ID: 11812 | OA
Hanauer K, Henzinger M, Hua QC. 2022. Fully dynamic four-vertex subgraph counting. 1st Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221, 18.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[184]
2022 | Published | Conference Paper | IST-REx-ID: 11918
Henzinger M, Lincoln A, Saha B. 2022. The complexity of average-case dynamic subgraph counting. 33rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 459–498.
View | DOI
 
[183]
2022 | Published | Conference Paper | IST-REx-ID: 11930 | OA
Henzinger M, Noe A, Schulz C. 2022. Practical fully dynamic minimum cut algorithms. 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 13–26.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[182]
2022 | Published | Book Chapter | IST-REx-ID: 20062
Henzinger M. 2022.Fine-Grained Complexity Lower Bounds for Problems in Computer Aided Verification. In: Principles of Systems Design. vol. 13660, 292–305.
View | DOI
 
[181]
2021 | Published | Conference Paper | IST-REx-ID: 11649 | OA
Henzinger M, Paz A, Schmid S. 2021. On the complexity of weight-dynamic network algorithms. IFIP Networking Conference. IFIP: Networking.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[180]
2021 | Published | Journal Article | IST-REx-ID: 11663 | OA
Bernstein A, Forster S, Henzinger M. 2021. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms. 17(4), 29.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[179]
2021 | Published | Journal Article | IST-REx-ID: 11756 | OA
Henzinger M, Peng P. 2021. Constant-time dynamic weight approximation for minimum spanning forest. Information and Computation. 281(12), 104805.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[178]
2021 | Published | Conference Paper | IST-REx-ID: 11771 | OA
Henzinger M, Wu X. 2021. Upper and lower bounds for fully retroactive graph problems. 17th International Symposium on Algorithms and Data Structures. WADS: Workshop on Algorithms and Data Structures, LNCS, vol. 12808, 471–484.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[177]
2021 | Published | Conference Paper | IST-REx-ID: 11814 | OA
Fichtenberger H, Henzinger M, Ost W. 2021. Differentially private algorithms for graphs under continual observation. 29th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 204, 42.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[176]
2021 | Published | Journal Article | IST-REx-ID: 11886 | OA
Henzinger M, Krinninger S, Nanongkai D. 2021. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. 50(3), STOC16-98-STOC16-137.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[175]
2021 | Published | Conference Paper | IST-REx-ID: 11919 | OA
Bergamaschi T, Henzinger M, Gutenberg MP, Williams VV, Wein N. 2021. New techniques and fine-grained hardness for dynamic near-additive spanners. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1836–1855.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[174]
2021 | Published | Conference Paper | IST-REx-ID: 11920 | OA
Bhattacharya S, Henzinger M, Nanongkai D, Wu X. 2021. Dynamic set cover: Improved amortized and worst-case update time. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 2537–2549.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[173]
2021 | Published | Conference Paper | IST-REx-ID: 11923 | OA
Henzinger M, Neumann S, Räcke H, Schmid S. 2021. Tight bounds for online graph partitioning. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 2799–2818.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[172]
2021 | Published | Conference Paper | IST-REx-ID: 11931 | OA
Goranci G, Henzinger M, Leniowski D, Schulz C, Svozil A. 2021. Fully dynamic k-center clustering in low dimensional metrics. 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 143–153.
[Published Version] View | DOI | Download Published Version (ext.)
 
[171]
2021 | Published | Conference Paper | IST-REx-ID: 10054 | OA
Chatterjee K, Henzinger M, Kale SS, Svozil A. 2021. Faster algorithms for bounded liveness in graphs and game graphs. 48th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 198, 124.
[Published Version] View | Files available | DOI
 
[170]
2021 | Published | Conference Paper | IST-REx-ID: 10002 | OA
Chatterjee K, Dvorak W, Henzinger M, Svozil A. 2021. Symbolic time and space tradeoffs for probabilistic verification. Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 1–13.
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[169]
2021 | Published | Journal Article | IST-REx-ID: 9293 | OA
Chatterjee K, Dvořák W, Henzinger M, Svozil A. 2021. Algorithms and conditional lower bounds for planning problems. Artificial Intelligence. 297(8), 103499.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | WoS | arXiv
 
[168]
2020 | Published | Journal Article | IST-REx-ID: 11674 | OA
Henzinger M, Leniowski D, Mathieu C. 2020. Dynamic clustering to minimize the sum of radii. Algorithmica. 82(11), 3183–3194.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[167]
2020 | Published | Journal Article | IST-REx-ID: 11675 | OA
Bhattacharya S, Chakrabarty D, Henzinger M. 2020. Deterministic dynamic matching in O(1) update time. Algorithmica. 82(4), 1057–1080.
[Published Version] View | DOI | Download Published Version (ext.)
 
[166]
2020 | Published | Conference Paper | IST-REx-ID: 11816 | OA
Henzinger M, Shahbaz K, Paul R, Schulz C. 2020. Dynamic matching algorithms in practice. 8th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 58.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[165]
2020 | Published | Conference Paper | IST-REx-ID: 11818 | OA
Henzinger M, Kale S. 2020. Fully-dynamic coresets. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 57.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[164]
2020 | Published | Conference Paper | IST-REx-ID: 11819 | OA
Henzinger M, Noe A, Schulz C, Strash D. 2020. Finding all global minimum cuts in practice. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 59.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[163]
2020 | Published | Conference Paper | IST-REx-ID: 11822 | OA
Hanauer K, Henzinger M, Schulz C. 2020. Faster fully dynamic transitive closure in practice. 18th International Symposium on Experimental Algorithms. SEA: Symposium on Experimental Algorithms, LIPIcs, vol. 160, 14.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[162]
2020 | Published | Conference Paper | IST-REx-ID: 11824 | OA
Henzinger M, Neumann S, Wiese A. 2020. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 51.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[161]
2020 | Published | Conference Paper | IST-REx-ID: 11825 | OA
Henzinger M, Peng P. 2020. Constant-time dynamic (Δ+1)-coloring. 37th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 154, 53.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[160]
2020 | Published | Conference Paper | IST-REx-ID: 11852 | OA
Chen L, Goranci G, Henzinger M, Peng R, Saranurak T. 2020. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. 61st Annual Symposium on Foundations of Computer Science. FOCS: Annual Symposium on Foundations of Computer Science, 1135–1146.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[159]
2020 | Published | Conference Paper | IST-REx-ID: 11880 | OA
Hanauer K, Henzinger M, Schulz C. 2020. Fully dynamic single-source reachability in practice: An experimental study. 2020 Symposium on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 106–119.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[158]
2020 | Published | Conference Paper | IST-REx-ID: 11881 | OA
Henzinger M, Noe A, Schulz C. 2020. Shared-memory branch-and-reduce for multiterminal cuts. 2020 Symposium on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 42–55.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[157]
2020 | Published | Journal Article | IST-REx-ID: 11889
Henzinger M, Rao S, Wang D. 2020. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. 49(1), 1–36.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[156]
2020 | Published | Journal Article | IST-REx-ID: 11894 | OA
Goranci G, Henzinger M, Peng P. 2020. Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics. 34(1), 130–162.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[155]
2019 | Published | Conference Paper | IST-REx-ID: 11826 | OA
Ancona B, Henzinger M, Roditty L, Williams VV, Wein N. 2019. Algorithms and hardness for diameter in dynamic graphs. 46th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 132, 13.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[154]
2019 | Published | Book Chapter | IST-REx-ID: 11847
Biedermann S, Henzinger M, Schulz C, Schuster B. 2019.Vienna Graph Clustering. In: Protein-Protein Interaction Networks. Methods in Molecular Biology, vol. 2074, 215–231.
View | DOI | PubMed | Europe PMC
 
[153]
2019 | Published | Conference Paper | IST-REx-ID: 11850 | OA
Henzinger M, Neumann S, Schmid S. 2019. Efficient distributed workload (re-)embedding. SIGMETRICS’19: International Conference on Measurement and Modeling of Computer Systems. SIGMETRICS: International Conference on Measurement and Modeling of Computer Systems, 43–44.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[152]
2019 | Published | Conference Paper | IST-REx-ID: 11851
Henzinger M, Noe A, Schulz C. 2019. Shared-memory exact minimum cuts. 33rd International Parallel and Distributed Processing Symposium. IPDPS: International Parallel and Distributed Processing Symposium, 8820968.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[151]
2019 | Published | Conference Paper | IST-REx-ID: 11853 | OA
Bhattacharya S, Henzinger M, Nanongkai D. 2019. A new deterministic algorithm for dynamic set cover. 60th Annual Symposium on Foundations of Computer Science. FOCS: Annual Symposium on Foundations of Computer Science, 406–423.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[150]
2019 | Published | Conference Paper | IST-REx-ID: 11865 | OA
Daga M, Henzinger M, Nanongkai D, Saranurak T. 2019. Distributed edge connectivity in sublinear time. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 343–354.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[149]
2019 | Published | Conference Paper | IST-REx-ID: 11871 | OA
Bernstein A, Forster S, Henzinger M. 2019. A deamortization approach for dynamic spanner and dynamic maximal matching. 30th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1899–1918.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[148]
2019 | Published | Journal Article | IST-REx-ID: 11898 | OA
Bhattacharya S, Henzinger M, Neumann S. 2019. New amortized cell-probe lower bounds for dynamic problems. Theoretical Computer Science. 779, 72–87.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[147]
2019 | Published | Conference Paper | IST-REx-ID: 6887 | OA
Chatterjee K, Dvorák W, Henzinger M, Svozil A. 2019. Near-linear time algorithms for Streett objectives in graphs and MDPs. Leibniz International Proceedings in Informatics. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 140, 7.
[Published Version] View | Files available | DOI
 
[146]
2018 | Published | Journal Article | IST-REx-ID: 11657 | OA
Henzinger M, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms. ACM Journal of Experimental Algorithmics. 23, 1–22.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[145]
2018 | Published | Journal Article | IST-REx-ID: 11664 | OA
Goranci G, Henzinger M, Thorup M. 2018. Incremental exact min-cut in polylogarithmic amortized update time. ACM Transactions on Algorithms. 14(2), 17.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[144]
2018 | Published | Journal Article | IST-REx-ID: 11667 | OA
Dütting P, Henzinger M, Starnberger M. 2018. Valuation compressions in VCG-based combinatorial auctions. ACM Transactions on Economics and Computation. 6(2), 5.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[143]
2018 | Published | Journal Article | IST-REx-ID: 11757 | OA
Bhattacharya S, Henzinger M, Italiano G. 2018. Dynamic algorithms via the primal-dual method. Information and Computation. 261(08), 219–239.
[Published Version] View | DOI | Download Published Version (ext.)
 
[142]
2018 | Published | Journal Article | IST-REx-ID: 11768 | OA
Henzinger M, Krinninger S, Nanongkai D. 2018. Decremental single-source shortest paths on undirected graphs in near-linear total update time. Journal of the ACM. 65(6), 1–40.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[141]
2018 | Published | Conference Paper | IST-REx-ID: 11827 | OA
Goranci G, Henzinger M, Leniowski D. 2018. A tree structure for dynamic facility location. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 39.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[140]
2018 | Published | Conference Paper | IST-REx-ID: 11828 | OA
Goranci G, Henzinger M, Peng P. 2018. Dynamic effective resistances and approximate schur complement on separable graphs. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 40.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[139]
2018 | Published | Conference Paper | IST-REx-ID: 11872 | OA
Bhattacharya S, Chakrabarty D, Henzinger M, Nanongkai D. 2018. Dynamic algorithms for graph coloring. 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1–20.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[138]
2018 | Published | Conference Paper | IST-REx-ID: 11882 | OA
Henzinger M, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms. 20th Workshop on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 48–61.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[137]
2018 | Published | Journal Article | IST-REx-ID: 11890 | OA
Bhattacharya S, Henzinger M, Italiano GF. 2018. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 47(3), 859–887.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[136]
2018 | Published | Conference Paper | IST-REx-ID: 11911 | OA
Biedermann S, Henzinger M, Schulz C, Schuster B. 2018. Memetic graph clustering. 17th International Symposium on Experimental Algorithms. SEA: Symposium on Experimental Algorithms, LIPIcs, vol. 103, 3.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[135]
2018 | Published | Conference Paper | IST-REx-ID: 310 | OA
Chatterjee K, Dvorák W, Henzinger M, Loitzenbauer V. 2018. Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety, and diameter. SODA: Symposium on Discrete Algorithms, 2341–2356.
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[134]
2018 | Published | Conference Paper | IST-REx-ID: 141 | OA
Chatterjee K, Henzinger M, Loitzenbauer V, Oraee S, Toman V. 2018. Symbolic algorithms for graphs and Markov decision processes with fairness objectives. CAV: Computer Aided Verification, LNCS, vol. 10982, 178–197.
[Published Version] View | Files available | DOI | WoS
 
[133]
2018 | Published | Conference Paper | IST-REx-ID: 10883 | OA
Chatterjee K, Dvořák W, Henzinger M, Svozil A. 2018. Quasipolynomial set-based symbolic algorithms for parity games. 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning. LPAR: Logic for Programming, Artificial Intelligence and Reasoning, EPiC Series in Computing, vol. 57, 233–253.
[Published Version] View | Files available | DOI | arXiv
 
[132]
2018 | Published | Conference Paper | IST-REx-ID: 35 | OA
Chatterjee K, Dvorák W, Henzinger M, Svozil A. 2018. Algorithms and conditional lower bounds for planning problems. 28th International Conference on Automated Planning and Scheduling . ICAPS: International Conference on Automated Planning and Scheduling.
[Preprint] View | Files available | Download Preprint (ext.) | WoS | arXiv
 
[131]
2017 | Published | Conference Paper | IST-REx-ID: 11651 | OA
Wang D, Fountoulakis K, Henzinger M, Mahoney MW, Rao Satish. 2017. Capacity releasing diffusion for speed and locality. Proceedings of the 34th International Conference on Machine Learning. International Conference on Machine Learning, PMLR, vol. 70, 3598–3607.
[Published Version] View | Download Published Version (ext.) | arXiv
 
[130]
2017 | Published | Journal Article | IST-REx-ID: 11665 | OA
Henzinger M, Krinninger S, Nanongkai D. 2017. Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks. ACM Transactions on Algorithms. 13(4), 51.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[129]
2017 | Published | Journal Article | IST-REx-ID: 11676 | OA
Dvořák W, Henzinger M, Williamson DP. 2017. Maximizing a submodular function with viability constraints. Algorithmica. 77(1), 152–172.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[128]
2017 | Published | Conference Paper | IST-REx-ID: 11772
Henzinger M. 2017. The state of the art in dynamic graph algorithms. 44th International Conference on Current Trends in Theory and Practice of Computer Science. SOFSEM: Theory and Practice of Computer Science, LNCS, vol. 10706, 40–44.
View | DOI
 
[127]
2017 | Published | Conference Paper | IST-REx-ID: 11829 | OA
Henzinger M, Lincoln A, Neumann S, Vassilevska Williams V. 2017. Conditional hardness for sensitivity problems. 8th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science Conference, LIPIcs, vol. 67, 26.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[126]
2017 | Published | Conference Paper | IST-REx-ID: 11831 | OA
Goranci G, Henzinger M, Peng P. 2017. Improved guarantees for vertex sparsification in planar graphs. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 44.
[Published Version] View | Files available | DOI | Download Published Version (ext.) | arXiv
 
[125]
2017 | Published | Conference Paper | IST-REx-ID: 11832 | OA
Henzinger M, Leniowski D, Mathieu C. 2017. Dynamic clustering to minimize the sum of radii. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 48.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[124]
2017 | Published | Conference Paper | IST-REx-ID: 11833 | OA
Goranci G, Henzinger M, Peng P. 2017. The power of vertex sparsifiers in dynamic graph algorithms. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 45.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[123]
2017 | Published | Conference Paper | IST-REx-ID: 11873 | OA
Henzinger M, Rao S, Wang D. 2017. Local flow partitioning for faster edge connectivity. 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1919–1938.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[122]
2017 | Published | Conference Paper | IST-REx-ID: 11874 | OA
Bhattacharya S, Henzinger M, Nanongkai D. 2017. Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 0, 470–489.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[121]
2017 | Published | Journal Article | IST-REx-ID: 11903 | OA
Bhattacharya S, Dvořák W, Henzinger M, Starnberger M. 2017. Welfare maximization with friends-of-friends network externalities. Theory of Computing Systems. 61(4), 948–986.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[120]
2017 | Published | Conference Paper | IST-REx-ID: 12571 | OA
Bhattacharya S, Chakrabarty D, Henzinger M. 2017. Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. 19th International Conference on Integer Programming and Combinatorial Optimization. IPCO: Integer Programming and Combinatorial Optimization, LNCS, vol. 10328, 86–98.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[119]
2017 | Published | Journal Article | IST-REx-ID: 464 | OA
Chatterjee K, Henzinger M, Loitzenbauer V. 2017. Improved algorithms for parity and Streett objectives. Logical Methods in Computer Science. 13(3), 26.
[Published Version] View | Files available | DOI | arXiv
 
[118]
2017 | Published | Conference Paper | IST-REx-ID: 6519 | OA
Chatterjee K, Dvorák W, Henzinger M, Loitzenbauer V. 2017. Improved set-based symbolic algorithms for parity games. CSL: Conference on Computer Science Logic vol. 82, 18.
[Published Version] View | Files available | DOI
 
[117]
2017 | Published | Conference Paper | IST-REx-ID: 552 | OA
Chatterjee K, Henzinger M, Svozil A. 2017. Faster algorithms for mean-payoff parity games. Leibniz International Proceedings in Informatics. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 83, 39.
[Published Version] View | Files available | DOI
 
[116]
2016 | Published | Conference Paper | IST-REx-ID: 11834 | OA
Goranci G, Henzinger M, Thorup M. 2016. Incremental exact min-cut in poly-logarithmic amortized update time. 24th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 57, 46.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[115]
2016 | Published | Conference Paper | IST-REx-ID: 11835 | OA
Henzinger M, Neumann S. 2016. Incremental and fully dynamic subgraph connectivity for emergency planning. 24th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 57, 48.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[114]
2016 | Published | Conference Paper | IST-REx-ID: 11836 | OA
Cheung YK, Goranci G, Henzinger M. 2016. Graph minors for preserving terminal distances approximately - lower and upper bounds. 43rd International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 55, 131.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[113]
2016 | Published | Conference Paper | IST-REx-ID: 11866 | OA
Henzinger M, Krinninger S, Nanongkai D. 2016. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 489–498.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[112]
2016 | Published | Conference Paper | IST-REx-ID: 11867 | OA
Bhattacharya S, Henzinger M, Nanongkai D. 2016. New deterministic approximation algorithms for fully dynamic matching. 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 398–411.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[111]
2016 | Published | Journal Article | IST-REx-ID: 11891 | OA
Henzinger M, Krinninger S, Nanongkai D. 2016. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing. 45(3), 947–1006.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[110]
2016 | Published | Conference Paper | IST-REx-ID: 1140 | OA
Chatterjee K, Dvoák W, Henzinger M, Loitzenbauer V. 2016. Model and objective separation with conditional lower bounds: disjunction is harder than conjunction. Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, Proceedings Symposium on Logic in Computer Science, , 197–206.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[109]
2016 | Published | Conference Paper | IST-REx-ID: 1068 | OA
Chatterjee K, Dvorák W, Henzinger M, Loitzenbauer V. 2016. Conditionally optimal algorithms for generalized Büchi Games. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 58, 25.
[Published Version] View | Files available | DOI
 
[108]
2015 | Published | Journal Article | IST-REx-ID: 11668 | OA
Colini-Baldeschi R, Leonardi S, Henzinger M, Starnberger M. 2015. On multiple keyword sponsored search auctions with budgets. ACM Transactions on Economics and Computation. 4(1), 2.
[Submitted Version] View | DOI | Download Submitted Version (ext.)
 
[107]
2015 | Published | Journal Article | IST-REx-ID: 11669 | OA
Dütting P, Henzinger M, Starnberger M. 2015. Auctions for heterogeneous items and budget limits. ACM Transactions on Economics and Computation. 4(1), 4.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[106]
2015 | Published | Journal Article | IST-REx-ID: 11670
Dütting P, Henzinger M, Weber I. 2015. An expressive mechanism for auctions on the web. ACM Transactions on Economics and Computation. 4(1), 1.
View | DOI
 
[105]
2015 | Published | Conference Paper | IST-REx-ID: 11773 | OA
Ben-Zwi O, Henzinger M, Loitzenbauer V. 2015. Ad exchange: Envy-free auctions with mediators. 11th International Conference on Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 9470, 104–117.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[104]
2015 | Published | Conference Paper | IST-REx-ID: 11774 | OA
Cheung YK, Henzinger M, Hoefer M, Starnberger M. 2015. Combinatorial auctions with conflict-based externalities. 11th International Conference on Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 9470, 230–243.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[103]
2015 | Published | Conference Paper | IST-REx-ID: 11785 | OA
Henzinger M, Krinninger S, Nanongkai D. 2015. Improved algorithms for decremental single-source reachability on directed graphs. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 725–736.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[102]
2015 | Published | Conference Paper | IST-REx-ID: 11786 | OA
Bhattacharya S, Henzinger M, Italiano GF. 2015. Design of dynamic algorithms via primal-dual method. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 206–218.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[101]
2015 | Published | Conference Paper | IST-REx-ID: 11787 | OA
Henzinger M, Krinninger S, Loitzenbauer V. 2015. Finding 2-edge and 2-vertex strongly connected components in quadratic time. 2nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 713–724.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[100]
2015 | Published | Conference Paper | IST-REx-ID: 11788 | OA
Dvořák W, Henzinger M. 2015. Online ad assignment with an ad exchange. 12th International Workshop of Approximation and Online Algorithms. WAOA: International Workshop on Approximation and Online Algorithms, LNCS, vol. 8952, 156–167.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[99]
2015 | Published | Conference Paper | IST-REx-ID: 11837 | OA
Bhattacharya S, Dvorák W, Henzinger M, Starnberger Martin. 2015. Welfare maximization with friends-of-friends network externalities. 32nd International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 30, 90–102.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[98]
2015 | Published | Journal Article | IST-REx-ID: 11845 | OA
Chernomor O, Minh BQ, Forest F, Klaere S, Ingram T, Henzinger M, von Haeseler A. 2015. Split diversity in constrained conservation prioritization using integer linear programming. Methods in Ecology and Evolution. 6(1), 83–91.
[Published Version] View | Files available | DOI | PubMed | Europe PMC
 
[97]
2015 | Published | Conference Paper | IST-REx-ID: 11868 | OA
Henzinger M, Krinninger S, Nanongkai D, Saranurak T. 2015. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. 47th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 21–30.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[96]
2015 | Published | Conference Paper | IST-REx-ID: 11869 | OA
Bhattacharya S, Henzinger M, Nanongkai D, Tsourakakis C. 2015. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. 47th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 173–182.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[95]
2015 | Published | Journal Article | IST-REx-ID: 11901 | OA
Henzinger M, Loitzenbauer V. 2015. Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. 573, 1–15.
View | DOI | Download None (ext.)
 
[94]
2015 | Published | Conference Paper | IST-REx-ID: 1661 | OA
Chatterjee K, Henzinger M, Loitzenbauer V. 2015. Improved algorithms for one-pair and k-pair Streett objectives. Proceedings - Symposium on Logic in Computer Science. LICS: Logic in Computer Science vol. 2015–July, 7174888.
[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.)
 
[93]
2014 | Published | Conference Paper | IST-REx-ID: 11789 | OA
Charikar M, Henzinger M, Nguyễn HL. 2014. Online bipartite matching with decomposable weights. 22nd Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LNCS, vol. 8737, 260–271.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[92]
2014 | Published | Conference Paper | IST-REx-ID: 11790
Cigler L, Dvořák W, Henzinger M, Starnberger M. 2014. Limiting price discrimination when selling products with positive network externalities. 10th International Conference of Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 8877, 44–57.
View | DOI
 
[91]
2014 | Published | Conference Paper | IST-REx-ID: 11855 | OA
Henzinger M, Krinninger S, Nanongkai D. 2014. Decremental single-source shortest paths on undirected graphs in near-linear total update time. 55th Annual Symposium on Foundations of Computer Science. FOCS: Annual Symposium on Foundations of Computer Science, 146–155.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[90]
2014 | Published | Conference Paper | IST-REx-ID: 11870 | OA
Henzinger M, Krinninger S, Nanongkai D. 2014. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. 46th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 674–683.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[89]
2014 | Published | Conference Paper | IST-REx-ID: 11875 | OA
Bhattacharya S, Henzinger M, Italiano GF. 2014. Deterministic fully dynamic data structures for vertex cover and matching. 26th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 785–804.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[88]
2014 | Published | Conference Paper | IST-REx-ID: 11876 | OA
Henzinger M, Krinninger S, Nanongkai D. 2014. A subquadratic-time algorithm for decremental single-source shortest paths. 25th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1053–1072.
[Published Version] View | DOI | Download Published Version (ext.)
 
[87]
2014 | Published | Journal Article | IST-REx-ID: 1375 | OA
Chatterjee K, Henzinger M, Krinninger S, Loitzenbauer V, Raskin M. 2014. Approximating the minimum cycle mean. Theoretical Computer Science. 547(C), 104–116.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[86]
2014 | Published | Journal Article | IST-REx-ID: 535 | OA
Chatterjee K, Henzinger M, Krinninger S, Nanongkai D. 2014. Polynomial-time algorithms for energy games with special weight structures. Algorithmica. 70(3), 457–492.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[85]
2014 | Published | Journal Article | IST-REx-ID: 2141 | OA
Chatterjee K, Henzinger M. 2014. Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition. Journal of the ACM. 61(3), a15.
[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.)
 
[84]
2013 | Published | Journal Article | IST-REx-ID: 11671
Baykan E, Weber I, Henzinger M. 2013. A comprehensive study of techniques for URL-based web page language classification. ACM Transactions on the Web. 7(1), 3.
View | DOI
 
[83]
2013 | Published | Journal Article | IST-REx-ID: 11758
Aceto L, Henzinger M, Sgall J. 2013. 38th International Colloquium on Automata, Languages and Programming. Information and Computation. 222(1), 1.
View | DOI
 
[82]
2013 | Published | Journal Article | IST-REx-ID: 11759 | OA
Dütting P, Henzinger M, Weber I. 2013. Sponsored search, market equilibria, and the Hungarian Method. Information Processing Letters. 113(3), 67–73.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[81]
2013 | Published | Conference Paper | IST-REx-ID: 11791 | OA
Dütting P, Henzinger M, Starnberger M. 2013. Valuation compressions in VCG-based combinatorial auctions. 9th International Conference on Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 8289, 146–159.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[80]
2013 | Published | Conference Paper | IST-REx-ID: 11792 | OA
Dvořák W, Henzinger M, Williamson DP. 2013. Maximizing a submodular function with viability constraints. 21st Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 8125, 409–420.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[79]
2013 | Published | Conference Paper | IST-REx-ID: 11793 | OA
Henzinger M, Krinninger S, Nanongkai D. 2013. Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks. 40th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 7966, 607–619.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[78]
2013 | Published | Conference Paper | IST-REx-ID: 11856 | OA
Henzinger M, Krinninger S, Nanongkai D. 2013. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. 54th Annual Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science, 538–547.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[77]
2013 | Published | Journal Article | IST-REx-ID: 11902
Dütting P, Henzinger M, Weber I. 2013. Bidder optimal assignments for general utilities. Theoretical Computer Science. 478(3), 22–32.
View | Files available | DOI
 
[76]
2013 | Published | Journal Article | IST-REx-ID: 2831 | OA
Chatterjee K, Henzinger M, Joglekar M, Shah N. 2013. Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. Formal Methods in System Design. 42(3), 301–327.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[75]
2012 | Published | Conference Paper | IST-REx-ID: 11656
Dütting P, Henzinger M, Weber I. 2012. Maximizing revenue from strategic recommendations under decaying trust. Proceedings of the 21st ACM international conference on Information and knowledge management. CIKM: Conference on Information and Knowledge Management, 2268–2286.
View | DOI
 
[74]
2012 | Published | Conference Paper | IST-REx-ID: 11794 | OA
Dütting P, Henzinger M, Starnberger M. 2012. Auctions with heterogeneous items and budget limits. 8th International Workshop on Internet and Network Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 7695, 44–57.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[73]
2012 | Published | Conference Paper | IST-REx-ID: 11795
Colini-Baldeschi R, Henzinger M, Leonardi S, Starnberger M. 2012. On multiple keyword sponsored search auctions with budgets. 39th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 7392, 1–12.
View | Files available | DOI
 
[72]
2012 | Published | Conference Paper | IST-REx-ID: 10905 | OA
Chatterjee K, Henzinger M, Krinninger S, Nanongkai D. 2012. Polynomial-time algorithms for energy games with special weight structures. Algorithms – ESA 2012. ESA: European Symposium on Algorithms, LNCS, vol. 7501, 301–312.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[71]
2012 | Published | Conference Paper | IST-REx-ID: 3165 | OA
Chatterjee K, Henzinger M. 2012. An O(n2) time algorithm for alternating Büchi games. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1386–1399.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[70]
2011 | Published | Journal Article | IST-REx-ID: 11673
Baykan E, Henzinger M, Marian L, Weber I. 2011. A comprehensive study of features and algorithms for URL-based topic classification. ACM Transactions on the Web. 5(3), 15.
View | DOI
 
[69]
2011 | Published | Journal Article | IST-REx-ID: 11760
Dütting P, Henzinger M, Weber I. 2011. Offline file assignments for online load balancing. Information Processing Letters. 111(4), 178–183.
View | DOI
 
[68]
2011 | Published | Conference Paper | IST-REx-ID: 11796
Henzinger M, Vidali A. 2011. Multi-parameter mechanism design under budget and matroid constraints. 19th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 6942, 192–202.
View | DOI
 
[67]
2011 | Published | Conference Paper | IST-REx-ID: 11864
Dütting P, Henzinger M, Weber I. 2011. An expressive mechanism for auctions on the web. Proceedings of the 20th international conference on World wide web. WWW: International Conference on World Wide Web, 127–136.
View | DOI
 
[66]
2011 | Published | Conference Paper | IST-REx-ID: 3343 | OA
Chatterjee K, Henzinger M. 2011. Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification. SODA: Symposium on Discrete Algorithms, 1318–1336.
[Submitted Version] View | DOI | Download Submitted Version (ext.)
 
[65]
2011 | Published | Conference Paper | IST-REx-ID: 3342 | OA
Chatterjee K, Henzinger M, Joglekar M, Nisarg S. 2011. Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. CAV: Computer Aided Verification, LNCS, vol. 6806, 260–276.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[64]
2011 | Published | Technical Report | IST-REx-ID: 5379 | OA
Chatterjee K, Henzinger M. 2011. An O(n2) time algorithm for alternating Büchi games, IST Austria, 20p.
[Published Version] View | Files available | DOI
 
[63]
2010 | Published | Conference Paper | IST-REx-ID: 11797 | OA
Feldman J, Henzinger M, Korula N, Mirrokni VS, Stein C. 2010. Online stochastic packing applied to display ad allocation. 18th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 6346, 182–194.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[62]
2010 | Published | Conference Paper | IST-REx-ID: 11798
Dütting P, Henzinger M. 2010. Mechanisms for the marriage and the assignment game. 7th International Conference on Algorithms and Complexity. CIAC: International Conference on Algorithms and Complexity, LNCS, vol. 6078, 6–12.
View | DOI
 
[61]
2010 | Published | Conference Paper | IST-REx-ID: 11838 | OA
Dütting P, Henzinger M, Weber I. 2010. Sponsored search, market equilibria, and the Hungarian Method. 27th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 5, 287–298.
[Published Version] View | Files available | DOI | Download Published Version (ext.) | arXiv
 
[60]
2010 | Published | Conference Paper | IST-REx-ID: 11863
Dütting P, Henzinger M, Weber I. 2010. How much is your personal recommendation worth? Proceedings of the 19th international conference on World wide web . WWW: International Conference on World Wide Web, 1085–1086.
View | DOI
 
[59]
2010 | Published | Journal Article | IST-REx-ID: 11885
Henzinger M, Suñol J, Weber I. 2010. The stability of the h-index. Scientometrics. 84(2), 465–479.
View | DOI
 
[58]
2009 | Published | Conference Paper | IST-REx-ID: 11799
Dütting P, Henzinger M, Weber I. 2009. Bidder optimal assignments for general utilities. 5th International Workshop on Internet and Network Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 5929, 575–582.
View | Files available | DOI
 
[57]
2009 | Published | Conference Paper | IST-REx-ID: 11905
Baykan E, Henzinger M, Marian L, Weber I. 2009. Purely URL-based topic classification. 18th International World Wide Web Conference. WWW: Conference on World Wide Web, 1109–1110.
View | DOI
 
[56]
2009 | Published | Conference Paper | IST-REx-ID: 11906
Abdel Hamid O, Behzadi B, Christoph S, Henzinger M. 2009. Detecting the origin of text segments efficiently. 18th International World Wide Web Conference. WWW: International Conference on World Wide Web, 61–70.
View | DOI
 
[55]
2009 | Published | Conference Paper | IST-REx-ID: 11912 | OA
Baykan Eda, Henzinger M, Keller SF, de Castelberg S, Kinzler M. 2009. A comparison of techniques for sampling web pages. 26th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 3, 13–30.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[54]
2008 | Published | Journal Article | IST-REx-ID: 11878
Baykan E, Henzinger M, Weber I. 2008. Web page language identification based on URLs. Proceedings of the VLDB Endowment. 1(1), 176–187.
View | DOI
 
[53]
2007 | Published | Journal Article | IST-REx-ID: 11884
Henzinger M. 2007. Search technologies for the internet. Science. 317(5837), 468–471.
View | DOI | PubMed | Europe PMC
 
[52]
2007 | Published | Conference Paper | IST-REx-ID: 11924
Henzinger M. 2007. Combinatorial algorithms for web search engines: three success stories. 18th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1022–1026.
View
 
[51]
2006 | Published | Conference Paper | IST-REx-ID: 11929
Henzinger M. 2006. Finding near-duplicate web pages: A large-scale evaluation of algorithms. 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. SIGIR: International Conference on Research and Development in Information Retrieval, 284–291.
View | DOI
 
[50]
2005 | Published | Conference Paper | IST-REx-ID: 11698
Henzinger M. 2005. Hyperlink analysis on the world wide web. Proceedings of the 16th ACM conference on Hypertext and hypermedia. HYPERTEXT: Conference on Hypertext and Hypermedia, 1–3.
View | DOI
 
[49]
2005 | Published | Journal Article | IST-REx-ID: 11763 | OA
Goel A, Henzinger M, Plotkin S. 2005. An online throughput-competitive algorithm for multicast routing and admission control. Journal of Algorithms. 55(1), 1–20.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[48]
2005 | Published | Journal Article | IST-REx-ID: 11904
Henzinger M, Chang B-W, Milch B, Brin S. 2005. Query-free news search. World Wide Web. 8(2), 101–126.
View | Files available | DOI
 
[47]
2004 | Published | Journal Article | IST-REx-ID: 11762 | OA
Henzinger M. 2004. Algorithmic challenges in web search engines. Internet Mathematics. 1(1), 115–123.
[Published Version] View | DOI | Download Published Version (ext.)
 
[46]
2004 | Published | Conference Paper | IST-REx-ID: 11800
Henzinger M. 2004. The past, present, and future of web search engines. 31st International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 3142, 3.
View | DOI
 
[45]
2004 | Published | Conference Paper | IST-REx-ID: 11801
Henzinger M. 2004. Algorithmic aspects of web search engines. 2th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 3221, 3.
View | DOI
 
[44]
2004 | Published | Conference Paper | IST-REx-ID: 11859
Henzinger M. 2004. The past, present, and future of web information retrieval. SPIE Proceedings. Document Recognition and Retrieval XI vol. 5296, 23–26.
View | DOI
 
[43]
2004 | Published | Journal Article | IST-REx-ID: 11877 | OA
Henzinger M, Lawrence S. 2004. Extracting knowledge from the World Wide Web. Proceedings of the National Academy of Sciences. 101(suppl_1), 5186–5191.
[Published Version] View | DOI | Download Published Version (ext.) | PubMed | Europe PMC
 
[42]
2003 | Published | Journal Article | IST-REx-ID: 11764
Goel A, Henzinger M, Plotkin S, Tardos E. 2003. Scheduling data transfers in a network and the set scheduling problem. Journal of Algorithms. 48(2), 314–332.
View | DOI
 
[41]
2003 | Published | Journal Article | IST-REx-ID: 11766 | OA
Henzinger M, Leonardi S. 2003. Scheduling multicasts on unit-capacity trees and meshes. Journal of Computer and System Sciences. 66(3), 567–611.
[Published Version] View | DOI | Download Published Version (ext.)
 
[40]
2003 | Published | Conference Paper | IST-REx-ID: 11860
Henzinger M, Chang B-W, Milch B, Brin S. 2003. Query-free news search. Proceedings of the 12th international conference on World Wide Web. WWW: International Conference on World Wide Web, 1–10.
View | Files available | DOI
 
[39]
2003 | Published | Conference Paper | IST-REx-ID: 11897
Bharat K, Henzinger M. 2003. Improved algorithms for topic distillation in a hyperlinked environment. 21st annual international ACM SIGIR conference on Research and development in information retrieval. SIGIR: International Conference on Research and Development in Information Retrieval, 104–111.
View | DOI
 
[38]
2003 | Published | Conference Paper | IST-REx-ID: 11909 | OA
Henzinger M, Motwani R, Silverstein C. 2003. Challenges in web search engines. 18th International Joint Conference on Artificial Intelligence. IJCAI: International Joint Conference on Artificial Intelligence, 1573–1579.
[Published Version] View | Download Published Version (ext.)
 
[37]
2001 | Published | Journal Article | IST-REx-ID: 11755
Henzinger M. 2001. Hyperlink analysis for the Web. IEEE Internet Computing. 5(1), 45–50.
View | DOI | WoS
 
[36]
2001 | Published | Journal Article | IST-REx-ID: 11892
Henzinger M, King V. 2001. Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. 31(2), 364–374.
View | DOI
 
[35]
2001 | Published | Conference Paper | IST-REx-ID: 11914
Bharat K, Chang B-W, Henzinger M, Ruhl M. 2001. Who links to whom: Mining linkage between Web sites. 1st IEEE International Conference on Data Mining. ICMD: International Conference on Data Mining, 51–58.
View | DOI
 
[34]
2000 | Published | Journal Article | IST-REx-ID: 11683
Henzinger M, Rao S, Gabow HN. 2000. Computing vertex connectivity: New bounds from old techniques. Journal of Algorithms. 34(2), 222–250.
View | DOI
 
[33]
2000 | Published | Journal Article | IST-REx-ID: 11685
Henzinger M, Heydon A, Mitzenmacher M, Najork M. 2000. On near-uniform URL sampling. Computer Networks. 33(1–6), 295–308.
View | DOI
 
[32]
2000 | Published | Journal Article | IST-REx-ID: 11694
Albers S, Henzinger M. 2000. Exploring unknown environments. SIAM Journal on Computing. 29(4), 1164–1188.
View | DOI
 
[31]
2000 | Published | Journal Article | IST-REx-ID: 11770 | OA
Bharat K, Broder A, Dean J, Henzinger M. 2000. A comparison of techniques to find mirrored hosts on the WWW. Journal of the American Society for Information Science. 51(12), 1114–1122.
[Published Version] View | DOI | Download Published Version (ext.)
 
[30]
2000 | Published | Conference Paper | IST-REx-ID: 11802
Henzinger M. 2000. Web information retrieval - an algorithmic perspective. 8th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 1879, 1–8.
View | DOI
 
[29]
2000 | Published | Journal Article | IST-REx-ID: 11893
Henzinger M. 2000. Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. 29(6), 1761–1815.
View | DOI
 
[28]
1999 | Published | Journal Article | IST-REx-ID: 11679
Henzinger M, King V, Warnow T. 1999. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica. 24, 1–13.
View | Files available | DOI
 
[27]
1999 | Published | Journal Article | IST-REx-ID: 11687
Dean J, Henzinger M. 1999. Finding related pages in the world wide Web. Computer Networks. 31(11–16), 1467–1479.
View | DOI
 
[26]
1999 | Published | Journal Article | IST-REx-ID: 11688
Henzinger M, Heydon A, Mitzenmacher M, Najork M. 1999. Measuring index quality using random walks on the web. Computer Networks. 31(11–16), 1291–1303.
View | DOI
 
[25]
1999 | Published | Conference Paper | IST-REx-ID: 11691
Goel A, Henzinger M, Plotkin S, Tardos E. 1999. Scheduling data transfers in a network and the set scheduling problem. Proceedings of the 31st annual ACM symposium on Theory of computing. STOC: Symposium on Theory of Computing, 189–197.
View | DOI
 
[24]
1999 | Published | Journal Article | IST-REx-ID: 11769
Henzinger M, King V. 1999. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM. 46(4), 502–516.
View | DOI
 
[23]
1999 | Published | Journal Article | IST-REx-ID: 11895 | OA
Silverstein C, Marais H, Henzinger M, Moricz M. 1999. Analysis of a very large web search engine query log. ACM SIGIR Forum. 33(1), 6–12.
[Published Version] View | DOI | Download Published Version (ext.)
 
[22]
1999 | Published | Conference Paper | IST-REx-ID: 11925
Henzinger M, Leonardi  S. 1999. Scheduling multicasts on unit-capacity trees and meshes. 10th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 438–447.
View
 
[21]
1998 | Published | Journal Article | IST-REx-ID: 11680
Alberts D, Henzinger M. 1998. Average-case analysis of dynamic graph algorithms. Algorithmica. 20, 31–60.
View | Files available | DOI
 
[20]
1998 | Published | Journal Article | IST-REx-ID: 11681
Henzinger M, Fredman ML. 1998. Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica. 22(3), 351–362.
View | DOI
 
[19]
1998 | Published | Conference Paper | IST-REx-ID: 11682
Agarwal PK, EppsteinL. J. Guibas D, Henzinger M. 1998. Parametric and kinetic minimum spanning trees. Proceedings of the 39th Annual Symposium on Foundations of Computer Science. Annual IEEE Symposium on Foundations of Computer Science, 596–605.
View | DOI
 
[18]
1998 | Published | Conference Paper | IST-REx-ID: 11926
Goel A, Henzinger M, Plotkin S. 1998. An online throughput-competitive algorithm for multicast routing and admission control. 9th Annual ACM SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 97–106.
View | Files available
 
[17]
1997 | Published | Journal Article | IST-REx-ID: 11666
Anderson JM, Berc LM, Dean J, Ghemawat S, Henzinger M, Leung S-TA, Sites RL, Vandevoorde MT, Waldspurger CA, Weihl WE. 1997. Continuous profiling: Where have all the cycles gone? ACM Transactions on Computer Systems. 15(4), 357–390.
View | DOI
 
[16]
1997 | Published | Journal Article | IST-REx-ID: 11765
Henzinger M. 1997. A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. Journal of Algorithms. 24(1), 194–220.
View | DOI
 
[15]
1997 | Published | Journal Article | IST-REx-ID: 11767 | OA
Henzinger M, Klein P, Rao S, Subramanian S. 1997. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences. 55(1), 3–23.
[Published Version] View | DOI | Download Published Version (ext.)
 
[14]
1997 | Published | Conference Paper | IST-REx-ID: 11803
Henzinger M, King V. 1997. Maintaining minimum spanning trees in dynamic graphs. 24th International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 1256, 594–604.
View | DOI
 
[13]
1997 | Published | Journal Article | IST-REx-ID: 11849 | OA
Anderson JM, Berc LM, Dean J, Ghemawat S, Henzinger M, Leung S-TA, Sites RL, Vandevoorde MT, Waldspurger CA, Weihl WE. 1997. Continuous profiling: Where have all the cycles gone? ACM SIGOPS Operating Systems Review. 31(5), 1–14.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[12]
1997 | Published | Journal Article | IST-REx-ID: 11883
Henzinger M, Thorup M. 1997. Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Random Structures and Algorithms. 11(4), 369–379.
View | DOI
 
[11]
1996 | Published | Journal Article | IST-REx-ID: 11761
Henzinger M, Williamson DP. 1996. On the number of small cuts in a graph. Information Processing Letters. 59(1), 41–44.
View | DOI
 
[10]
1996 | Published | Conference Paper | IST-REx-ID: 11804
Henzinger M, Telle JA. 1996. Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning. 5th Scandinavian Workshop on Algorithm Theory. SWAT: Scandinavian Workshop on Algorithm Theory, LNCS, vol. 1097, 16–27.
View | DOI
 
[9]
1996 | Published | Conference Paper | IST-REx-ID: 11910
Henzinger M, Thorup M. 1996. Improved sampling with applications to dynamic graph algorithms. 23rd International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 1099, 290–299.
View | DOI
 
[8]
1996 | Published | Conference Paper | IST-REx-ID: 11927 | OA
Henzinger M, King V, Warnow T. 1996. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. 7th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 333–340.
[Published Version] View | Files available | Download Published Version (ext.)
 
[7]
1995 | Published | Journal Article | IST-REx-ID: 11677
Henzinger M. 1995. Fully dynamic biconnectivity in graphs. Algorithmica. 13(6), 503–538.
View | DOI
 
[6]
1995 | Published | Conference Paper | IST-REx-ID: 11684
Henzinger M, King V. 1995. Fully dynamic biconnectivity and transitive closure. Proceedings of IEEE 36th Annual Foundations of Computer Science. Foundations of Computer Science, 664–672.
View | DOI
 
[5]
1995 | Published | Conference Paper | IST-REx-ID: 11805
Henzinger M, Poutré H. 1995. Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. 3rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 979, 171–184.
View | DOI
 
[4]
1995 | Published | Conference Paper | IST-REx-ID: 11806
Henzinger M. 1995. Approximating minimum cuts under insertions. 22nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 944, 280–291.
View | DOI
 
[3]
1995 | Published | Conference Paper | IST-REx-ID: 11928 | OA
Alberts D, Henzinger M. 1995. Average case analysis of dynamic graph algorithms. 6th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 312–321.
[Published Version] View | Files available | Download Published Version (ext.)
 
[2]
1995 | Published | Conference Paper | IST-REx-ID: 4498
Henzinger M, Henzinger TA, Kopke P. 1995. Computing simulations on finite and infinite graphs. Proceedings of IEEE 36th Annual Foundations of Computer Science. FOCS: Foundations of Computer Science, 453–462.
View | DOI
 
[1]
1994 | Published | Conference Paper | IST-REx-ID: 11857
Henzinger M. 1994. Fully dynamic cycle-equivalence in graphs. 35th Annual Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science, 744–755.
View | DOI
 
Marked Publication(s)

Search

Filter Publications

Display / Sort

Citation Style: ISTA Annual Report

Export / Embed