Monika Henzinger

Henzinger_Monika Group

199 Publications

Mark all

[199]
2024 | Conference Paper | IST-REx-ID: 15008 | OA
Goranci, Gramoz, Monika H Henzinger, Harald Räcke, Sushant Sachdeva, and A. R. Sricharan. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.” In 15th Innovations in Theoretical Computer Science Conference, Vol. 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ITCS.2024.55.
[Published Version] View | Files available | DOI | arXiv
 
[198]
2024 | Conference Paper | IST-REx-ID: 14769 | OA
Henzinger, Monika H, David Saulpic, and Leonhard Sidl. “Experimental Evaluation of Fully Dynamic K-Means via Coresets.” In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, 220–33. Society for Industrial & Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977929.17.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[197]
2024 | Journal Article | IST-REx-ID: 15121 | OA
Zheng, Da Wei, and Monika H Henzinger. “Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching.” Mathematical Programming. Springer Nature, 2024. https://doi.org/10.1007/s10107-024-02066-3.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[196]
2024 | Conference Paper | IST-REx-ID: 15093 | OA
Cultrera di Montesano, Sebastiano, Herbert Edelsbrunner, Monika H Henzinger, and Lara Ost. “Dynamically Maintaining the Persistent Homology of Time Series.” In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), edited by David P. Woodruff, 243–95. Society for Industrial and Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977912.11.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[195]
2024 | Conference Paper | IST-REx-ID: 15253 | OA
Henzinger, Monika H, Jalaj Upadhyay, and Sarvagya Upadhyay. “A Unifying Framework for Differentially Private Sums under Continual Observation.” In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, 2024:995–1018. Society for Industrial and Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977912.38.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[194]
2023 | Conference Paper | IST-REx-ID: 12760 | OA
Henzinger, Monika H, Stefan Neumann, Harald Räcke, and Stefan Schmid. “Dynamic Maintenance of Monotone Dynamic Programs and Applications.” In 40th International Symposium on Theoretical Aspects of Computer Science, Vol. 254. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.STACS.2023.36.
[Published Version] View | Files available | DOI | arXiv
 
[193]
2023 | Conference Paper | IST-REx-ID: 14085 | OA
Goranci, Gramoz, and Monika H Henzinger. “Efficient Data Structures for Incremental Exact and Approximate Maximum Flow.” In 50th International Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.69.
[Published Version] View | Files available | DOI
 
[192]
2023 | Conference Paper | IST-REx-ID: 14086 | OA
Henzinger, Monika H, Paul Liu, Jan Vondrák, and Da Wei Zheng. “Faster Submodular Maximization for Several Classes of Matroids.” In 50th International Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.74.
[Published Version] View | Files available | DOI | arXiv
 
[191]
2023 | Conference Paper | IST-REx-ID: 14462 | OA
Fichtenberger, Hendrik, Monika H Henzinger, and Jalaj Upadhyay. “Constant Matters: Fine-Grained Error Bound on Differentially Private Continual Observation.” In Proceedings of the 40th International Conference on Machine Learning, 202:10072–92. ML Research Press, 2023.
[Published Version] View | Download Published Version (ext.)
 
[190]
2023 | Journal Article | IST-REx-ID: 14558
Bhattacharya, Sayan, Monika H Henzinger, Danupon Nanongkai, and Xiaowei Wu. “Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/21M1428649.
View | DOI
 
[189]
2023 | Journal Article | IST-REx-ID: 14043 | OA
Henzinger, Monika H, Billy Jin, Richard Peng, and David P. Williamson. “A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems.” Algorithmica. Springer Nature, 2023. https://doi.org/10.1007/s00453-023-01154-8.
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[188]
2023 | Conference Paper | IST-REx-ID: 13236 | OA
Zheng, Da Wei, and Monika H Henzinger. “Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching.” In International Conference on Integer Programming and Combinatorial Optimization, 13904:453–65. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-32726-1_32.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[187]
2022 | Journal Article | IST-REx-ID: 11662
Henzinger, Monika H, and Pan Peng. “Constant-Time Dynamic (Δ +1)-Coloring.” ACM Transactions on Algorithms. Association for Computing Machinery (ACM), 2022. https://doi.org/10.1145/3501403.
View | DOI
 
[186]
2022 | Conference Paper | IST-REx-ID: 11812 | OA
Hanauer, Kathrin, Monika H Henzinger, and Qi Cheng Hua. “Fully Dynamic Four-Vertex Subgraph Counting.” In 1st Symposium on Algorithmic Foundations of Dynamic Networks, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.SAND.2022.18.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[185]
2022 | Conference Paper | IST-REx-ID: 11808 | OA
Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Recent Advances in Fully Dynamic Graph Algorithms.” In 1st Symposium on Algorithmic Foundations of Dynamic Networks, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.SAND.2022.1.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[184]
2022 | Conference Paper | IST-REx-ID: 11918
Henzinger, Monika H, Andrea Lincoln, and Barna Saha. “The Complexity of Average-Case Dynamic Subgraph Counting.” In 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, 459–98. Society for Industrial and Applied Mathematics, 2022. https://doi.org/10.1137/1.9781611977073.23.
View | DOI
 
[183]
2022 | Conference Paper | IST-REx-ID: 11930 | OA
Henzinger, Monika H, Alexander Noe, and Christian Schulz. “Practical Fully Dynamic Minimum Cut Algorithms.” In 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments, 13–26. Society for Industrial and Applied Mathematics, 2022. https://doi.org/10.1137/1.9781611977042.2.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[182]
2022 | Preprint | IST-REx-ID: 14236 | OA
Goranci, Gramoz, and Monika H Henzinger. “Incremental Approximate Maximum Flow in M1/2+o(1) Update Time.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2211.09606.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[181]
2021 | Conference Paper | IST-REx-ID: 10054 | OA
Chatterjee, Krishnendu, Monika H Henzinger, Sagar Sudhir Kale, and Alexander Svozil. “Faster Algorithms for Bounded Liveness in Graphs and Game Graphs.” In 48th International Colloquium on Automata, Languages, and Programming, Vol. 198. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.ICALP.2021.124.
[Published Version] View | Files available | DOI
 
[180]
2021 | Conference Paper | IST-REx-ID: 11649 | OA
Henzinger, Monika H, Ami Paz, and Stefan Schmid. “On the Complexity of Weight-Dynamic Network Algorithms.” In IFIP Networking Conference. Institute of Electrical and Electronics Engineers, 2021. https://doi.org/10.23919/ifipnetworking52078.2021.9472803.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[179]
2021 | Journal Article | IST-REx-ID: 11663 | OA
Bernstein, Aaron, Sebastian Forster, and Monika H Henzinger. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” ACM Transactions on Algorithms. Association for Computing Machinery, 2021. https://doi.org/10.1145/3469833.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[178]
2021 | Journal Article | IST-REx-ID: 11756 | OA
Henzinger, Monika H, and Pan Peng. “Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest.” Information and Computation. Elsevier, 2021. https://doi.org/10.1016/j.ic.2021.104805.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[177]
2021 | Conference Paper | IST-REx-ID: 11771 | OA
Henzinger, Monika H, and Xiaowei Wu. “Upper and Lower Bounds for Fully Retroactive Graph Problems.” In 17th International Symposium on Algorithms and Data Structures, 12808:471–484. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-83508-8_34.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[176]
2021 | Conference Paper | IST-REx-ID: 11814 | OA
Fichtenberger, Hendrik, Monika H Henzinger, and Wolfgang Ost. “Differentially Private Algorithms for Graphs under Continual Observation.” In 29th Annual European Symposium on Algorithms, Vol. 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.ESA.2021.42.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[175]
2021 | Journal Article | IST-REx-ID: 11886 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2021. https://doi.org/10.1137/16m1097808.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[174]
2021 | Conference Paper | IST-REx-ID: 11919 | OA
Bergamaschi, Thiago, Monika H Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. “New Techniques and Fine-Grained Hardness for Dynamic near-Additive Spanners.” In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1836–55. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/1.9781611976465.110.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[173]
2021 | Conference Paper | IST-REx-ID: 11923 | OA
Henzinger, Monika H, Stefan Neumann, Harald Räcke, and Stefan Schmid. “Tight Bounds for Online Graph Partitioning.” In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2799–2818. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/1.9781611976465.166.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[172]
2021 | Conference Paper | IST-REx-ID: 11920 | OA
Bhattacharya, Sayan, Monika H Henzinger, Danupon Nanongkai, and Xiaowei Wu. “Dynamic Set Cover: Improved Amortized and Worst-Case Update Time.” In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2537–49. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/1.9781611976465.150.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[171]
2021 | Conference Paper | IST-REx-ID: 11931 | OA
Goranci, Gramoz, Monika H Henzinger, Dariusz Leniowski, Christian Schulz, and Alexander Svozil. “Fully Dynamic K-Center Clustering in Low Dimensional Metrics.” In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments, 143–53. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/1.9781611976472.11.
[Published Version] View | DOI | Download Published Version (ext.)
 
[170]
2021 | Conference Paper | IST-REx-ID: 10002 | OA
Chatterjee, Krishnendu, Wolfgang Dvorak, Monika H Henzinger, and Alexander Svozil. “Symbolic Time and Space Tradeoffs for Probabilistic Verification.” In Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 1–13. Institute of Electrical and Electronics Engineers, 2021. https://doi.org/10.1109/LICS52264.2021.9470739.
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[169]
2021 | Journal Article | IST-REx-ID: 9293 | OA
Chatterjee, Krishnendu, Wolfgang Dvořák, Monika H Henzinger, and Alexander Svozil. “Algorithms and Conditional Lower Bounds for Planning Problems.” Artificial Intelligence. Elsevier, 2021. https://doi.org/10.1016/j.artint.2021.103499.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | WoS | arXiv
 
[168]
2020 | Journal Article | IST-REx-ID: 11675 | OA
Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika H Henzinger. “Deterministic Dynamic Matching in O(1) Update Time.” Algorithmica. Springer Nature, 2020. https://doi.org/10.1007/s00453-019-00630-4.
[Published Version] View | DOI | Download Published Version (ext.)
 
[167]
2020 | Journal Article | IST-REx-ID: 11674 | OA
Henzinger, Monika H, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering to Minimize the Sum of Radii.” Algorithmica. Springer Nature, 2020. https://doi.org/10.1007/s00453-020-00721-7.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[166]
2020 | Conference Paper | IST-REx-ID: 11818 | OA
Henzinger, Monika H, and Sagar Kale. “Fully-Dynamic Coresets.” In 28th Annual European Symposium on Algorithms, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.ESA.2020.57.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[165]
2020 | Conference Paper | IST-REx-ID: 11816 | OA
Henzinger, Monika H, Khan Shahbaz, Richard Paul, and Christian Schulz. “Dynamic Matching Algorithms in Practice.” In 8th Annual European Symposium on Algorithms, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.ESA.2020.58.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[164]
2020 | Conference Paper | IST-REx-ID: 11824 | OA
Henzinger, Monika H, Stefan Neumann, and Andreas Wiese. “Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.51.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[163]
2020 | Conference Paper | IST-REx-ID: 11822 | OA
Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Faster Fully Dynamic Transitive Closure in Practice.” In 18th International Symposium on Experimental Algorithms, Vol. 160. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SEA.2020.14.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[162]
2020 | Conference Paper | IST-REx-ID: 11825 | OA
Henzinger, Monika H, and Pan Peng. “Constant-Time Dynamic (Δ+1)-Coloring.” In 37th International Symposium on Theoretical Aspects of Computer Science, Vol. 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.STACS.2020.53.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[161]
2020 | Conference Paper | IST-REx-ID: 11819 | OA
Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Finding All Global Minimum Cuts in Practice.” In 28th Annual European Symposium on Algorithms, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.ESA.2020.59.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[160]
2020 | Conference Paper | IST-REx-ID: 11852 | OA
Chen, Li, Gramoz Goranci, Monika H Henzinger, Richard Peng, and Thatchaphol Saranurak. “Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers.” In 61st Annual Symposium on Foundations of Computer Science, 1135–46. Institute of Electrical and Electronics Engineers, 2020. https://doi.org/10.1109/focs46700.2020.00109.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[159]
2020 | Conference Paper | IST-REx-ID: 11880 | OA
Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Fully Dynamic Single-Source Reachability in Practice: An Experimental Study.” In 2020 Symposium on Algorithm Engineering and Experiments, 106–19. Society for Industrial and Applied Mathematics, 2020. https://doi.org/10.1137/1.9781611976007.9.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[158]
2020 | Conference Paper | IST-REx-ID: 11881 | OA
Henzinger, Monika H, Alexander Noe, and Christian Schulz. “Shared-Memory Branch-and-Reduce for Multiterminal Cuts.” In 2020 Symposium on Algorithm Engineering and Experiments, 42–55. Society for Industrial and Applied Mathematics, 2020. https://doi.org/10.1137/1.9781611976007.4.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[157]
2020 | Journal Article | IST-REx-ID: 11889
Henzinger, Monika H, Satish Rao, and Di Wang. “Local Flow Partitioning for Faster Edge Connectivity.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2020. https://doi.org/10.1137/18m1180335.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[156]
2020 | Journal Article | IST-REx-ID: 11894 | OA
Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” SIAM Journal on Discrete Mathematics. Society for Industrial & Applied Mathematics, 2020. https://doi.org/10.1137/17m1163153.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[155]
2019 | Conference Paper | IST-REx-ID: 11826 | OA
Ancona, Bertie, Monika H Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein. “Algorithms and Hardness for Diameter in Dynamic Graphs.” In 46th International Colloquium on Automata, Languages, and Programming, Vol. 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.13.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[154]
2019 | Conference Paper | IST-REx-ID: 11850 | OA
Henzinger, Monika H, Stefan Neumann, and Stefan Schmid. “Efficient Distributed Workload (Re-)Embedding.” In SIGMETRICS’19: International Conference on Measurement and Modeling of Computer Systems, 43–44. Association for Computing Machinery, 2019. https://doi.org/10.1145/3309697.3331503.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[153]
2019 | Book Chapter | IST-REx-ID: 11847
Biedermann, Sonja, Monika H Henzinger, Christian Schulz, and Bernhard Schuster. “Vienna Graph Clustering.” In Protein-Protein Interaction Networks, edited by Stefan Canzar and Francisca Rojas Ringeling, 2074:215–231. MIMB. Springer Nature, 2019. https://doi.org/10.1007/978-1-4939-9873-9_16.
View | DOI | PubMed | Europe PMC
 
[152]
2019 | Conference Paper | IST-REx-ID: 11853 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “A New Deterministic Algorithm for Dynamic Set Cover.” In 60th Annual Symposium on Foundations of Computer Science, 406–23. Institute of Electrical and Electronics Engineers, 2019. https://doi.org/10.1109/focs.2019.00033.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[151]
2019 | Conference Paper | IST-REx-ID: 11851
Henzinger, Monika H, Alexander Noe, and Christian Schulz. “Shared-Memory Exact Minimum Cuts.” In 33rd International Parallel and Distributed Processing Symposium. Institute of Electrical and Electronics Engineers, 2019. https://doi.org/10.1109/ipdps.2019.00013.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[150]
2019 | Conference Paper | IST-REx-ID: 11865 | OA
Daga, Mohit, Monika H Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak. “Distributed Edge Connectivity in Sublinear Time.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 343–354. Association for Computing Machinery, 2019. https://doi.org/10.1145/3313276.3316346.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[149]
2019 | Conference Paper | IST-REx-ID: 11871 | OA
Bernstein, Aaron, Sebastian Forster, and Monika H Henzinger. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” In 30th Annual ACM-SIAM Symposium on Discrete Algorithms, 1899–1918. Society for Industrial and Applied Mathematics, 2019. https://doi.org/10.1137/1.9781611975482.115.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[148]
2019 | Journal Article | IST-REx-ID: 11898 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Stefan Neumann. “New Amortized Cell-Probe Lower Bounds for Dynamic Problems.” Theoretical Computer Science. Elsevier, 2019. https://doi.org/10.1016/j.tcs.2019.01.043.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[147]
2019 | Conference Paper | IST-REx-ID: 6887 | OA
Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Alexander Svozil. “Near-Linear Time Algorithms for Streett Objectives in Graphs and MDPs.” In Leibniz International Proceedings in Informatics, Vol. 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.CONCUR.2019.7.
[Published Version] View | Files available | DOI
 
[146]
2018 | Conference Paper | IST-REx-ID: 10883 | OA
Chatterjee, Krishnendu, Wolfgang Dvořák, Monika H Henzinger, and Alexander Svozil. “Quasipolynomial Set-Based Symbolic Algorithms for Parity Games.” In 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, 57:233–53. EasyChair, 2018. https://doi.org/10.29007/5z5k.
[Published Version] View | Files available | DOI | arXiv
 
[145]
2018 | Journal Article | IST-REx-ID: 11657 | OA
Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Practical Minimum Cut Algorithms.” ACM Journal of Experimental Algorithmics. Association for Computing Machinery, 2018. https://doi.org/10.1145/3274662.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[144]
2018 | Journal Article | IST-REx-ID: 11667 | OA
Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Valuation Compressions in VCG-Based Combinatorial Auctions.” ACM Transactions on Economics and Computation. Association for Computing Machinery, 2018. https://doi.org/10.1145/3232860.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[143]
2018 | Journal Article | IST-REx-ID: 11664 | OA
Goranci, Gramoz, Monika H Henzinger, and Mikkel Thorup. “Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time.” ACM Transactions on Algorithms. Association for Computing Machinery, 2018. https://doi.org/10.1145/3174803.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[142]
2018 | Journal Article | IST-REx-ID: 11757 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe Italiano. “Dynamic Algorithms via the Primal-Dual Method.” Information and Computation. Elsevier, 2018. https://doi.org/10.1016/j.ic.2018.02.005.
[Published Version] View | DOI | Download Published Version (ext.)
 
[141]
2018 | Conference Paper | IST-REx-ID: 11828 | OA
Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.” In 26th Annual European Symposium on Algorithms, Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.ESA.2018.40.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[140]
2018 | Conference Paper | IST-REx-ID: 11827 | OA
Goranci, Gramoz , Monika H Henzinger, and Dariusz Leniowski. “A Tree Structure for Dynamic Facility Location.” In 26th Annual European Symposium on Algorithms, Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.ESA.2018.39.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[139]
2018 | Journal Article | IST-REx-ID: 11768 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” Journal of the ACM. Association for Computing Machinery, 2018. https://doi.org/10.1145/3218657.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[138]
2018 | Conference Paper | IST-REx-ID: 11872 | OA
Bhattacharya, Sayan, Deeparnab Chakrabarty, Monika H Henzinger, and Danupon Nanongkai. “Dynamic Algorithms for Graph Coloring.” In 29th Annual ACM-SIAM Symposium on Discrete Algorithms, 1–20. Society for Industrial and Applied Mathematics, 2018. https://doi.org/10.1137/1.9781611975031.1.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[137]
2018 | Conference Paper | IST-REx-ID: 11882 | OA
Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Practical Minimum Cut Algorithms.” In 20th Workshop on Algorithm Engineering and Experiments, 48–61. Society for Industrial and Applied Mathematics, 2018. https://doi.org/10.1137/1.9781611975055.5.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[136]
2018 | Journal Article | IST-REx-ID: 11890 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2018. https://doi.org/10.1137/140998925.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[135]
2018 | Conference Paper | IST-REx-ID: 11911 | OA
Biedermann, Sonja, Monika H Henzinger, Christian Schulz, and Bernhard Schuster. “Memetic Graph Clustering.” In 17th International Symposium on Experimental Algorithms, Vol. 103. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.SEA.2018.3.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[134]
2018 | Conference Paper | IST-REx-ID: 310 | OA
Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Veronika Loitzenbauer. “Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter,” 2341–56. ACM, 2018. https://doi.org/10.1137/1.9781611975031.151.
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[133]
2018 | Conference Paper | IST-REx-ID: 141 | OA
Chatterjee, Krishnendu, Monika H Henzinger, Veronika Loitzenbauer, Simin Oraee, and Viktor Toman. “Symbolic Algorithms for Graphs and Markov Decision Processes with Fairness Objectives,” 10982:178–97. Springer, 2018. https://doi.org/10.1007/978-3-319-96142-2_13.
[Published Version] View | Files available | DOI | WoS
 
[132]
2018 | Conference Paper | IST-REx-ID: 35 | OA
Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Alexander Svozil. “Algorithms and Conditional Lower Bounds for Planning Problems.” In 28th International Conference on Automated Planning and Scheduling . AAAI Press, 2018.
View | Files available | Download None (ext.) | WoS | arXiv
 
[131]
2017 | Conference Paper | IST-REx-ID: 11651 | OA
Wang, Di, Kimon Fountoulakis, Monika H Henzinger, Michael W. Mahoney, and Satish Rao . “Capacity Releasing Diffusion for Speed and Locality.” In Proceedings of the 34th International Conference on Machine Learning, 70:3598–3607. ML Research Press, 2017.
[Published Version] View | Download Published Version (ext.) | arXiv
 
[130]
2017 | Journal Article | IST-REx-ID: 11665 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.” ACM Transactions on Algorithms. Association for Computing Machinery, 2017. https://doi.org/10.1145/3146550.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[129]
2017 | Journal Article | IST-REx-ID: 11676 | OA
Dvořák, Wolfgang, Monika H Henzinger, and David P. Williamson. “Maximizing a Submodular Function with Viability Constraints.” Algorithmica. Springer Nature, 2017. https://doi.org/10.1007/s00453-015-0066-y.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[128]
2017 | Conference Paper | IST-REx-ID: 11772
Henzinger, Monika H. “The State of the Art in Dynamic Graph Algorithms.” In 44th International Conference on Current Trends in Theory and Practice of Computer Science, 10706:40–44. Springer Nature, 2017. https://doi.org/10.1007/978-3-319-73117-9_3.
View | DOI
 
[127]
2017 | Conference Paper | IST-REx-ID: 11829 | OA
Henzinger, Monika H, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. “Conditional Hardness for Sensitivity Problems.” In 8th Innovations in Theoretical Computer Science Conference, Vol. 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ITCS.2017.26.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[126]
2017 | Conference Paper | IST-REx-ID: 11833 | OA
Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.” In 25th Annual European Symposium on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.45.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[125]
2017 | Conference Paper | IST-REx-ID: 11832 | OA
Henzinger, Monika H, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering to Minimize the Sum of Radii.” In 25th Annual European Symposium on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.48.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[124]
2017 | Conference Paper | IST-REx-ID: 11874 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in o(Log3 n) Worst Case Update Time.” In 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 0:470–89. Society for Industrial and Applied Mathematics, 2017. https://doi.org/10.1137/1.9781611974782.30.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[123]
2017 | Conference Paper | IST-REx-ID: 11873 | OA
Henzinger, Monika H, Satish Rao, and Di Wang. “Local Flow Partitioning for Faster Edge Connectivity.” In 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 1919–38. Society for Industrial and Applied Mathematics, 2017. https://doi.org/10.1137/1.9781611974782.125.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[122]
2017 | Conference Paper | IST-REx-ID: 11831 | OA
Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” In 25th Annual European Symposium on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.44.
[Published Version] View | Files available | DOI | Download Published Version (ext.) | arXiv
 
[121]
2017 | Journal Article | IST-REx-ID: 11903 | OA
Bhattacharya, Sayan, Wolfgang Dvořák, Monika H Henzinger, and Martin Starnberger. “Welfare Maximization with Friends-of-Friends Network Externalities.” Theory of Computing Systems. Springer Nature, 2017. https://doi.org/10.1007/s00224-017-9759-8.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[120]
2017 | Conference Paper | IST-REx-ID: 12571 | OA
Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika H Henzinger. “Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time.” In 19th International Conference on Integer Programming and Combinatorial Optimization, 10328:86–98. Springer Nature, 2017. https://doi.org/10.1007/978-3-319-59250-3_8.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[119]
2017 | Journal Article | IST-REx-ID: 464 | OA
Chatterjee, Krishnendu, Monika H Henzinger, and Veronika Loitzenbauer. “Improved Algorithms for Parity and Streett Objectives.” Logical Methods in Computer Science. International Federation of Computational Logic, 2017. https://doi.org/10.23638/LMCS-13(3:26)2017.
[Published Version] View | Files available | DOI | arXiv
 
[118]
2017 | Conference Paper | IST-REx-ID: 552 | OA
Chatterjee, Krishnendu, Monika H Henzinger, and Alexander Svozil. “Faster Algorithms for Mean-Payoff Parity Games.” In Leibniz International Proceedings in Informatics, Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.MFCS.2017.39.
[Published Version] View | Files available | DOI
 
[117]
2017 | Conference Paper | IST-REx-ID: 6519 | OA
Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Veronika Loitzenbauer. “Improved Set-Based Symbolic Algorithms for Parity Games,” Vol. 82. Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, 2017. https://doi.org/10.4230/LIPICS.CSL.2017.18.
[Published Version] View | Files available | DOI
 
[116]
2016 | Conference Paper | IST-REx-ID: 1068 | OA
Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Veronika Loitzenbauer. “Conditionally Optimal Algorithms for Generalized Büchi Games,” Vol. 58. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPIcs.MFCS.2016.25.
[Published Version] View | Files available | DOI
 
[115]
2016 | Conference Paper | IST-REx-ID: 1140 | OA
Chatterjee, Krishnendu, Wolfgang Dvoák, Monika H Henzinger, and Veronika Loitzenbauer. “Model and Objective Separation with Conditional Lower Bounds: Disjunction Is Harder than Conjunction.” In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 197–206. IEEE, 2016. https://doi.org/10.1145/2933575.2935304.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[114]
2016 | Conference Paper | IST-REx-ID: 11836 | OA
Cheung, Yun Kuen, Gramoz Goranci, and Monika H Henzinger. “Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds.” In 43rd International Colloquium on Automata, Languages, and Programming, Vol. 55. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPICS.ICALP.2016.131.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[113]
2016 | Conference Paper | IST-REx-ID: 11834 | OA
Goranci, Gramoz, Monika H Henzinger, and Mikkel Thorup. “Incremental Exact Min-Cut in Poly-Logarithmic Amortized Update Time.” In 24th Annual European Symposium on Algorithms, Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPICS.ESA.2016.46.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[112]
2016 | Conference Paper | IST-REx-ID: 11835 | OA
Henzinger, Monika H, and Stefan Neumann. “Incremental and Fully Dynamic Subgraph Connectivity for Emergency Planning.” In 24th Annual European Symposium on Algorithms, Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPICS.ESA.2016.48.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[111]
2016 | Conference Paper | IST-REx-ID: 11866 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” In 48th Annual ACM SIGACT Symposium on Theory of Computing, 489–98. Association for Computing Machinery, 2016. https://doi.org/10.1145/2897518.2897638.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[110]
2016 | Conference Paper | IST-REx-ID: 11867 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “New Deterministic Approximation Algorithms for Fully Dynamic Matching.” In 48th Annual ACM SIGACT Symposium on Theory of Computing, 398–411. Association for Computing Machinery, 2016. https://doi.org/10.1145/2897518.2897568.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[109]
2016 | Journal Article | IST-REx-ID: 11891 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2016. https://doi.org/10.1137/140957299.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[108]
2015 | Journal Article | IST-REx-ID: 11668 | OA
Colini-Baldeschi, Riccardo, Stefano Leonardi, Monika H Henzinger, and Martin Starnberger. “On Multiple Keyword Sponsored Search Auctions with Budgets.” ACM Transactions on Economics and Computation. Association for Computing Machinery, 2015. https://doi.org/10.1145/2818357.
[Submitted Version] View | DOI | Download Submitted Version (ext.)
 
[107]
2015 | Journal Article | IST-REx-ID: 11669 | OA
Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Auctions for Heterogeneous Items and Budget Limits.” ACM Transactions on Economics and Computation. Association for Computing Machinery, 2015. https://doi.org/10.1145/2818351.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[106]
2015 | Journal Article | IST-REx-ID: 11670
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “An Expressive Mechanism for Auctions on the Web.” ACM Transactions on Economics and Computation. Association for Computing Machinery, 2015. https://doi.org/10.1145/2716312.
View | DOI
 
[105]
2015 | Conference Paper | IST-REx-ID: 11774 | OA
Cheung, Yun Kuen, Monika H Henzinger, Martin Hoefer, and Martin Starnberger. “Combinatorial Auctions with Conflict-Based Externalities.” In 11th International Conference on Web and Internet Economics, 9470:230–243. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-48995-6_17.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[104]
2015 | Conference Paper | IST-REx-ID: 11773 | OA
Ben-Zwi, Oren, Monika H Henzinger, and Veronika Loitzenbauer. “Ad Exchange: Envy-Free Auctions with Mediators.” In 11th International Conference on Web and Internet Economics, 9470:104–117. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-48995-6_8.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[103]
2015 | Conference Paper | IST-REx-ID: 11785 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.” In 42nd International Colloquium on Automata, Languages and Programming, 9134:725–36. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_59.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[102]
2015 | Conference Paper | IST-REx-ID: 11787 | OA
Henzinger, Monika H, Sebastian Krinninger, and Veronika Loitzenbauer. “Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.” In 2nd International Colloquium on Automata, Languages and Programming, 9134:713–24. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_58.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[101]
2015 | Conference Paper | IST-REx-ID: 11788 | OA
Dvořák, Wolfgang, and Monika H Henzinger. “Online Ad Assignment with an Ad Exchange.” In 12th International Workshop of Approximation and Online Algorithms, 8952:156–167. Springer Nature, 2015. https://doi.org/10.1007/978-3-319-18263-6_14.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[100]
2015 | Conference Paper | IST-REx-ID: 11786 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Design of Dynamic Algorithms via Primal-Dual Method.” In 42nd International Colloquium on Automata, Languages and Programming, 9134:206–18. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_17.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[99]
2015 | Journal Article | IST-REx-ID: 11845 | OA
Chernomor, Olga, Bui Quang Minh, Félix Forest, Steffen Klaere, Travis Ingram, Monika H Henzinger, and Arndt von Haeseler. “Split Diversity in Constrained Conservation Prioritization Using Integer Linear Programming.” Methods in Ecology and Evolution. Wiley, 2015. https://doi.org/10.1111/2041-210x.12299.
[Published Version] View | Files available | DOI | PubMed | Europe PMC
 
[98]
2015 | Conference Paper | IST-REx-ID: 11868 | OA
Henzinger, Monika H, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. “Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.” In 47th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 2015. https://doi.org/10.1145/2746539.2746609.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[97]
2015 | Conference Paper | IST-REx-ID: 11869 | OA
Bhattacharya, Sayan, Monika H Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. “Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.” In 47th Annual ACM Symposium on Theory of Computing, 173–82. Association for Computing Machinery, 2015. https://doi.org/10.1145/2746539.2746592.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[96]
2015 | Conference Paper | IST-REx-ID: 11837 | OA
Bhattacharya, Sayan, Wolfgang Dvorák, Monika H Henzinger, and Martin Starnberger. “Welfare Maximization with Friends-of-Friends Network Externalities.” In 32nd International Symposium on Theoretical Aspects of Computer Science, 30:90–102. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. https://doi.org/10.4230/LIPICS.STACS.2015.90.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[95]
2015 | Journal Article | IST-REx-ID: 11901 | OA
Henzinger, Monika H, and Veronika Loitzenbauer. “Truthful Unit-Demand Auctions with Budgets Revisited.” Theoretical Computer Science. Elsevier, 2015. https://doi.org/10.1016/j.tcs.2015.01.033.
View | DOI | Download None (ext.)
 
[94]
2015 | Conference Paper | IST-REx-ID: 1661 | OA
Chatterjee, Krishnendu, Monika H Henzinger, and Veronika Loitzenbauer. “Improved Algorithms for One-Pair and k-Pair Streett Objectives.” In Proceedings - Symposium on Logic in Computer Science, Vol. 2015–July. IEEE, 2015. https://doi.org/10.1109/LICS.2015.34.
[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.)
 
[93]
2014 | Conference Paper | IST-REx-ID: 11789 | OA
Charikar, Moses, Monika H Henzinger, and Huy L. Nguyễn. “Online Bipartite Matching with Decomposable Weights.” In 22nd Annual European Symposium on Algorithms, 8737:260–71. Springer Nature, 2014. https://doi.org/10.1007/978-3-662-44777-2_22.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[92]
2014 | Conference Paper | IST-REx-ID: 11790
Cigler, Luděk, Wolfgang Dvořák, Monika H Henzinger, and Martin Starnberger. “Limiting Price Discrimination When Selling Products with Positive Network Externalities.” In 10th International Conference of Web and Internet Economics, 8877:44–57. Springer Nature, 2014. https://doi.org/10.1007/978-3-319-13129-0_4.
View | DOI
 
[91]
2014 | Conference Paper | IST-REx-ID: 11855 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” In 55th Annual Symposium on Foundations of Computer Science, 146–55. Institute of Electrical and Electronics Engineers, 2014. https://doi.org/10.1109/focs.2014.24.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[90]
2014 | Conference Paper | IST-REx-ID: 11870 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs.” In 46th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 2014. https://doi.org/10.1145/2591796.2591869.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[89]
2014 | Conference Paper | IST-REx-ID: 11876 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths.” In 25th Annual ACM-SIAM Symposium on Discrete Algorithms, 1053–72. Society for Industrial and Applied Mathematics, 2014. https://doi.org/10.1137/1.9781611973402.79.
[Published Version] View | DOI | Download Published Version (ext.)
 
[88]
2014 | Conference Paper | IST-REx-ID: 11875 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” In 26th Annual ACM-SIAM Symposium on Discrete Algorithms, 785–804. Society for Industrial and Applied Mathematics, 2014. https://doi.org/10.1137/1.9781611973730.54.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[87]
2014 | Journal Article | IST-REx-ID: 1375 | OA
Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, Veronika Loitzenbauer, and Michael Raskin. “Approximating the Minimum Cycle Mean.” Theoretical Computer Science. Elsevier, 2014. https://doi.org/10.1016/j.tcs.2014.06.031.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[86]
2014 | Journal Article | IST-REx-ID: 2141 | OA
Chatterjee, Krishnendu, and Monika H Henzinger. “Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition.” Journal of the ACM. ACM, 2014. https://doi.org/10.1145/2597631.
[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.)
 
[85]
2014 | Journal Article | IST-REx-ID: 535 | OA
Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” Algorithmica. Springer, 2014. https://doi.org/10.1007/s00453-013-9843-7.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[84]
2013 | Journal Article | IST-REx-ID: 11671
Baykan, Eda, Ingmar Weber, and Monika H Henzinger. “A Comprehensive Study of Techniques for URL-Based Web Page Language Classification.” ACM Transactions on the Web. Association for Computing Machinery, 2013. https://doi.org/10.1145/2435215.2435218.
View | DOI
 
[83]
2013 | Journal Article | IST-REx-ID: 11759 | OA
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Sponsored Search, Market Equilibria, and the Hungarian Method.” Information Processing Letters. Elsevier, 2013. https://doi.org/10.1016/j.ipl.2012.11.006.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[82]
2013 | Conference Paper | IST-REx-ID: 11793 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks.” In 40th International Colloquium on Automata, Languages, and Programming, 7966:607–619. Springer Nature, 2013. https://doi.org/10.1007/978-3-642-39212-2_53.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[81]
2013 | Conference Paper | IST-REx-ID: 11791 | OA
Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Valuation Compressions in VCG-Based Combinatorial Auctions.” In 9th International Conference on Web and Internet Economics, 8289:146–159. Springer Nature, 2013. https://doi.org/10.1007/978-3-642-45046-4_13.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[80]
2013 | Conference Paper | IST-REx-ID: 11792 | OA
Dvořák, Wolfgang, Monika H Henzinger, and David P. Williamson. “Maximizing a Submodular Function with Viability Constraints.” In 21st Annual European Symposium on Algorithms, 8125:409–20. Springer Nature, 2013. https://doi.org/10.1007/978-3-642-40450-4_35.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[79]
2013 | Conference Paper | IST-REx-ID: 11856 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.” In 54th Annual Symposium on Foundations of Computer Science, 538–47. Institute of Electrical and Electronics Engineers, 2013. https://doi.org/10.1109/focs.2013.64.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[78]
2013 | Journal Article | IST-REx-ID: 11902
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Bidder Optimal Assignments for General Utilities.” Theoretical Computer Science. Elsevier, 2013. https://doi.org/10.1016/j.tcs.2013.01.030.
View | Files available | DOI
 
[77]
2013 | Journal Article | IST-REx-ID: 11758
Aceto, Luca, Monika H Henzinger, and Jiří Sgall. “38th International Colloquium on Automata, Languages and Programming.” Information and Computation. Elsevier, 2013. https://doi.org/10.1016/j.ic.2012.11.002.
View | DOI
 
[76]
2013 | Journal Article | IST-REx-ID: 2831 | OA
Chatterjee, Krishnendu, Monika H Henzinger, Manas Joglekar, and Nisarg Shah. “Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives.” Formal Methods in System Design. Springer, 2013. https://doi.org/10.1007/s10703-012-0180-2.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[75]
2012 | Conference Paper | IST-REx-ID: 11656
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Maximizing Revenue from Strategic Recommendations under Decaying Trust.” In Proceedings of the 21st ACM International Conference on Information and Knowledge Management, 2268–86. Association for Computing Machinery, 2012. https://doi.org/10.1145/2396761.2398621.
View | DOI
 
[74]
2012 | Conference Paper | IST-REx-ID: 11794 | OA
Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Auctions with Heterogeneous Items and Budget Limits.” In 8th International Workshop on Internet and Network Economics, 7695:44–57. Springer Nature, 2012. https://doi.org/10.1007/978-3-642-35311-6_4.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[73]
2012 | Conference Paper | IST-REx-ID: 11795
Colini-Baldeschi, Riccardo, Monika H Henzinger, Stefano Leonardi, and Martin Starnberger. “On Multiple Keyword Sponsored Search Auctions with Budgets.” In 39th International Colloquium on Automata, Languages, and Programming, 7392:1–12. Springer Nature, 2012. https://doi.org/10.1007/978-3-642-31585-5_1.
View | Files available | DOI
 
[72]
2012 | Conference Paper | IST-REx-ID: 3165 | OA
Chatterjee, Krishnendu, and Monika H Henzinger. “An O(N2) Time Algorithm for Alternating Büchi Games.” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 1386–99. SIAM, 2012. https://doi.org/10.1137/1.9781611973099.109.
View | Files available | DOI | Download None (ext.) | arXiv
 
[71]
2012 | Conference Paper | IST-REx-ID: 10905 | OA
Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” In Algorithms – ESA 2012, 7501:301–12. Springer, 2012. https://doi.org/10.1007/978-3-642-33090-2_27.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[70]
2011 | Journal Article | IST-REx-ID: 11673
Baykan, Eda, Monika H Henzinger, Ludmila Marian, and Ingmar Weber. “A Comprehensive Study of Features and Algorithms for URL-Based Topic Classification.” ACM Transactions on the Web. Association for Computing Machinery, 2011. https://doi.org/10.1145/1993053.1993057.
View | DOI
 
[69]
2011 | Journal Article | IST-REx-ID: 11760
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Offline File Assignments for Online Load Balancing.” Information Processing Letters. Elsevier, 2011. https://doi.org/10.1016/j.ipl.2010.11.022.
View | DOI
 
[68]
2011 | Conference Paper | IST-REx-ID: 11796
Henzinger, Monika H, and Angelina Vidali. “Multi-Parameter Mechanism Design under Budget and Matroid Constraints.” In 19th Annual European Symposium on Algorithms, 6942:192–202. Springer Nature, 2011. https://doi.org/10.1007/978-3-642-23719-5_17.
View | DOI
 
[67]
2011 | Conference Paper | IST-REx-ID: 11864
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “An Expressive Mechanism for Auctions on the Web.” In Proceedings of the 20th International Conference on World Wide Web, 127–36. Association for Computing Machinery, 2011. https://doi.org/10.1145/1963405.1963427.
View | DOI
 
[66]
2011 | Conference Paper | IST-REx-ID: 3342 | OA
Chatterjee, Krishnendu, Monika H Henzinger, Manas Joglekar, and Shah Nisarg. “Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives.” edited by Ganesh Gopalakrishnan and Shaz Qadeer, 6806:260–76. Springer, 2011. https://doi.org/10.1007/978-3-642-22110-1_21.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[65]
2011 | Conference Paper | IST-REx-ID: 3343 | OA
Chatterjee, Krishnendu, and Monika H Henzinger. “Faster and Dynamic Algorithms for Maximal End-Component Decomposition and Related Graph Problems in Probabilistic Verification,” 1318–36. SIAM, 2011. https://doi.org/10.1137/1.9781611973082.101.
[Submitted Version] View | DOI | Download Submitted Version (ext.)
 
[64]
2011 | Technical Report | IST-REx-ID: 5379 | OA
Chatterjee, Krishnendu, and Monika H Henzinger. An O(N2) Time Algorithm for Alternating Büchi Games. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0009.
[Published Version] View | Files available | DOI
 
[63]
2010 | Conference Paper | IST-REx-ID: 11797 | OA
Feldman, Jon, Monika H Henzinger, Nitish Korula, Vahab S. Mirrokni, and Cliff Stein. “Online Stochastic Packing Applied to Display Ad Allocation.” In 18th Annual European Symposium on Algorithms, 6346:182–194. Springer Nature, 2010. https://doi.org/10.1007/978-3-642-15775-2_16.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[62]
2010 | Conference Paper | IST-REx-ID: 11798
Dütting, Paul, and Monika H Henzinger. “Mechanisms for the Marriage and the Assignment Game.” In 7th International Conference on Algorithms and Complexity, 6078:6–12. Springer Nature, 2010. https://doi.org/10.1007/978-3-642-13073-1_2.
View | DOI
 
[61]
2010 | Conference Paper | IST-REx-ID: 11838 | OA
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Sponsored Search, Market Equilibria, and the Hungarian Method.” In 27th International Symposium on Theoretical Aspects of Computer Science, 5:287–98. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. https://doi.org/10.4230/LIPICS.STACS.2010.2463.
[Published Version] View | Files available | DOI | Download Published Version (ext.) | arXiv
 
[60]
2010 | Conference Paper | IST-REx-ID: 11863
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “How Much Is Your Personal Recommendation Worth?” In Proceedings of the 19th International Conference on World Wide Web , 1085–86. Association for Computing Machinery, 2010. https://doi.org/10.1145/1772690.1772816.
View | DOI
 
[59]
2010 | Journal Article | IST-REx-ID: 11885
Henzinger, Monika H, Jacob Suñol, and Ingmar Weber. “The Stability of the H-Index.” Scientometrics. Springer Nature, 2010. https://doi.org/10.1007/s11192-009-0098-7.
View | DOI
 
[58]
2009 | Conference Paper | IST-REx-ID: 11799
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Bidder Optimal Assignments for General Utilities.” In 5th International Workshop on Internet and Network Economics, 5929:575–82. Springer Nature, 2009. https://doi.org/10.1007/978-3-642-10841-9_58.
View | Files available | DOI
 
[57]
2009 | Conference Paper | IST-REx-ID: 11912 | OA
Baykan, Eda, Monika H Henzinger, Stefan F. Keller, Sebastian de Castelberg, and Markus Kinzler. “A Comparison of Techniques for Sampling Web Pages.” In 26th International Symposium on Theoretical Aspects of Computer Science, 3:13–30. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009. https://doi.org/10.4230/LIPICS.STACS.2009.1809.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[56]
2009 | Conference Paper | IST-REx-ID: 11905
Baykan, Eda, Monika H Henzinger, Ludmila Marian, and Ingmar Weber. “Purely URL-Based Topic Classification.” In 18th International World Wide Web Conference, 1109–10. Association for Computing Machinery, 2009. https://doi.org/10.1145/1526709.1526880.
View | DOI
 
[55]
2009 | Conference Paper | IST-REx-ID: 11906
Abdel Hamid, Ossama, Behshad Behzadi, Stefan Christoph, and Monika H Henzinger. “Detecting the Origin of Text Segments Efficiently.” In 18th International World Wide Web Conference, 61–70. Association for Computing Machinery, 2009. https://doi.org/10.1145/1526709.1526719.
View | DOI
 
[54]
2008 | Journal Article | IST-REx-ID: 11878
Baykan, Eda, Monika H Henzinger, and Ingmar Weber. “Web Page Language Identification Based on URLs.” Proceedings of the VLDB Endowment. Association for Computing Machinery, 2008. https://doi.org/10.14778/1453856.1453880.
View | DOI
 
[53]
2007 | Journal Article | IST-REx-ID: 11884
Henzinger, Monika H. “Search Technologies for the Internet.” Science. American Association for the Advancement of Science, 2007. https://doi.org/10.1126/science.1126557.
View | DOI | PubMed | Europe PMC
 
[52]
2007 | Conference Paper | IST-REx-ID: 11924
Henzinger, Monika H. “Combinatorial Algorithms for Web Search Engines: Three Success Stories.” In 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 1022–26. Society for Industrial & Applied Mathematics, 2007.
View
 
[51]
2006 | Conference Paper | IST-REx-ID: 11929
Henzinger, Monika H. “Finding Near-Duplicate Web Pages: A Large-Scale Evaluation of Algorithms.” In 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 284–91. Association for Computing Machinery, 2006. https://doi.org/10.1145/1148170.1148222.
View | DOI
 
[50]
2005 | Conference Paper | IST-REx-ID: 11698
Henzinger, Monika H. “Hyperlink Analysis on the World Wide Web.” In Proceedings of the 16th ACM Conference on Hypertext and Hypermedia, 1–3. Association for Computing Machinery, 2005. https://doi.org/10.1145/1083356.1083357.
View | DOI
 
[49]
2005 | Journal Article | IST-REx-ID: 11904
Henzinger, Monika H, Bay-Wei Chang, Brian Milch, and Sergey Brin. “Query-Free News Search.” World Wide Web. Springer Nature, 2005. https://doi.org/10.1007/s11280-004-4870-6.
View | Files available | DOI
 
[48]
2005 | Journal Article | IST-REx-ID: 11763 | OA
Goel, Ashish, Monika H Henzinger, and Serge Plotkin. “An Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control.” Journal of Algorithms. Elsevier, 2005. https://doi.org/10.1016/j.jalgor.2004.11.001.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[47]
2004 | Journal Article | IST-REx-ID: 11762 | OA
Henzinger, Monika H. “Algorithmic Challenges in Web Search Engines.” Internet Mathematics. Internet Mathematics, 2004. https://doi.org/10.1080/15427951.2004.10129079.
[Published Version] View | DOI | Download Published Version (ext.)
 
[46]
2004 | Conference Paper | IST-REx-ID: 11801
Henzinger, Monika H. “Algorithmic Aspects of Web Search Engines.” In 2th Annual European Symposium on Algorithms, 3221:3. Springer Nature, 2004. https://doi.org/10.1007/978-3-540-30140-0_2.
View | DOI
 
[45]
2004 | Conference Paper | IST-REx-ID: 11800
Henzinger, Monika H. “The Past, Present, and Future of Web Search Engines.” In 31st International Colloquium on Automata, Languages and Programming, 3142:3. Springer Nature, 2004. https://doi.org/10.1007/978-3-540-27836-8_2.
View | DOI
 
[44]
2004 | Conference Paper | IST-REx-ID: 11859
Henzinger, Monika H. “The Past, Present, and Future of Web Information Retrieval.” In SPIE Proceedings, 5296:23–26. Society of Photo-Optical Instrumentation Engineers, 2004. https://doi.org/10.1117/12.537534.
View | DOI
 
[43]
2004 | Journal Article | IST-REx-ID: 11877 | OA
Henzinger, Monika H, and Steve Lawrence. “Extracting Knowledge from the World Wide Web.” Proceedings of the National Academy of Sciences. Proceedings of the National Academy of Sciences, 2004. https://doi.org/10.1073/pnas.0307528100.
[Published Version] View | DOI | Download Published Version (ext.) | PubMed | Europe PMC
 
[42]
2003 | Journal Article | IST-REx-ID: 11766 | OA
Henzinger, Monika H, and Stefano Leonardi. “Scheduling Multicasts on Unit-Capacity Trees and Meshes.” Journal of Computer and System Sciences. Elsevier, 2003. https://doi.org/10.1016/s0022-0000(03)00043-6.
[Published Version] View | DOI | Download Published Version (ext.)
 
[41]
2003 | Journal Article | IST-REx-ID: 11764
Goel, Ashish, Monika H Henzinger, Serge Plotkin, and Eva Tardos. “Scheduling Data Transfers in a Network and the Set Scheduling Problem.” Journal of Algorithms. Elsevier, 2003. https://doi.org/10.1016/s0196-6774(03)00054-3.
View | DOI
 
[40]
2003 | Conference Paper | IST-REx-ID: 11897
Bharat, Krishna, and Monika H Henzinger. “Improved Algorithms for Topic Distillation in a Hyperlinked Environment.” In 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 104–111. Association for Computing Machinery, 2003. https://doi.org/10.1145/290941.290972.
View | DOI
 
[39]
2003 | Conference Paper | IST-REx-ID: 11860
Henzinger, Monika H, Bay-Wei Chang, Brian Milch, and Sergey Brin. “Query-Free News Search.” In Proceedings of the 12th International Conference on World Wide Web. Association for Computing Machinery, 2003. https://doi.org/10.1145/775152.775154.
View | Files available | DOI
 
[38]
2003 | Conference Paper | IST-REx-ID: 11909 | OA
Henzinger, Monika H, Rajeev Motwani, and Craig Silverstein. “Challenges in Web Search Engines.” In 18th International Joint Conference on Artificial Intelligence, 1573–79. Association for Computing Machinery, 2003.
[Published Version] View | Download Published Version (ext.)
 
[37]
2001 | Journal Article | IST-REx-ID: 11892
Henzinger, Monika H, and Valerie King. “Maintaining Minimum Spanning Forests in Dynamic Graphs.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2001. https://doi.org/10.1137/s0097539797327209.
View | DOI
 
[36]
2001 | Conference Paper | IST-REx-ID: 11914
Bharat, K., Bay-Wei Chang, Monika H Henzinger, and M. Ruhl. “Who Links to Whom: Mining Linkage between Web Sites.” In 1st IEEE International Conference on Data Mining, 51–58. Institute of Electrical and Electronics Engineers, 2001. https://doi.org/10.1109/ICDM.2001.989500.
View | DOI
 
[35]
2001 | Journal Article | IST-REx-ID: 11755
Henzinger, Monika H. “Hyperlink Analysis for the Web.” IEEE Internet Computing. Institute of Electrical and Electronics Engineers, 2001. https://doi.org/10.1109/4236.895141.
View | DOI | WoS
 
[34]
2000 | Journal Article | IST-REx-ID: 11683
Henzinger, Monika H, Satish Rao, and Harold N. Gabow. “Computing Vertex Connectivity: New Bounds from Old Techniques.” Journal of Algorithms. Elsevier, 2000. https://doi.org/10.1006/jagm.1999.1055.
View | DOI
 
[33]
2000 | Journal Article | IST-REx-ID: 11685
Henzinger, Monika H, Allan Heydon, Michael Mitzenmacher, and Marc Najork. “On Near-Uniform URL Sampling.” Computer Networks. Elsevier, 2000. https://doi.org/10.1016/s1389-1286(00)00055-4.
View | DOI
 
[32]
2000 | Journal Article | IST-REx-ID: 11694
Albers, Susanne, and Monika H Henzinger. “Exploring Unknown Environments.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2000. https://doi.org/10.1137/s009753979732428x.
View | DOI
 
[31]
2000 | Journal Article | IST-REx-ID: 11770 | OA
Bharat, Krishna, Andrei Broder, Jeffrey Dean, and Monika H Henzinger. “A Comparison of Techniques to Find Mirrored Hosts on the WWW.” Journal of the American Society for Information Science. Wiley, 2000. https://doi.org/10.1002/1097-4571(2000)9999:9999<::aid-asi1025>3.0.co;2-0.
[Published Version] View | DOI | Download Published Version (ext.)
 
[30]
2000 | Conference Paper | IST-REx-ID: 11802
Henzinger, Monika H. “Web Information Retrieval - an Algorithmic Perspective.” In 8th Annual European Symposium on Algorithms, 1879:1–8. Springer Nature, 2000. https://doi.org/10.1007/3-540-45253-2_1.
View | DOI
 
[29]
2000 | Journal Article | IST-REx-ID: 11893
Henzinger, Monika H. “Improved Data Structures for Fully Dynamic Biconnectivity.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2000. https://doi.org/10.1137/s0097539794263907.
View | DOI
 
[28]
1999 | Conference Paper | IST-REx-ID: 11691
Goel, Ashish, Monika H Henzinger, Serge Plotkin, and Eva Tardos. “Scheduling Data Transfers in a Network and the Set Scheduling Problem.” In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 189–97. Association for Computing Machinery, 1999. https://doi.org/10.1145/301250.301300.
View | DOI
 
[27]
1999 | Journal Article | IST-REx-ID: 11687
Dean, Jeffrey, and Monika H Henzinger. “Finding Related Pages in the World Wide Web.” Computer Networks. Elsevier, 1999. https://doi.org/10.1016/s1389-1286(99)00022-5.
View | DOI
 
[26]
1999 | Journal Article | IST-REx-ID: 11688
Henzinger, Monika H, Allan Heydon, Michael Mitzenmacher, and Marc Najork. “Measuring Index Quality Using Random Walks on the Web.” Computer Networks. Elsevier, 1999. https://doi.org/10.1016/s1389-1286(99)00016-x.
View | DOI
 
[25]
1999 | Journal Article | IST-REx-ID: 11769
Henzinger, Monika H, and Valerie King. “Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation.” Journal of the ACM. Association for Computing Machinery, 1999. https://doi.org/10.1145/320211.320215.
View | DOI
 
[24]
1999 | Journal Article | IST-REx-ID: 11895 | OA
Silverstein, Craig, Hannes Marais, Monika H Henzinger, and Michael Moricz. “Analysis of a Very Large Web Search Engine Query Log.” ACM SIGIR Forum. Association for Computing Machinery, 1999. https://doi.org/10.1145/331403.331405.
[Published Version] View | DOI | Download Published Version (ext.)
 
[23]
1999 | Journal Article | IST-REx-ID: 11679
Henzinger, Monika H, V. King, and T. Warnow. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” Algorithmica. Springer Nature, 1999. https://doi.org/10.1007/pl00009268.
View | Files available | DOI
 
[22]
1999 | Conference Paper | IST-REx-ID: 11925
Henzinger, Monika H, and Stefano Leonardi  . “Scheduling Multicasts on Unit-Capacity Trees and Meshes.” In 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 438–47. Society for Industrial & Applied Mathematics, 1999.
View
 
[21]
1998 | Conference Paper | IST-REx-ID: 11682
Agarwal, P. K., D. EppsteinL. J. Guibas, and Monika H Henzinger. “Parametric and Kinetic Minimum Spanning Trees.” In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 596–605, 1998. https://doi.org/10.1109/SFCS.1998.743510.
View | DOI
 
[20]
1998 | Journal Article | IST-REx-ID: 11681
Henzinger, Monika H, and M. L. Fredman. “Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.” Algorithmica. Springer Nature, 1998. https://doi.org/10.1007/pl00009228.
View | DOI
 
[19]
1998 | Conference Paper | IST-REx-ID: 11926
Goel, Ashish, Monika H Henzinger, and Serge Plotkin. “An Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control.” In 9th Annual ACM SIAM Symposium on Discrete Algorithms, 97–106. Society for Industrial and Applied Mathematics, 1998.
View | Files available
 
[18]
1998 | Journal Article | IST-REx-ID: 11680
Alberts, D., and Monika H Henzinger. “Average-Case Analysis of Dynamic Graph Algorithms.” Algorithmica. Springer Nature, 1998. https://doi.org/10.1007/pl00009186.
View | Files available | DOI
 
[17]
1997 | Journal Article | IST-REx-ID: 11666
Anderson, Jennifer M., Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika H Henzinger, Shun-Tak A. Leung, Richard L. Sites, Mark T. Vandevoorde, Carl A. Waldspurger, and William E. Weihl. “Continuous Profiling: Where Have All the Cycles Gone?” ACM Transactions on Computer Systems. Association for Computing Machinery, 1997. https://doi.org/10.1145/265924.265925.
View | DOI
 
[16]
1997 | Journal Article | IST-REx-ID: 11767 | OA
Henzinger, Monika H, Philip Klein, Satish Rao, and Sairam Subramanian. “Faster Shortest-Path Algorithms for Planar Graphs.” Journal of Computer and System Sciences. Elsevier, 1997. https://doi.org/10.1006/jcss.1997.1493.
[Published Version] View | DOI | Download Published Version (ext.)
 
[15]
1997 | Journal Article | IST-REx-ID: 11765
Henzinger, Monika H. “A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity.” Journal of Algorithms. Elsevier, 1997. https://doi.org/10.1006/jagm.1997.0855.
View | DOI
 
[14]
1997 | Conference Paper | IST-REx-ID: 11803
Henzinger, Monika H, and Valerie King. “Maintaining Minimum Spanning Trees in Dynamic Graphs.” In 24th International Colloquium on Automata, Languages and Programming, 1256:594–604. Springer Nature, 1997. https://doi.org/10.1007/3-540-63165-8_214.
View | DOI
 
[13]
1997 | Journal Article | IST-REx-ID: 11849 | OA
Anderson, Jennifer M., Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika H Henzinger, Shun-Tak A. Leung, Richard L. Sites, Mark T. Vandevoorde, Carl A. Waldspurger, and William E. Weihl. “Continuous Profiling: Where Have All the Cycles Gone?” ACM SIGOPS Operating Systems Review. Association for Computing Machinery, 1997. https://doi.org/10.1145/269005.266637.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[12]
1997 | Journal Article | IST-REx-ID: 11883
Henzinger, Monika H, and Mikkel Thorup. “Sampling to Provide or to Bound: With Applications to Fully Dynamic Graph Algorithms.” Random Structures and Algorithms. Wiley, 1997. https://doi.org/10.1002/(sici)1098-2418(199712)11:4<369::aid-rsa5>3.0.co;2-x.
View | DOI
 
[11]
1996 | Journal Article | IST-REx-ID: 11761
Henzinger, Monika H, and David P. Williamson. “On the Number of Small Cuts in a Graph.” Information Processing Letters. Elsevier, 1996. https://doi.org/10.1016/0020-0190(96)00079-8.
View | DOI
 
[10]
1996 | Conference Paper | IST-REx-ID: 11804
Henzinger, Monika H, and Jan Arne Telle. “Faster Algorithms for the Nonemptiness of Streett Automata and for Communication Protocol Pruning.” In 5th Scandinavian Workshop on Algorithm Theory, 1097:16–27. Springer Nature, 1996. https://doi.org/10.1007/3-540-61422-2_117.
View | DOI
 
[9]
1996 | Conference Paper | IST-REx-ID: 11910
Henzinger, Monika H, and Mikkel Thorup. “Improved Sampling with Applications to Dynamic Graph Algorithms.” In 23rd International Colloquium on Automata, Languages, and Programming, 1099:290–99. Springer Nature, 1996. https://doi.org/10.1007/3-540-61440-0_136.
View | DOI
 
[8]
1996 | Conference Paper | IST-REx-ID: 11927 | OA
Henzinger, Monika H, Valerie King, and Tandy Warnow. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” In 7th Annual ACM-SIAM Symposium on Discrete Algorithms, 333–40. Society for Industrial and Applied Mathematics, 1996.
[Published Version] View | Files available | Download Published Version (ext.)
 
[7]
1995 | Journal Article | IST-REx-ID: 11677
Henzinger, Monika H. “Fully Dynamic Biconnectivity in Graphs.” Algorithmica. Springer Nature, 1995. https://doi.org/10.1007/bf01189067.
View | DOI
 
[6]
1995 | Conference Paper | IST-REx-ID: 11684
Henzinger, Monika H, and V. King. “Fully Dynamic Biconnectivity and Transitive Closure.” In Proceedings of IEEE 36th Annual Foundations of Computer Science, 664–72. Institute of Electrical and Electronics Engineers, 1995. https://doi.org/10.1109/SFCS.1995.492668.
View | DOI
 
[5]
1995 | Conference Paper | IST-REx-ID: 11806
Henzinger, Monika H. “Approximating Minimum Cuts under Insertions.” In 22nd International Colloquium on Automata, Languages and Programming, 944:280–291. Springer Nature, 1995. https://doi.org/10.1007/3-540-60084-1_81.
View | DOI
 
[4]
1995 | Conference Paper | IST-REx-ID: 11805
Henzinger, Monika H, and Han Poutré. “Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs.” In 3rd Annual European Symposium on Algorithms, 979:171–184. Springer Nature, 1995. https://doi.org/10.1007/3-540-60313-1_142.
View | DOI
 
[3]
1995 | Conference Paper | IST-REx-ID: 11928 | OA
Alberts, David, and Monika H Henzinger. “Average Case Analysis of Dynamic Graph Algorithms.” In 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 312–21. Society for Industrial and Applied Mathematics, 1995.
[Published Version] View | Files available | Download Published Version (ext.)
 
[2]
1995 | Conference Paper | IST-REx-ID: 4498
Henzinger, Monika H, Thomas A Henzinger, and Peter Kopke. “Computing Simulations on Finite and Infinite Graphs.” In Proceedings of IEEE 36th Annual Foundations of Computer Science, 453–62. IEEE, 1995. https://doi.org/10.1109/SFCS.1995.492576.
View | DOI
 
[1]
1994 | Conference Paper | IST-REx-ID: 11857
Henzinger, Monika H. “Fully Dynamic Cycle-Equivalence in Graphs.” In 35th Annual Symposium on Foundations of Computer Science, 744–55. Institute of Electrical and Electronics Engineers, 1994. https://doi.org/10.1109/sfcs.1994.365718.
View | DOI
 
Marked Publication(s)

Search

Filter Publications

    • Display / Sort

    Citation Style: Chicago

    Export / Embed

199 Publications

Mark all

[199]
2024 | Conference Paper | IST-REx-ID: 15008 | OA
Goranci, Gramoz, Monika H Henzinger, Harald Räcke, Sushant Sachdeva, and A. R. Sricharan. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.” In 15th Innovations in Theoretical Computer Science Conference, Vol. 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ITCS.2024.55.
[Published Version] View | Files available | DOI | arXiv
 
[198]
2024 | Conference Paper | IST-REx-ID: 14769 | OA
Henzinger, Monika H, David Saulpic, and Leonhard Sidl. “Experimental Evaluation of Fully Dynamic K-Means via Coresets.” In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, 220–33. Society for Industrial & Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977929.17.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[197]
2024 | Journal Article | IST-REx-ID: 15121 | OA
Zheng, Da Wei, and Monika H Henzinger. “Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching.” Mathematical Programming. Springer Nature, 2024. https://doi.org/10.1007/s10107-024-02066-3.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[196]
2024 | Conference Paper | IST-REx-ID: 15093 | OA
Cultrera di Montesano, Sebastiano, Herbert Edelsbrunner, Monika H Henzinger, and Lara Ost. “Dynamically Maintaining the Persistent Homology of Time Series.” In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), edited by David P. Woodruff, 243–95. Society for Industrial and Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977912.11.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[195]
2024 | Conference Paper | IST-REx-ID: 15253 | OA
Henzinger, Monika H, Jalaj Upadhyay, and Sarvagya Upadhyay. “A Unifying Framework for Differentially Private Sums under Continual Observation.” In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, 2024:995–1018. Society for Industrial and Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977912.38.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[194]
2023 | Conference Paper | IST-REx-ID: 12760 | OA
Henzinger, Monika H, Stefan Neumann, Harald Räcke, and Stefan Schmid. “Dynamic Maintenance of Monotone Dynamic Programs and Applications.” In 40th International Symposium on Theoretical Aspects of Computer Science, Vol. 254. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.STACS.2023.36.
[Published Version] View | Files available | DOI | arXiv
 
[193]
2023 | Conference Paper | IST-REx-ID: 14085 | OA
Goranci, Gramoz, and Monika H Henzinger. “Efficient Data Structures for Incremental Exact and Approximate Maximum Flow.” In 50th International Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.69.
[Published Version] View | Files available | DOI
 
[192]
2023 | Conference Paper | IST-REx-ID: 14086 | OA
Henzinger, Monika H, Paul Liu, Jan Vondrák, and Da Wei Zheng. “Faster Submodular Maximization for Several Classes of Matroids.” In 50th International Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.74.
[Published Version] View | Files available | DOI | arXiv
 
[191]
2023 | Conference Paper | IST-REx-ID: 14462 | OA
Fichtenberger, Hendrik, Monika H Henzinger, and Jalaj Upadhyay. “Constant Matters: Fine-Grained Error Bound on Differentially Private Continual Observation.” In Proceedings of the 40th International Conference on Machine Learning, 202:10072–92. ML Research Press, 2023.
[Published Version] View | Download Published Version (ext.)
 
[190]
2023 | Journal Article | IST-REx-ID: 14558
Bhattacharya, Sayan, Monika H Henzinger, Danupon Nanongkai, and Xiaowei Wu. “Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/21M1428649.
View | DOI
 
[189]
2023 | Journal Article | IST-REx-ID: 14043 | OA
Henzinger, Monika H, Billy Jin, Richard Peng, and David P. Williamson. “A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems.” Algorithmica. Springer Nature, 2023. https://doi.org/10.1007/s00453-023-01154-8.
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[188]
2023 | Conference Paper | IST-REx-ID: 13236 | OA
Zheng, Da Wei, and Monika H Henzinger. “Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching.” In International Conference on Integer Programming and Combinatorial Optimization, 13904:453–65. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-32726-1_32.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[187]
2022 | Journal Article | IST-REx-ID: 11662
Henzinger, Monika H, and Pan Peng. “Constant-Time Dynamic (Δ +1)-Coloring.” ACM Transactions on Algorithms. Association for Computing Machinery (ACM), 2022. https://doi.org/10.1145/3501403.
View | DOI
 
[186]
2022 | Conference Paper | IST-REx-ID: 11812 | OA
Hanauer, Kathrin, Monika H Henzinger, and Qi Cheng Hua. “Fully Dynamic Four-Vertex Subgraph Counting.” In 1st Symposium on Algorithmic Foundations of Dynamic Networks, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.SAND.2022.18.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[185]
2022 | Conference Paper | IST-REx-ID: 11808 | OA
Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Recent Advances in Fully Dynamic Graph Algorithms.” In 1st Symposium on Algorithmic Foundations of Dynamic Networks, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.SAND.2022.1.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[184]
2022 | Conference Paper | IST-REx-ID: 11918
Henzinger, Monika H, Andrea Lincoln, and Barna Saha. “The Complexity of Average-Case Dynamic Subgraph Counting.” In 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, 459–98. Society for Industrial and Applied Mathematics, 2022. https://doi.org/10.1137/1.9781611977073.23.
View | DOI
 
[183]
2022 | Conference Paper | IST-REx-ID: 11930 | OA
Henzinger, Monika H, Alexander Noe, and Christian Schulz. “Practical Fully Dynamic Minimum Cut Algorithms.” In 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments, 13–26. Society for Industrial and Applied Mathematics, 2022. https://doi.org/10.1137/1.9781611977042.2.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[182]
2022 | Preprint | IST-REx-ID: 14236 | OA
Goranci, Gramoz, and Monika H Henzinger. “Incremental Approximate Maximum Flow in M1/2+o(1) Update Time.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2211.09606.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[181]
2021 | Conference Paper | IST-REx-ID: 10054 | OA
Chatterjee, Krishnendu, Monika H Henzinger, Sagar Sudhir Kale, and Alexander Svozil. “Faster Algorithms for Bounded Liveness in Graphs and Game Graphs.” In 48th International Colloquium on Automata, Languages, and Programming, Vol. 198. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.ICALP.2021.124.
[Published Version] View | Files available | DOI
 
[180]
2021 | Conference Paper | IST-REx-ID: 11649 | OA
Henzinger, Monika H, Ami Paz, and Stefan Schmid. “On the Complexity of Weight-Dynamic Network Algorithms.” In IFIP Networking Conference. Institute of Electrical and Electronics Engineers, 2021. https://doi.org/10.23919/ifipnetworking52078.2021.9472803.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[179]
2021 | Journal Article | IST-REx-ID: 11663 | OA
Bernstein, Aaron, Sebastian Forster, and Monika H Henzinger. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” ACM Transactions on Algorithms. Association for Computing Machinery, 2021. https://doi.org/10.1145/3469833.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[178]
2021 | Journal Article | IST-REx-ID: 11756 | OA
Henzinger, Monika H, and Pan Peng. “Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest.” Information and Computation. Elsevier, 2021. https://doi.org/10.1016/j.ic.2021.104805.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[177]
2021 | Conference Paper | IST-REx-ID: 11771 | OA
Henzinger, Monika H, and Xiaowei Wu. “Upper and Lower Bounds for Fully Retroactive Graph Problems.” In 17th International Symposium on Algorithms and Data Structures, 12808:471–484. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-83508-8_34.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[176]
2021 | Conference Paper | IST-REx-ID: 11814 | OA
Fichtenberger, Hendrik, Monika H Henzinger, and Wolfgang Ost. “Differentially Private Algorithms for Graphs under Continual Observation.” In 29th Annual European Symposium on Algorithms, Vol. 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.ESA.2021.42.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[175]
2021 | Journal Article | IST-REx-ID: 11886 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2021. https://doi.org/10.1137/16m1097808.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[174]
2021 | Conference Paper | IST-REx-ID: 11919 | OA
Bergamaschi, Thiago, Monika H Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. “New Techniques and Fine-Grained Hardness for Dynamic near-Additive Spanners.” In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1836–55. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/1.9781611976465.110.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[173]
2021 | Conference Paper | IST-REx-ID: 11923 | OA
Henzinger, Monika H, Stefan Neumann, Harald Räcke, and Stefan Schmid. “Tight Bounds for Online Graph Partitioning.” In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2799–2818. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/1.9781611976465.166.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[172]
2021 | Conference Paper | IST-REx-ID: 11920 | OA
Bhattacharya, Sayan, Monika H Henzinger, Danupon Nanongkai, and Xiaowei Wu. “Dynamic Set Cover: Improved Amortized and Worst-Case Update Time.” In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2537–49. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/1.9781611976465.150.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[171]
2021 | Conference Paper | IST-REx-ID: 11931 | OA
Goranci, Gramoz, Monika H Henzinger, Dariusz Leniowski, Christian Schulz, and Alexander Svozil. “Fully Dynamic K-Center Clustering in Low Dimensional Metrics.” In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments, 143–53. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/1.9781611976472.11.
[Published Version] View | DOI | Download Published Version (ext.)
 
[170]
2021 | Conference Paper | IST-REx-ID: 10002 | OA
Chatterjee, Krishnendu, Wolfgang Dvorak, Monika H Henzinger, and Alexander Svozil. “Symbolic Time and Space Tradeoffs for Probabilistic Verification.” In Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 1–13. Institute of Electrical and Electronics Engineers, 2021. https://doi.org/10.1109/LICS52264.2021.9470739.
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[169]
2021 | Journal Article | IST-REx-ID: 9293 | OA
Chatterjee, Krishnendu, Wolfgang Dvořák, Monika H Henzinger, and Alexander Svozil. “Algorithms and Conditional Lower Bounds for Planning Problems.” Artificial Intelligence. Elsevier, 2021. https://doi.org/10.1016/j.artint.2021.103499.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | WoS | arXiv
 
[168]
2020 | Journal Article | IST-REx-ID: 11675 | OA
Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika H Henzinger. “Deterministic Dynamic Matching in O(1) Update Time.” Algorithmica. Springer Nature, 2020. https://doi.org/10.1007/s00453-019-00630-4.
[Published Version] View | DOI | Download Published Version (ext.)
 
[167]
2020 | Journal Article | IST-REx-ID: 11674 | OA
Henzinger, Monika H, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering to Minimize the Sum of Radii.” Algorithmica. Springer Nature, 2020. https://doi.org/10.1007/s00453-020-00721-7.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[166]
2020 | Conference Paper | IST-REx-ID: 11818 | OA
Henzinger, Monika H, and Sagar Kale. “Fully-Dynamic Coresets.” In 28th Annual European Symposium on Algorithms, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.ESA.2020.57.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[165]
2020 | Conference Paper | IST-REx-ID: 11816 | OA
Henzinger, Monika H, Khan Shahbaz, Richard Paul, and Christian Schulz. “Dynamic Matching Algorithms in Practice.” In 8th Annual European Symposium on Algorithms, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.ESA.2020.58.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[164]
2020 | Conference Paper | IST-REx-ID: 11824 | OA
Henzinger, Monika H, Stefan Neumann, and Andreas Wiese. “Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.51.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[163]
2020 | Conference Paper | IST-REx-ID: 11822 | OA
Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Faster Fully Dynamic Transitive Closure in Practice.” In 18th International Symposium on Experimental Algorithms, Vol. 160. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SEA.2020.14.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[162]
2020 | Conference Paper | IST-REx-ID: 11825 | OA
Henzinger, Monika H, and Pan Peng. “Constant-Time Dynamic (Δ+1)-Coloring.” In 37th International Symposium on Theoretical Aspects of Computer Science, Vol. 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.STACS.2020.53.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[161]
2020 | Conference Paper | IST-REx-ID: 11819 | OA
Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Finding All Global Minimum Cuts in Practice.” In 28th Annual European Symposium on Algorithms, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.ESA.2020.59.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[160]
2020 | Conference Paper | IST-REx-ID: 11852 | OA
Chen, Li, Gramoz Goranci, Monika H Henzinger, Richard Peng, and Thatchaphol Saranurak. “Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers.” In 61st Annual Symposium on Foundations of Computer Science, 1135–46. Institute of Electrical and Electronics Engineers, 2020. https://doi.org/10.1109/focs46700.2020.00109.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[159]
2020 | Conference Paper | IST-REx-ID: 11880 | OA
Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Fully Dynamic Single-Source Reachability in Practice: An Experimental Study.” In 2020 Symposium on Algorithm Engineering and Experiments, 106–19. Society for Industrial and Applied Mathematics, 2020. https://doi.org/10.1137/1.9781611976007.9.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[158]
2020 | Conference Paper | IST-REx-ID: 11881 | OA
Henzinger, Monika H, Alexander Noe, and Christian Schulz. “Shared-Memory Branch-and-Reduce for Multiterminal Cuts.” In 2020 Symposium on Algorithm Engineering and Experiments, 42–55. Society for Industrial and Applied Mathematics, 2020. https://doi.org/10.1137/1.9781611976007.4.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[157]
2020 | Journal Article | IST-REx-ID: 11889
Henzinger, Monika H, Satish Rao, and Di Wang. “Local Flow Partitioning for Faster Edge Connectivity.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2020. https://doi.org/10.1137/18m1180335.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[156]
2020 | Journal Article | IST-REx-ID: 11894 | OA
Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” SIAM Journal on Discrete Mathematics. Society for Industrial & Applied Mathematics, 2020. https://doi.org/10.1137/17m1163153.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[155]
2019 | Conference Paper | IST-REx-ID: 11826 | OA
Ancona, Bertie, Monika H Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein. “Algorithms and Hardness for Diameter in Dynamic Graphs.” In 46th International Colloquium on Automata, Languages, and Programming, Vol. 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.13.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[154]
2019 | Conference Paper | IST-REx-ID: 11850 | OA
Henzinger, Monika H, Stefan Neumann, and Stefan Schmid. “Efficient Distributed Workload (Re-)Embedding.” In SIGMETRICS’19: International Conference on Measurement and Modeling of Computer Systems, 43–44. Association for Computing Machinery, 2019. https://doi.org/10.1145/3309697.3331503.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[153]
2019 | Book Chapter | IST-REx-ID: 11847
Biedermann, Sonja, Monika H Henzinger, Christian Schulz, and Bernhard Schuster. “Vienna Graph Clustering.” In Protein-Protein Interaction Networks, edited by Stefan Canzar and Francisca Rojas Ringeling, 2074:215–231. MIMB. Springer Nature, 2019. https://doi.org/10.1007/978-1-4939-9873-9_16.
View | DOI | PubMed | Europe PMC
 
[152]
2019 | Conference Paper | IST-REx-ID: 11853 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “A New Deterministic Algorithm for Dynamic Set Cover.” In 60th Annual Symposium on Foundations of Computer Science, 406–23. Institute of Electrical and Electronics Engineers, 2019. https://doi.org/10.1109/focs.2019.00033.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[151]
2019 | Conference Paper | IST-REx-ID: 11851
Henzinger, Monika H, Alexander Noe, and Christian Schulz. “Shared-Memory Exact Minimum Cuts.” In 33rd International Parallel and Distributed Processing Symposium. Institute of Electrical and Electronics Engineers, 2019. https://doi.org/10.1109/ipdps.2019.00013.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[150]
2019 | Conference Paper | IST-REx-ID: 11865 | OA
Daga, Mohit, Monika H Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak. “Distributed Edge Connectivity in Sublinear Time.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 343–354. Association for Computing Machinery, 2019. https://doi.org/10.1145/3313276.3316346.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[149]
2019 | Conference Paper | IST-REx-ID: 11871 | OA
Bernstein, Aaron, Sebastian Forster, and Monika H Henzinger. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” In 30th Annual ACM-SIAM Symposium on Discrete Algorithms, 1899–1918. Society for Industrial and Applied Mathematics, 2019. https://doi.org/10.1137/1.9781611975482.115.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[148]
2019 | Journal Article | IST-REx-ID: 11898 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Stefan Neumann. “New Amortized Cell-Probe Lower Bounds for Dynamic Problems.” Theoretical Computer Science. Elsevier, 2019. https://doi.org/10.1016/j.tcs.2019.01.043.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[147]
2019 | Conference Paper | IST-REx-ID: 6887 | OA
Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Alexander Svozil. “Near-Linear Time Algorithms for Streett Objectives in Graphs and MDPs.” In Leibniz International Proceedings in Informatics, Vol. 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.CONCUR.2019.7.
[Published Version] View | Files available | DOI
 
[146]
2018 | Conference Paper | IST-REx-ID: 10883 | OA
Chatterjee, Krishnendu, Wolfgang Dvořák, Monika H Henzinger, and Alexander Svozil. “Quasipolynomial Set-Based Symbolic Algorithms for Parity Games.” In 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, 57:233–53. EasyChair, 2018. https://doi.org/10.29007/5z5k.
[Published Version] View | Files available | DOI | arXiv
 
[145]
2018 | Journal Article | IST-REx-ID: 11657 | OA
Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Practical Minimum Cut Algorithms.” ACM Journal of Experimental Algorithmics. Association for Computing Machinery, 2018. https://doi.org/10.1145/3274662.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[144]
2018 | Journal Article | IST-REx-ID: 11667 | OA
Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Valuation Compressions in VCG-Based Combinatorial Auctions.” ACM Transactions on Economics and Computation. Association for Computing Machinery, 2018. https://doi.org/10.1145/3232860.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[143]
2018 | Journal Article | IST-REx-ID: 11664 | OA
Goranci, Gramoz, Monika H Henzinger, and Mikkel Thorup. “Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time.” ACM Transactions on Algorithms. Association for Computing Machinery, 2018. https://doi.org/10.1145/3174803.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[142]
2018 | Journal Article | IST-REx-ID: 11757 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe Italiano. “Dynamic Algorithms via the Primal-Dual Method.” Information and Computation. Elsevier, 2018. https://doi.org/10.1016/j.ic.2018.02.005.
[Published Version] View | DOI | Download Published Version (ext.)
 
[141]
2018 | Conference Paper | IST-REx-ID: 11828 | OA
Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.” In 26th Annual European Symposium on Algorithms, Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.ESA.2018.40.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[140]
2018 | Conference Paper | IST-REx-ID: 11827 | OA
Goranci, Gramoz , Monika H Henzinger, and Dariusz Leniowski. “A Tree Structure for Dynamic Facility Location.” In 26th Annual European Symposium on Algorithms, Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.ESA.2018.39.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[139]
2018 | Journal Article | IST-REx-ID: 11768 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” Journal of the ACM. Association for Computing Machinery, 2018. https://doi.org/10.1145/3218657.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[138]
2018 | Conference Paper | IST-REx-ID: 11872 | OA
Bhattacharya, Sayan, Deeparnab Chakrabarty, Monika H Henzinger, and Danupon Nanongkai. “Dynamic Algorithms for Graph Coloring.” In 29th Annual ACM-SIAM Symposium on Discrete Algorithms, 1–20. Society for Industrial and Applied Mathematics, 2018. https://doi.org/10.1137/1.9781611975031.1.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[137]
2018 | Conference Paper | IST-REx-ID: 11882 | OA
Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Practical Minimum Cut Algorithms.” In 20th Workshop on Algorithm Engineering and Experiments, 48–61. Society for Industrial and Applied Mathematics, 2018. https://doi.org/10.1137/1.9781611975055.5.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[136]
2018 | Journal Article | IST-REx-ID: 11890 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2018. https://doi.org/10.1137/140998925.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[135]
2018 | Conference Paper | IST-REx-ID: 11911 | OA
Biedermann, Sonja, Monika H Henzinger, Christian Schulz, and Bernhard Schuster. “Memetic Graph Clustering.” In 17th International Symposium on Experimental Algorithms, Vol. 103. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.SEA.2018.3.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[134]
2018 | Conference Paper | IST-REx-ID: 310 | OA
Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Veronika Loitzenbauer. “Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter,” 2341–56. ACM, 2018. https://doi.org/10.1137/1.9781611975031.151.
[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv
 
[133]
2018 | Conference Paper | IST-REx-ID: 141 | OA
Chatterjee, Krishnendu, Monika H Henzinger, Veronika Loitzenbauer, Simin Oraee, and Viktor Toman. “Symbolic Algorithms for Graphs and Markov Decision Processes with Fairness Objectives,” 10982:178–97. Springer, 2018. https://doi.org/10.1007/978-3-319-96142-2_13.
[Published Version] View | Files available | DOI | WoS
 
[132]
2018 | Conference Paper | IST-REx-ID: 35 | OA
Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Alexander Svozil. “Algorithms and Conditional Lower Bounds for Planning Problems.” In 28th International Conference on Automated Planning and Scheduling . AAAI Press, 2018.
View | Files available | Download None (ext.) | WoS | arXiv
 
[131]
2017 | Conference Paper | IST-REx-ID: 11651 | OA
Wang, Di, Kimon Fountoulakis, Monika H Henzinger, Michael W. Mahoney, and Satish Rao . “Capacity Releasing Diffusion for Speed and Locality.” In Proceedings of the 34th International Conference on Machine Learning, 70:3598–3607. ML Research Press, 2017.
[Published Version] View | Download Published Version (ext.) | arXiv
 
[130]
2017 | Journal Article | IST-REx-ID: 11665 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.” ACM Transactions on Algorithms. Association for Computing Machinery, 2017. https://doi.org/10.1145/3146550.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[129]
2017 | Journal Article | IST-REx-ID: 11676 | OA
Dvořák, Wolfgang, Monika H Henzinger, and David P. Williamson. “Maximizing a Submodular Function with Viability Constraints.” Algorithmica. Springer Nature, 2017. https://doi.org/10.1007/s00453-015-0066-y.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[128]
2017 | Conference Paper | IST-REx-ID: 11772
Henzinger, Monika H. “The State of the Art in Dynamic Graph Algorithms.” In 44th International Conference on Current Trends in Theory and Practice of Computer Science, 10706:40–44. Springer Nature, 2017. https://doi.org/10.1007/978-3-319-73117-9_3.
View | DOI
 
[127]
2017 | Conference Paper | IST-REx-ID: 11829 | OA
Henzinger, Monika H, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. “Conditional Hardness for Sensitivity Problems.” In 8th Innovations in Theoretical Computer Science Conference, Vol. 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ITCS.2017.26.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[126]
2017 | Conference Paper | IST-REx-ID: 11833 | OA
Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.” In 25th Annual European Symposium on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.45.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[125]
2017 | Conference Paper | IST-REx-ID: 11832 | OA
Henzinger, Monika H, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering to Minimize the Sum of Radii.” In 25th Annual European Symposium on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.48.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[124]
2017 | Conference Paper | IST-REx-ID: 11874 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in o(Log3 n) Worst Case Update Time.” In 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 0:470–89. Society for Industrial and Applied Mathematics, 2017. https://doi.org/10.1137/1.9781611974782.30.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[123]
2017 | Conference Paper | IST-REx-ID: 11873 | OA
Henzinger, Monika H, Satish Rao, and Di Wang. “Local Flow Partitioning for Faster Edge Connectivity.” In 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 1919–38. Society for Industrial and Applied Mathematics, 2017. https://doi.org/10.1137/1.9781611974782.125.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[122]
2017 | Conference Paper | IST-REx-ID: 11831 | OA
Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” In 25th Annual European Symposium on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.44.
[Published Version] View | Files available | DOI | Download Published Version (ext.) | arXiv
 
[121]
2017 | Journal Article | IST-REx-ID: 11903 | OA
Bhattacharya, Sayan, Wolfgang Dvořák, Monika H Henzinger, and Martin Starnberger. “Welfare Maximization with Friends-of-Friends Network Externalities.” Theory of Computing Systems. Springer Nature, 2017. https://doi.org/10.1007/s00224-017-9759-8.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[120]
2017 | Conference Paper | IST-REx-ID: 12571 | OA
Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika H Henzinger. “Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time.” In 19th International Conference on Integer Programming and Combinatorial Optimization, 10328:86–98. Springer Nature, 2017. https://doi.org/10.1007/978-3-319-59250-3_8.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[119]
2017 | Journal Article | IST-REx-ID: 464 | OA
Chatterjee, Krishnendu, Monika H Henzinger, and Veronika Loitzenbauer. “Improved Algorithms for Parity and Streett Objectives.” Logical Methods in Computer Science. International Federation of Computational Logic, 2017. https://doi.org/10.23638/LMCS-13(3:26)2017.
[Published Version] View | Files available | DOI | arXiv
 
[118]
2017 | Conference Paper | IST-REx-ID: 552 | OA
Chatterjee, Krishnendu, Monika H Henzinger, and Alexander Svozil. “Faster Algorithms for Mean-Payoff Parity Games.” In Leibniz International Proceedings in Informatics, Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.MFCS.2017.39.
[Published Version] View | Files available | DOI
 
[117]
2017 | Conference Paper | IST-REx-ID: 6519 | OA
Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Veronika Loitzenbauer. “Improved Set-Based Symbolic Algorithms for Parity Games,” Vol. 82. Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, 2017. https://doi.org/10.4230/LIPICS.CSL.2017.18.
[Published Version] View | Files available | DOI
 
[116]
2016 | Conference Paper | IST-REx-ID: 1068 | OA
Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Veronika Loitzenbauer. “Conditionally Optimal Algorithms for Generalized Büchi Games,” Vol. 58. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPIcs.MFCS.2016.25.
[Published Version] View | Files available | DOI
 
[115]
2016 | Conference Paper | IST-REx-ID: 1140 | OA
Chatterjee, Krishnendu, Wolfgang Dvoák, Monika H Henzinger, and Veronika Loitzenbauer. “Model and Objective Separation with Conditional Lower Bounds: Disjunction Is Harder than Conjunction.” In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 197–206. IEEE, 2016. https://doi.org/10.1145/2933575.2935304.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[114]
2016 | Conference Paper | IST-REx-ID: 11836 | OA
Cheung, Yun Kuen, Gramoz Goranci, and Monika H Henzinger. “Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds.” In 43rd International Colloquium on Automata, Languages, and Programming, Vol. 55. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPICS.ICALP.2016.131.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[113]
2016 | Conference Paper | IST-REx-ID: 11834 | OA
Goranci, Gramoz, Monika H Henzinger, and Mikkel Thorup. “Incremental Exact Min-Cut in Poly-Logarithmic Amortized Update Time.” In 24th Annual European Symposium on Algorithms, Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPICS.ESA.2016.46.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[112]
2016 | Conference Paper | IST-REx-ID: 11835 | OA
Henzinger, Monika H, and Stefan Neumann. “Incremental and Fully Dynamic Subgraph Connectivity for Emergency Planning.” In 24th Annual European Symposium on Algorithms, Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPICS.ESA.2016.48.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[111]
2016 | Conference Paper | IST-REx-ID: 11866 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” In 48th Annual ACM SIGACT Symposium on Theory of Computing, 489–98. Association for Computing Machinery, 2016. https://doi.org/10.1145/2897518.2897638.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[110]
2016 | Conference Paper | IST-REx-ID: 11867 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “New Deterministic Approximation Algorithms for Fully Dynamic Matching.” In 48th Annual ACM SIGACT Symposium on Theory of Computing, 398–411. Association for Computing Machinery, 2016. https://doi.org/10.1145/2897518.2897568.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[109]
2016 | Journal Article | IST-REx-ID: 11891 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2016. https://doi.org/10.1137/140957299.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[108]
2015 | Journal Article | IST-REx-ID: 11668 | OA
Colini-Baldeschi, Riccardo, Stefano Leonardi, Monika H Henzinger, and Martin Starnberger. “On Multiple Keyword Sponsored Search Auctions with Budgets.” ACM Transactions on Economics and Computation. Association for Computing Machinery, 2015. https://doi.org/10.1145/2818357.
[Submitted Version] View | DOI | Download Submitted Version (ext.)
 
[107]
2015 | Journal Article | IST-REx-ID: 11669 | OA
Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Auctions for Heterogeneous Items and Budget Limits.” ACM Transactions on Economics and Computation. Association for Computing Machinery, 2015. https://doi.org/10.1145/2818351.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[106]
2015 | Journal Article | IST-REx-ID: 11670
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “An Expressive Mechanism for Auctions on the Web.” ACM Transactions on Economics and Computation. Association for Computing Machinery, 2015. https://doi.org/10.1145/2716312.
View | DOI
 
[105]
2015 | Conference Paper | IST-REx-ID: 11774 | OA
Cheung, Yun Kuen, Monika H Henzinger, Martin Hoefer, and Martin Starnberger. “Combinatorial Auctions with Conflict-Based Externalities.” In 11th International Conference on Web and Internet Economics, 9470:230–243. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-48995-6_17.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[104]
2015 | Conference Paper | IST-REx-ID: 11773 | OA
Ben-Zwi, Oren, Monika H Henzinger, and Veronika Loitzenbauer. “Ad Exchange: Envy-Free Auctions with Mediators.” In 11th International Conference on Web and Internet Economics, 9470:104–117. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-48995-6_8.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[103]
2015 | Conference Paper | IST-REx-ID: 11785 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.” In 42nd International Colloquium on Automata, Languages and Programming, 9134:725–36. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_59.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[102]
2015 | Conference Paper | IST-REx-ID: 11787 | OA
Henzinger, Monika H, Sebastian Krinninger, and Veronika Loitzenbauer. “Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.” In 2nd International Colloquium on Automata, Languages and Programming, 9134:713–24. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_58.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[101]
2015 | Conference Paper | IST-REx-ID: 11788 | OA
Dvořák, Wolfgang, and Monika H Henzinger. “Online Ad Assignment with an Ad Exchange.” In 12th International Workshop of Approximation and Online Algorithms, 8952:156–167. Springer Nature, 2015. https://doi.org/10.1007/978-3-319-18263-6_14.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[100]
2015 | Conference Paper | IST-REx-ID: 11786 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Design of Dynamic Algorithms via Primal-Dual Method.” In 42nd International Colloquium on Automata, Languages and Programming, 9134:206–18. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_17.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[99]
2015 | Journal Article | IST-REx-ID: 11845 | OA
Chernomor, Olga, Bui Quang Minh, Félix Forest, Steffen Klaere, Travis Ingram, Monika H Henzinger, and Arndt von Haeseler. “Split Diversity in Constrained Conservation Prioritization Using Integer Linear Programming.” Methods in Ecology and Evolution. Wiley, 2015. https://doi.org/10.1111/2041-210x.12299.
[Published Version] View | Files available | DOI | PubMed | Europe PMC
 
[98]
2015 | Conference Paper | IST-REx-ID: 11868 | OA
Henzinger, Monika H, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. “Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.” In 47th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 2015. https://doi.org/10.1145/2746539.2746609.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[97]
2015 | Conference Paper | IST-REx-ID: 11869 | OA
Bhattacharya, Sayan, Monika H Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. “Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.” In 47th Annual ACM Symposium on Theory of Computing, 173–82. Association for Computing Machinery, 2015. https://doi.org/10.1145/2746539.2746592.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[96]
2015 | Conference Paper | IST-REx-ID: 11837 | OA
Bhattacharya, Sayan, Wolfgang Dvorák, Monika H Henzinger, and Martin Starnberger. “Welfare Maximization with Friends-of-Friends Network Externalities.” In 32nd International Symposium on Theoretical Aspects of Computer Science, 30:90–102. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. https://doi.org/10.4230/LIPICS.STACS.2015.90.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[95]
2015 | Journal Article | IST-REx-ID: 11901 | OA
Henzinger, Monika H, and Veronika Loitzenbauer. “Truthful Unit-Demand Auctions with Budgets Revisited.” Theoretical Computer Science. Elsevier, 2015. https://doi.org/10.1016/j.tcs.2015.01.033.
View | DOI | Download None (ext.)
 
[94]
2015 | Conference Paper | IST-REx-ID: 1661 | OA
Chatterjee, Krishnendu, Monika H Henzinger, and Veronika Loitzenbauer. “Improved Algorithms for One-Pair and k-Pair Streett Objectives.” In Proceedings - Symposium on Logic in Computer Science, Vol. 2015–July. IEEE, 2015. https://doi.org/10.1109/LICS.2015.34.
[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.)
 
[93]
2014 | Conference Paper | IST-REx-ID: 11789 | OA
Charikar, Moses, Monika H Henzinger, and Huy L. Nguyễn. “Online Bipartite Matching with Decomposable Weights.” In 22nd Annual European Symposium on Algorithms, 8737:260–71. Springer Nature, 2014. https://doi.org/10.1007/978-3-662-44777-2_22.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[92]
2014 | Conference Paper | IST-REx-ID: 11790
Cigler, Luděk, Wolfgang Dvořák, Monika H Henzinger, and Martin Starnberger. “Limiting Price Discrimination When Selling Products with Positive Network Externalities.” In 10th International Conference of Web and Internet Economics, 8877:44–57. Springer Nature, 2014. https://doi.org/10.1007/978-3-319-13129-0_4.
View | DOI
 
[91]
2014 | Conference Paper | IST-REx-ID: 11855 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” In 55th Annual Symposium on Foundations of Computer Science, 146–55. Institute of Electrical and Electronics Engineers, 2014. https://doi.org/10.1109/focs.2014.24.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[90]
2014 | Conference Paper | IST-REx-ID: 11870 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs.” In 46th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 2014. https://doi.org/10.1145/2591796.2591869.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[89]
2014 | Conference Paper | IST-REx-ID: 11876 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths.” In 25th Annual ACM-SIAM Symposium on Discrete Algorithms, 1053–72. Society for Industrial and Applied Mathematics, 2014. https://doi.org/10.1137/1.9781611973402.79.
[Published Version] View | DOI | Download Published Version (ext.)
 
[88]
2014 | Conference Paper | IST-REx-ID: 11875 | OA
Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” In 26th Annual ACM-SIAM Symposium on Discrete Algorithms, 785–804. Society for Industrial and Applied Mathematics, 2014. https://doi.org/10.1137/1.9781611973730.54.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[87]
2014 | Journal Article | IST-REx-ID: 1375 | OA
Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, Veronika Loitzenbauer, and Michael Raskin. “Approximating the Minimum Cycle Mean.” Theoretical Computer Science. Elsevier, 2014. https://doi.org/10.1016/j.tcs.2014.06.031.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[86]
2014 | Journal Article | IST-REx-ID: 2141 | OA
Chatterjee, Krishnendu, and Monika H Henzinger. “Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition.” Journal of the ACM. ACM, 2014. https://doi.org/10.1145/2597631.
[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.)
 
[85]
2014 | Journal Article | IST-REx-ID: 535 | OA
Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” Algorithmica. Springer, 2014. https://doi.org/10.1007/s00453-013-9843-7.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[84]
2013 | Journal Article | IST-REx-ID: 11671
Baykan, Eda, Ingmar Weber, and Monika H Henzinger. “A Comprehensive Study of Techniques for URL-Based Web Page Language Classification.” ACM Transactions on the Web. Association for Computing Machinery, 2013. https://doi.org/10.1145/2435215.2435218.
View | DOI
 
[83]
2013 | Journal Article | IST-REx-ID: 11759 | OA
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Sponsored Search, Market Equilibria, and the Hungarian Method.” Information Processing Letters. Elsevier, 2013. https://doi.org/10.1016/j.ipl.2012.11.006.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[82]
2013 | Conference Paper | IST-REx-ID: 11793 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks.” In 40th International Colloquium on Automata, Languages, and Programming, 7966:607–619. Springer Nature, 2013. https://doi.org/10.1007/978-3-642-39212-2_53.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[81]
2013 | Conference Paper | IST-REx-ID: 11791 | OA
Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Valuation Compressions in VCG-Based Combinatorial Auctions.” In 9th International Conference on Web and Internet Economics, 8289:146–159. Springer Nature, 2013. https://doi.org/10.1007/978-3-642-45046-4_13.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[80]
2013 | Conference Paper | IST-REx-ID: 11792 | OA
Dvořák, Wolfgang, Monika H Henzinger, and David P. Williamson. “Maximizing a Submodular Function with Viability Constraints.” In 21st Annual European Symposium on Algorithms, 8125:409–20. Springer Nature, 2013. https://doi.org/10.1007/978-3-642-40450-4_35.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[79]
2013 | Conference Paper | IST-REx-ID: 11856 | OA
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.” In 54th Annual Symposium on Foundations of Computer Science, 538–47. Institute of Electrical and Electronics Engineers, 2013. https://doi.org/10.1109/focs.2013.64.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[78]
2013 | Journal Article | IST-REx-ID: 11902
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Bidder Optimal Assignments for General Utilities.” Theoretical Computer Science. Elsevier, 2013. https://doi.org/10.1016/j.tcs.2013.01.030.
View | Files available | DOI
 
[77]
2013 | Journal Article | IST-REx-ID: 11758
Aceto, Luca, Monika H Henzinger, and Jiří Sgall. “38th International Colloquium on Automata, Languages and Programming.” Information and Computation. Elsevier, 2013. https://doi.org/10.1016/j.ic.2012.11.002.
View | DOI
 
[76]
2013 | Journal Article | IST-REx-ID: 2831 | OA
Chatterjee, Krishnendu, Monika H Henzinger, Manas Joglekar, and Nisarg Shah. “Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives.” Formal Methods in System Design. Springer, 2013. https://doi.org/10.1007/s10703-012-0180-2.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[75]
2012 | Conference Paper | IST-REx-ID: 11656
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Maximizing Revenue from Strategic Recommendations under Decaying Trust.” In Proceedings of the 21st ACM International Conference on Information and Knowledge Management, 2268–86. Association for Computing Machinery, 2012. https://doi.org/10.1145/2396761.2398621.
View | DOI
 
[74]
2012 | Conference Paper | IST-REx-ID: 11794 | OA
Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Auctions with Heterogeneous Items and Budget Limits.” In 8th International Workshop on Internet and Network Economics, 7695:44–57. Springer Nature, 2012. https://doi.org/10.1007/978-3-642-35311-6_4.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[73]
2012 | Conference Paper | IST-REx-ID: 11795
Colini-Baldeschi, Riccardo, Monika H Henzinger, Stefano Leonardi, and Martin Starnberger. “On Multiple Keyword Sponsored Search Auctions with Budgets.” In 39th International Colloquium on Automata, Languages, and Programming, 7392:1–12. Springer Nature, 2012. https://doi.org/10.1007/978-3-642-31585-5_1.
View | Files available | DOI
 
[72]
2012 | Conference Paper | IST-REx-ID: 3165 | OA
Chatterjee, Krishnendu, and Monika H Henzinger. “An O(N2) Time Algorithm for Alternating Büchi Games.” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 1386–99. SIAM, 2012. https://doi.org/10.1137/1.9781611973099.109.
View | Files available | DOI | Download None (ext.) | arXiv
 
[71]
2012 | Conference Paper | IST-REx-ID: 10905 | OA
Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” In Algorithms – ESA 2012, 7501:301–12. Springer, 2012. https://doi.org/10.1007/978-3-642-33090-2_27.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[70]
2011 | Journal Article | IST-REx-ID: 11673
Baykan, Eda, Monika H Henzinger, Ludmila Marian, and Ingmar Weber. “A Comprehensive Study of Features and Algorithms for URL-Based Topic Classification.” ACM Transactions on the Web. Association for Computing Machinery, 2011. https://doi.org/10.1145/1993053.1993057.
View | DOI
 
[69]
2011 | Journal Article | IST-REx-ID: 11760
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Offline File Assignments for Online Load Balancing.” Information Processing Letters. Elsevier, 2011. https://doi.org/10.1016/j.ipl.2010.11.022.
View | DOI
 
[68]
2011 | Conference Paper | IST-REx-ID: 11796
Henzinger, Monika H, and Angelina Vidali. “Multi-Parameter Mechanism Design under Budget and Matroid Constraints.” In 19th Annual European Symposium on Algorithms, 6942:192–202. Springer Nature, 2011. https://doi.org/10.1007/978-3-642-23719-5_17.
View | DOI
 
[67]
2011 | Conference Paper | IST-REx-ID: 11864
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “An Expressive Mechanism for Auctions on the Web.” In Proceedings of the 20th International Conference on World Wide Web, 127–36. Association for Computing Machinery, 2011. https://doi.org/10.1145/1963405.1963427.
View | DOI
 
[66]
2011 | Conference Paper | IST-REx-ID: 3342 | OA
Chatterjee, Krishnendu, Monika H Henzinger, Manas Joglekar, and Shah Nisarg. “Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives.” edited by Ganesh Gopalakrishnan and Shaz Qadeer, 6806:260–76. Springer, 2011. https://doi.org/10.1007/978-3-642-22110-1_21.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
[65]
2011 | Conference Paper | IST-REx-ID: 3343 | OA
Chatterjee, Krishnendu, and Monika H Henzinger. “Faster and Dynamic Algorithms for Maximal End-Component Decomposition and Related Graph Problems in Probabilistic Verification,” 1318–36. SIAM, 2011. https://doi.org/10.1137/1.9781611973082.101.
[Submitted Version] View | DOI | Download Submitted Version (ext.)
 
[64]
2011 | Technical Report | IST-REx-ID: 5379 | OA
Chatterjee, Krishnendu, and Monika H Henzinger. An O(N2) Time Algorithm for Alternating Büchi Games. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0009.
[Published Version] View | Files available | DOI
 
[63]
2010 | Conference Paper | IST-REx-ID: 11797 | OA
Feldman, Jon, Monika H Henzinger, Nitish Korula, Vahab S. Mirrokni, and Cliff Stein. “Online Stochastic Packing Applied to Display Ad Allocation.” In 18th Annual European Symposium on Algorithms, 6346:182–194. Springer Nature, 2010. https://doi.org/10.1007/978-3-642-15775-2_16.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
[62]
2010 | Conference Paper | IST-REx-ID: 11798
Dütting, Paul, and Monika H Henzinger. “Mechanisms for the Marriage and the Assignment Game.” In 7th International Conference on Algorithms and Complexity, 6078:6–12. Springer Nature, 2010. https://doi.org/10.1007/978-3-642-13073-1_2.
View | DOI
 
[61]
2010 | Conference Paper | IST-REx-ID: 11838 | OA
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Sponsored Search, Market Equilibria, and the Hungarian Method.” In 27th International Symposium on Theoretical Aspects of Computer Science, 5:287–98. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. https://doi.org/10.4230/LIPICS.STACS.2010.2463.
[Published Version] View | Files available | DOI | Download Published Version (ext.) | arXiv
 
[60]
2010 | Conference Paper | IST-REx-ID: 11863
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “How Much Is Your Personal Recommendation Worth?” In Proceedings of the 19th International Conference on World Wide Web , 1085–86. Association for Computing Machinery, 2010. https://doi.org/10.1145/1772690.1772816.
View | DOI
 
[59]
2010 | Journal Article | IST-REx-ID: 11885
Henzinger, Monika H, Jacob Suñol, and Ingmar Weber. “The Stability of the H-Index.” Scientometrics. Springer Nature, 2010. https://doi.org/10.1007/s11192-009-0098-7.
View | DOI
 
[58]
2009 | Conference Paper | IST-REx-ID: 11799
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Bidder Optimal Assignments for General Utilities.” In 5th International Workshop on Internet and Network Economics, 5929:575–82. Springer Nature, 2009. https://doi.org/10.1007/978-3-642-10841-9_58.
View | Files available | DOI
 
[57]
2009 | Conference Paper | IST-REx-ID: 11912 | OA
Baykan, Eda, Monika H Henzinger, Stefan F. Keller, Sebastian de Castelberg, and Markus Kinzler. “A Comparison of Techniques for Sampling Web Pages.” In 26th International Symposium on Theoretical Aspects of Computer Science, 3:13–30. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009. https://doi.org/10.4230/LIPICS.STACS.2009.1809.
[Published Version] View | DOI | Download Published Version (ext.) | arXiv
 
[56]
2009 | Conference Paper | IST-REx-ID: 11905
Baykan, Eda, Monika H Henzinger, Ludmila Marian, and Ingmar Weber. “Purely URL-Based Topic Classification.” In 18th International World Wide Web Conference, 1109–10. Association for Computing Machinery, 2009. https://doi.org/10.1145/1526709.1526880.
View | DOI
 
[55]
2009 | Conference Paper | IST-REx-ID: 11906
Abdel Hamid, Ossama, Behshad Behzadi, Stefan Christoph, and Monika H Henzinger. “Detecting the Origin of Text Segments Efficiently.” In 18th International World Wide Web Conference, 61–70. Association for Computing Machinery, 2009. https://doi.org/10.1145/1526709.1526719.
View | DOI
 
[54]
2008 | Journal Article | IST-REx-ID: 11878
Baykan, Eda, Monika H Henzinger, and Ingmar Weber. “Web Page Language Identification Based on URLs.” Proceedings of the VLDB Endowment. Association for Computing Machinery, 2008. https://doi.org/10.14778/1453856.1453880.
View | DOI
 
[53]
2007 | Journal Article | IST-REx-ID: 11884
Henzinger, Monika H. “Search Technologies for the Internet.” Science. American Association for the Advancement of Science, 2007. https://doi.org/10.1126/science.1126557.
View | DOI | PubMed | Europe PMC
 
[52]
2007 | Conference Paper | IST-REx-ID: 11924
Henzinger, Monika H. “Combinatorial Algorithms for Web Search Engines: Three Success Stories.” In 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 1022–26. Society for Industrial & Applied Mathematics, 2007.
View
 
[51]
2006 | Conference Paper | IST-REx-ID: 11929
Henzinger, Monika H. “Finding Near-Duplicate Web Pages: A Large-Scale Evaluation of Algorithms.” In 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 284–91. Association for Computing Machinery, 2006. https://doi.org/10.1145/1148170.1148222.
View | DOI
 
[50]
2005 | Conference Paper | IST-REx-ID: 11698
Henzinger, Monika H. “Hyperlink Analysis on the World Wide Web.” In Proceedings of the 16th ACM Conference on Hypertext and Hypermedia, 1–3. Association for Computing Machinery, 2005. https://doi.org/10.1145/1083356.1083357.
View | DOI
 
[49]
2005 | Journal Article | IST-REx-ID: 11904
Henzinger, Monika H, Bay-Wei Chang, Brian Milch, and Sergey Brin. “Query-Free News Search.” World Wide Web. Springer Nature, 2005. https://doi.org/10.1007/s11280-004-4870-6.
View | Files available | DOI
 
[48]
2005 | Journal Article | IST-REx-ID: 11763 | OA
Goel, Ashish, Monika H Henzinger, and Serge Plotkin. “An Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control.” Journal of Algorithms. Elsevier, 2005. https://doi.org/10.1016/j.jalgor.2004.11.001.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[47]
2004 | Journal Article | IST-REx-ID: 11762 | OA
Henzinger, Monika H. “Algorithmic Challenges in Web Search Engines.” Internet Mathematics. Internet Mathematics, 2004. https://doi.org/10.1080/15427951.2004.10129079.
[Published Version] View | DOI | Download Published Version (ext.)
 
[46]
2004 | Conference Paper | IST-REx-ID: 11801
Henzinger, Monika H. “Algorithmic Aspects of Web Search Engines.” In 2th Annual European Symposium on Algorithms, 3221:3. Springer Nature, 2004. https://doi.org/10.1007/978-3-540-30140-0_2.
View | DOI
 
[45]
2004 | Conference Paper | IST-REx-ID: 11800
Henzinger, Monika H. “The Past, Present, and Future of Web Search Engines.” In 31st International Colloquium on Automata, Languages and Programming, 3142:3. Springer Nature, 2004. https://doi.org/10.1007/978-3-540-27836-8_2.
View | DOI
 
[44]
2004 | Conference Paper | IST-REx-ID: 11859
Henzinger, Monika H. “The Past, Present, and Future of Web Information Retrieval.” In SPIE Proceedings, 5296:23–26. Society of Photo-Optical Instrumentation Engineers, 2004. https://doi.org/10.1117/12.537534.
View | DOI
 
[43]
2004 | Journal Article | IST-REx-ID: 11877 | OA
Henzinger, Monika H, and Steve Lawrence. “Extracting Knowledge from the World Wide Web.” Proceedings of the National Academy of Sciences. Proceedings of the National Academy of Sciences, 2004. https://doi.org/10.1073/pnas.0307528100.
[Published Version] View | DOI | Download Published Version (ext.) | PubMed | Europe PMC
 
[42]
2003 | Journal Article | IST-REx-ID: 11766 | OA
Henzinger, Monika H, and Stefano Leonardi. “Scheduling Multicasts on Unit-Capacity Trees and Meshes.” Journal of Computer and System Sciences. Elsevier, 2003. https://doi.org/10.1016/s0022-0000(03)00043-6.
[Published Version] View | DOI | Download Published Version (ext.)
 
[41]
2003 | Journal Article | IST-REx-ID: 11764
Goel, Ashish, Monika H Henzinger, Serge Plotkin, and Eva Tardos. “Scheduling Data Transfers in a Network and the Set Scheduling Problem.” Journal of Algorithms. Elsevier, 2003. https://doi.org/10.1016/s0196-6774(03)00054-3.
View | DOI
 
[40]
2003 | Conference Paper | IST-REx-ID: 11897
Bharat, Krishna, and Monika H Henzinger. “Improved Algorithms for Topic Distillation in a Hyperlinked Environment.” In 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 104–111. Association for Computing Machinery, 2003. https://doi.org/10.1145/290941.290972.
View | DOI
 
[39]
2003 | Conference Paper | IST-REx-ID: 11860
Henzinger, Monika H, Bay-Wei Chang, Brian Milch, and Sergey Brin. “Query-Free News Search.” In Proceedings of the 12th International Conference on World Wide Web. Association for Computing Machinery, 2003. https://doi.org/10.1145/775152.775154.
View | Files available | DOI
 
[38]
2003 | Conference Paper | IST-REx-ID: 11909 | OA
Henzinger, Monika H, Rajeev Motwani, and Craig Silverstein. “Challenges in Web Search Engines.” In 18th International Joint Conference on Artificial Intelligence, 1573–79. Association for Computing Machinery, 2003.
[Published Version] View | Download Published Version (ext.)
 
[37]
2001 | Journal Article | IST-REx-ID: 11892
Henzinger, Monika H, and Valerie King. “Maintaining Minimum Spanning Forests in Dynamic Graphs.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2001. https://doi.org/10.1137/s0097539797327209.
View | DOI
 
[36]
2001 | Conference Paper | IST-REx-ID: 11914
Bharat, K., Bay-Wei Chang, Monika H Henzinger, and M. Ruhl. “Who Links to Whom: Mining Linkage between Web Sites.” In 1st IEEE International Conference on Data Mining, 51–58. Institute of Electrical and Electronics Engineers, 2001. https://doi.org/10.1109/ICDM.2001.989500.
View | DOI
 
[35]
2001 | Journal Article | IST-REx-ID: 11755
Henzinger, Monika H. “Hyperlink Analysis for the Web.” IEEE Internet Computing. Institute of Electrical and Electronics Engineers, 2001. https://doi.org/10.1109/4236.895141.
View | DOI | WoS
 
[34]
2000 | Journal Article | IST-REx-ID: 11683
Henzinger, Monika H, Satish Rao, and Harold N. Gabow. “Computing Vertex Connectivity: New Bounds from Old Techniques.” Journal of Algorithms. Elsevier, 2000. https://doi.org/10.1006/jagm.1999.1055.
View | DOI
 
[33]
2000 | Journal Article | IST-REx-ID: 11685
Henzinger, Monika H, Allan Heydon, Michael Mitzenmacher, and Marc Najork. “On Near-Uniform URL Sampling.” Computer Networks. Elsevier, 2000. https://doi.org/10.1016/s1389-1286(00)00055-4.
View | DOI
 
[32]
2000 | Journal Article | IST-REx-ID: 11694
Albers, Susanne, and Monika H Henzinger. “Exploring Unknown Environments.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2000. https://doi.org/10.1137/s009753979732428x.
View | DOI
 
[31]
2000 | Journal Article | IST-REx-ID: 11770 | OA
Bharat, Krishna, Andrei Broder, Jeffrey Dean, and Monika H Henzinger. “A Comparison of Techniques to Find Mirrored Hosts on the WWW.” Journal of the American Society for Information Science. Wiley, 2000. https://doi.org/10.1002/1097-4571(2000)9999:9999<::aid-asi1025>3.0.co;2-0.
[Published Version] View | DOI | Download Published Version (ext.)
 
[30]
2000 | Conference Paper | IST-REx-ID: 11802
Henzinger, Monika H. “Web Information Retrieval - an Algorithmic Perspective.” In 8th Annual European Symposium on Algorithms, 1879:1–8. Springer Nature, 2000. https://doi.org/10.1007/3-540-45253-2_1.
View | DOI
 
[29]
2000 | Journal Article | IST-REx-ID: 11893
Henzinger, Monika H. “Improved Data Structures for Fully Dynamic Biconnectivity.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2000. https://doi.org/10.1137/s0097539794263907.
View | DOI
 
[28]
1999 | Conference Paper | IST-REx-ID: 11691
Goel, Ashish, Monika H Henzinger, Serge Plotkin, and Eva Tardos. “Scheduling Data Transfers in a Network and the Set Scheduling Problem.” In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 189–97. Association for Computing Machinery, 1999. https://doi.org/10.1145/301250.301300.
View | DOI
 
[27]
1999 | Journal Article | IST-REx-ID: 11687
Dean, Jeffrey, and Monika H Henzinger. “Finding Related Pages in the World Wide Web.” Computer Networks. Elsevier, 1999. https://doi.org/10.1016/s1389-1286(99)00022-5.
View | DOI
 
[26]
1999 | Journal Article | IST-REx-ID: 11688
Henzinger, Monika H, Allan Heydon, Michael Mitzenmacher, and Marc Najork. “Measuring Index Quality Using Random Walks on the Web.” Computer Networks. Elsevier, 1999. https://doi.org/10.1016/s1389-1286(99)00016-x.
View | DOI
 
[25]
1999 | Journal Article | IST-REx-ID: 11769
Henzinger, Monika H, and Valerie King. “Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation.” Journal of the ACM. Association for Computing Machinery, 1999. https://doi.org/10.1145/320211.320215.
View | DOI
 
[24]
1999 | Journal Article | IST-REx-ID: 11895 | OA
Silverstein, Craig, Hannes Marais, Monika H Henzinger, and Michael Moricz. “Analysis of a Very Large Web Search Engine Query Log.” ACM SIGIR Forum. Association for Computing Machinery, 1999. https://doi.org/10.1145/331403.331405.
[Published Version] View | DOI | Download Published Version (ext.)
 
[23]
1999 | Journal Article | IST-REx-ID: 11679
Henzinger, Monika H, V. King, and T. Warnow. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” Algorithmica. Springer Nature, 1999. https://doi.org/10.1007/pl00009268.
View | Files available | DOI
 
[22]
1999 | Conference Paper | IST-REx-ID: 11925
Henzinger, Monika H, and Stefano Leonardi  . “Scheduling Multicasts on Unit-Capacity Trees and Meshes.” In 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 438–47. Society for Industrial & Applied Mathematics, 1999.
View
 
[21]
1998 | Conference Paper | IST-REx-ID: 11682
Agarwal, P. K., D. EppsteinL. J. Guibas, and Monika H Henzinger. “Parametric and Kinetic Minimum Spanning Trees.” In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 596–605, 1998. https://doi.org/10.1109/SFCS.1998.743510.
View | DOI
 
[20]
1998 | Journal Article | IST-REx-ID: 11681
Henzinger, Monika H, and M. L. Fredman. “Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.” Algorithmica. Springer Nature, 1998. https://doi.org/10.1007/pl00009228.
View | DOI
 
[19]
1998 | Conference Paper | IST-REx-ID: 11926
Goel, Ashish, Monika H Henzinger, and Serge Plotkin. “An Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control.” In 9th Annual ACM SIAM Symposium on Discrete Algorithms, 97–106. Society for Industrial and Applied Mathematics, 1998.
View | Files available
 
[18]
1998 | Journal Article | IST-REx-ID: 11680
Alberts, D., and Monika H Henzinger. “Average-Case Analysis of Dynamic Graph Algorithms.” Algorithmica. Springer Nature, 1998. https://doi.org/10.1007/pl00009186.
View | Files available | DOI
 
[17]
1997 | Journal Article | IST-REx-ID: 11666
Anderson, Jennifer M., Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika H Henzinger, Shun-Tak A. Leung, Richard L. Sites, Mark T. Vandevoorde, Carl A. Waldspurger, and William E. Weihl. “Continuous Profiling: Where Have All the Cycles Gone?” ACM Transactions on Computer Systems. Association for Computing Machinery, 1997. https://doi.org/10.1145/265924.265925.
View | DOI
 
[16]
1997 | Journal Article | IST-REx-ID: 11767 | OA
Henzinger, Monika H, Philip Klein, Satish Rao, and Sairam Subramanian. “Faster Shortest-Path Algorithms for Planar Graphs.” Journal of Computer and System Sciences. Elsevier, 1997. https://doi.org/10.1006/jcss.1997.1493.
[Published Version] View | DOI | Download Published Version (ext.)
 
[15]
1997 | Journal Article | IST-REx-ID: 11765
Henzinger, Monika H. “A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity.” Journal of Algorithms. Elsevier, 1997. https://doi.org/10.1006/jagm.1997.0855.
View | DOI
 
[14]
1997 | Conference Paper | IST-REx-ID: 11803
Henzinger, Monika H, and Valerie King. “Maintaining Minimum Spanning Trees in Dynamic Graphs.” In 24th International Colloquium on Automata, Languages and Programming, 1256:594–604. Springer Nature, 1997. https://doi.org/10.1007/3-540-63165-8_214.
View | DOI
 
[13]
1997 | Journal Article | IST-REx-ID: 11849 | OA
Anderson, Jennifer M., Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika H Henzinger, Shun-Tak A. Leung, Richard L. Sites, Mark T. Vandevoorde, Carl A. Waldspurger, and William E. Weihl. “Continuous Profiling: Where Have All the Cycles Gone?” ACM SIGOPS Operating Systems Review. Association for Computing Machinery, 1997. https://doi.org/10.1145/269005.266637.
[Published Version] View | Files available | DOI | Download Published Version (ext.)
 
[12]
1997 | Journal Article | IST-REx-ID: 11883
Henzinger, Monika H, and Mikkel Thorup. “Sampling to Provide or to Bound: With Applications to Fully Dynamic Graph Algorithms.” Random Structures and Algorithms. Wiley, 1997. https://doi.org/10.1002/(sici)1098-2418(199712)11:4<369::aid-rsa5>3.0.co;2-x.
View | DOI
 
[11]
1996 | Journal Article | IST-REx-ID: 11761
Henzinger, Monika H, and David P. Williamson. “On the Number of Small Cuts in a Graph.” Information Processing Letters. Elsevier, 1996. https://doi.org/10.1016/0020-0190(96)00079-8.
View | DOI
 
[10]
1996 | Conference Paper | IST-REx-ID: 11804
Henzinger, Monika H, and Jan Arne Telle. “Faster Algorithms for the Nonemptiness of Streett Automata and for Communication Protocol Pruning.” In 5th Scandinavian Workshop on Algorithm Theory, 1097:16–27. Springer Nature, 1996. https://doi.org/10.1007/3-540-61422-2_117.
View | DOI
 
[9]
1996 | Conference Paper | IST-REx-ID: 11910
Henzinger, Monika H, and Mikkel Thorup. “Improved Sampling with Applications to Dynamic Graph Algorithms.” In 23rd International Colloquium on Automata, Languages, and Programming, 1099:290–99. Springer Nature, 1996. https://doi.org/10.1007/3-540-61440-0_136.
View | DOI
 
[8]
1996 | Conference Paper | IST-REx-ID: 11927 | OA
Henzinger, Monika H, Valerie King, and Tandy Warnow. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” In 7th Annual ACM-SIAM Symposium on Discrete Algorithms, 333–40. Society for Industrial and Applied Mathematics, 1996.
[Published Version] View | Files available | Download Published Version (ext.)
 
[7]
1995 | Journal Article | IST-REx-ID: 11677
Henzinger, Monika H. “Fully Dynamic Biconnectivity in Graphs.” Algorithmica. Springer Nature, 1995. https://doi.org/10.1007/bf01189067.
View | DOI
 
[6]
1995 | Conference Paper | IST-REx-ID: 11684
Henzinger, Monika H, and V. King. “Fully Dynamic Biconnectivity and Transitive Closure.” In Proceedings of IEEE 36th Annual Foundations of Computer Science, 664–72. Institute of Electrical and Electronics Engineers, 1995. https://doi.org/10.1109/SFCS.1995.492668.
View | DOI
 
[5]
1995 | Conference Paper | IST-REx-ID: 11806
Henzinger, Monika H. “Approximating Minimum Cuts under Insertions.” In 22nd International Colloquium on Automata, Languages and Programming, 944:280–291. Springer Nature, 1995. https://doi.org/10.1007/3-540-60084-1_81.
View | DOI
 
[4]
1995 | Conference Paper | IST-REx-ID: 11805
Henzinger, Monika H, and Han Poutré. “Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs.” In 3rd Annual European Symposium on Algorithms, 979:171–184. Springer Nature, 1995. https://doi.org/10.1007/3-540-60313-1_142.
View | DOI
 
[3]
1995 | Conference Paper | IST-REx-ID: 11928 | OA
Alberts, David, and Monika H Henzinger. “Average Case Analysis of Dynamic Graph Algorithms.” In 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 312–21. Society for Industrial and Applied Mathematics, 1995.
[Published Version] View | Files available | Download Published Version (ext.)
 
[2]
1995 | Conference Paper | IST-REx-ID: 4498
Henzinger, Monika H, Thomas A Henzinger, and Peter Kopke. “Computing Simulations on Finite and Infinite Graphs.” In Proceedings of IEEE 36th Annual Foundations of Computer Science, 453–62. IEEE, 1995. https://doi.org/10.1109/SFCS.1995.492576.
View | DOI
 
[1]
1994 | Conference Paper | IST-REx-ID: 11857
Henzinger, Monika H. “Fully Dynamic Cycle-Equivalence in Graphs.” In 35th Annual Symposium on Foundations of Computer Science, 744–55. Institute of Electrical and Electronics Engineers, 1994. https://doi.org/10.1109/sfcs.1994.365718.
View | DOI
 
Marked Publication(s)

Search

Filter Publications

    • Display / Sort

    Citation Style: Chicago

    Export / Embed