Monika Henzinger

Henzinger_Monika Group

199 Publications

Mark all

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

Search

Filter Publications

    • Display / Sort

    Citation Style: Default

    Export / Embed

199 Publications

Mark all

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

Search

Filter Publications

    • Display / Sort

    Citation Style: Default

    Export / Embed