Static and Dynamic Hierarchical Graph Decompositions

Project Period: 2023-03-01 – 2026-02-28
Funder: Austrian Science Fund
Principal Investigator
Department(s)
Henzinger_Monika Group
Grant Number
I05982
Grant DOI
10.55776/I5982
Funder
Austrian Science Fund
Funder Schema
FWF-IP-JP-DFG
Funder Registry
10.13039/501100002428

33 Publications

2026 | Published | Conference Paper | IST-REx-ID: 22004 | OA
Charting the diameter computation landscape of intersection graphs in 3D and above
T.M. Chan, H.C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
[Published Version] View | Files available | DOI | arXiv
 
2026 | Published | Conference Paper | IST-REx-ID: 21719 | OA
Dynamic hierarchical j-tree decomposition and its applications
G. Goranci, M. Henzinger, P. Kiss, A. Momeni, G. Zöcklein, in:, Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2026, pp. 1128–1180.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
2026 | Published | Conference Paper | IST-REx-ID: 22245 | OA
An improved quality hierarchical congestion approximator in near-linear time
M. Henzinger, R. Münk, H. Räcke, in:, 58th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2026, pp. 1417–1428.
[Published Version] View | Files available | DOI | arXiv
 
2026 | Published | Journal Article | IST-REx-ID: 22318 | OA | PlanS
Concurrent composition for differentially private continual mechanisms
M. Henzinger, R. Safavi Hemami, S. Vadhan, Proceedings of the ACM on Management of Data 4 (2026) 1–26.
[Published Version] View | Files available | DOI | arXiv
 
2026 | Published | Conference Paper | IST-REx-ID: 22327 | OA
Ranking opinions with few states in population protocols
T.-L. Breitkopf, J. Dallot, A. El-Hayek, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2026, pp. 414–424.
[Published Version] View | Files available | DOI | arXiv
 
2026 | Published | Thesis | PhD | IST-REx-ID: 22281 | OA
Handling updates and failures: Dynamic graph algorithms and distributed computing on dynamic networks
A. El-Hayek, Handling Updates and Failures: Dynamic Graph Algorithms and Distributed Computing on Dynamic Networks, Institute of Science and Technology Austria, 2026.
[Published Version] View | Files available | DOI
 
2026 | Published | Conference Paper | IST-REx-ID: 21720 | OA
Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time
A. El-Hayek, M. Henzinger, J. Li, in:, Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2026, pp. 613–663.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
2026 | Published | Conference Paper | IST-REx-ID: 22405 | OA
Charting the landscape of diameter computation on geometric intersection graphs in the plane
T.M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, in:, 53rd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026.
[Published Version] View | Files available | DOI | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 21280 | OA
Incremental approximate maximum flow via residual graph sparsification
G. Goranci, M. Henzinger, H. Räcke, A. Sricharan, in:, 52nd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 91:1-91:20.
[Published Version] View | Files available | DOI | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 19038 | OA
Improved differentially private continual observation using group algebra
M. Henzinger, J. Upadhyay, in:, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, 2025, pp. 2951–2970.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 19858 | OA
On b-matching and fully-dynamic maximum k-edge coloring
A. El-Hayek, K. Hanauer, M. Henzinger, in:, 4th Symposium on Algorithmic Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
[Published Version] View | Files available | DOI | WoS | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 20052 | OA
Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols
T.-L. Breitkopf, J. Dallot, A. El-Hayek, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025, pp. 549–552.
[Published Version] View | Files available | DOI | WoS
 
2025 | Published | Conference Paper | IST-REx-ID: 20301 | OA
Differentially private continual release of histograms and related queries
M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, The 28th International Conference on Artificial Intelligence and Statistics, ML Research Press, 2025, pp. 1990–1998.
[Preprint] View | Download Preprint (ext.) | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 20534 | OA
Efficient contractions of dynamic graphs - with applications
M. Henzinger, E. Kosinas, R. Münk, H. Räcke, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
[Published Version] View | Files available | DOI | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 20535 | OA
Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism
L. Dhulipala, M. Henzinger, G.Z. Li, Q.C. Liu, A.R. Sricharan, L. Zhu, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
[Published Version] View | Files available | DOI | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 20051 | OA
An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model
A. El-Hayek, R. Elsässer, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025.
[Published Version] View | Files available | DOI | WoS | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 19982 | OA
Fully dynamic approximate minimum cut in subpolynomial time per operation
A. El-Hayek, M. Henzinger, J. Li, in:, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2025, pp. 750–784.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
2024 | Published | Conference Paper | IST-REx-ID: 14769 | OA
Experimental evaluation of fully dynamic k-means via coresets
M. Henzinger, D. Saulpic, L. Sidl, in:, 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2024, pp. 220–233.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
2024 | Published | Conference Paper | IST-REx-ID: 15008 | OA
Electrical flows for polylogarithmic competitive oblivious routing
G. Goranci, M. 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 | WoS | arXiv
 
2024 | Published | Conference Paper | IST-REx-ID: 15253 | OA
A unifying framework for differentially private sums under continual observation
M. 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
 

Search

Filter Publications

Display / Sort

Citation Style: APA

Export / Embed