default search action
BibTeX records: Monika Henzinger
@article{DBLP:journals/mp/ZhengH25,
author = {Da Wei Zheng and
Monika Henzinger},
title = {Multiplicative auction algorithm for approximate maximum weight bipartite
matching},
journal = {Math. Program.},
volume = {210},
number = {1},
pages = {881--894},
year = {2025}
}
@inproceedings{DBLP:conf/aistats/HenzingerSS25,
author = {Monika Henzinger and
A. R. Sricharan and
Teresa Anna Steiner},
title = {Differentially Private Continual Release of Histograms and Related
Queries},
booktitle = {{AISTATS}},
series = {Proceedings of Machine Learning Research},
volume = {258},
pages = {1990--1998},
publisher = {{PMLR}},
year = {2025}
}
@inproceedings{DBLP:conf/esa/HenzingerS25,
author = {Monika Henzinger and
Roodabeh Safavi},
title = {Securing Dynamic Data: {A} Primer on Differentially Private Data Structures
(Invited Talk)},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {351},
pages = {2:1--2:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2025}
}
@inproceedings{DBLP:conf/esa/HenzingerKMR25,
author = {Monika Henzinger and
Evangelos Kosinas and
Robin M{\"{u}}nk and
Harald R{\"{a}}cke},
title = {Efficient Contractions of Dynamic Graphs - With Applications},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {351},
pages = {36:1--36:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2025}
}
@inproceedings{DBLP:conf/esa/DhulipalaHLLSZ25,
author = {Laxman Dhulipala and
Monika Henzinger and
George Z. Li and
Quanquan C. Liu and
A. R. Sricharan and
Leqi Zhu},
title = {Near-Optimal Differentially Private Graph Algorithms via the Multidimensional
AboveThreshold Mechanism},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {351},
pages = {91:1--91:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2025}
}
@inproceedings{DBLP:conf/icalp/GoranciHRS25,
author = {Gramoz Goranci and
Monika Henzinger and
Harald R{\"{a}}cke and
A. R. Sricharan},
title = {Incremental Approximate Maximum Flow via Residual Graph Sparsification},
booktitle = {{ICALP}},
series = {LIPIcs},
volume = {334},
pages = {91:1--91:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2025}
}
@inproceedings{DBLP:conf/sand/El-HayekHH25,
author = {Antoine El{-}Hayek and
Kathrin Hanauer and
Monika Henzinger},
title = {On b-Matching and Fully-Dynamic Maximum k-Edge Coloring},
booktitle = {{SAND}},
series = {LIPIcs},
volume = {330},
pages = {4:1--4:23},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2025}
}
@inproceedings{DBLP:conf/soda/El-HayekH025,
author = {Antoine El{-}Hayek and
Monika Henzinger and
Jason Li},
title = {Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation},
booktitle = {{SODA}},
pages = {750--784},
publisher = {{SIAM}},
year = {2025}
}
@inproceedings{DBLP:conf/soda/HenzingerU25,
author = {Monika Henzinger and
Jalaj Upadhyay},
title = {Improved Differentially Private Continual Observation Using Group
Algebra},
booktitle = {{SODA}},
pages = {2951--2970},
publisher = {{SIAM}},
year = {2025}
}
@article{DBLP:journals/corr/abs-2502-09105,
author = {Gramoz Goranci and
Monika Henzinger and
Harald R{\"{a}}cke and
A. R. Sricharan},
title = {Incremental Approximate Maximum Flow via Residual Graph Sparsification},
journal = {CoRR},
volume = {abs/2502.09105},
year = {2025}
}
@article{DBLP:journals/corr/abs-2504-04398,
author = {Monika Henzinger and
Nikita P. Kalinin and
Jalaj Upadhyay},
title = {Binned Group Algebra Factorization for Differentially Private Continual
Counting},
journal = {CoRR},
volume = {abs/2504.04398},
year = {2025}
}
@article{DBLP:journals/corr/abs-2506-08201,
author = {Krishna Pillutla and
Jalaj Upadhyay and
Christopher A. Choquette{-}Choo and
Krishnamurthy Dvijotham and
Arun Ganesh and
Monika Henzinger and
Jonathan Katz and
Ryan McKenna and
H. Brendan McMahan and
Keith Rush and
Thomas Steinke and
Abhradeep Thakurta},
title = {Correlated Noise Mechanisms for Differentially Private Learning},
journal = {CoRR},
volume = {abs/2506.08201},
year = {2025}
}
@article{DBLP:journals/corr/abs-2508-02182,
author = {Laxman Dhulipala and
Monika Henzinger and
George Z. Li and
Quanquan C. Liu and
A. R. Sricharan and
Leqi Zhu},
title = {Near-Optimal Differentially Private Graph Algorithms via the Multidimensional
AboveThreshold Mechanism},
journal = {CoRR},
volume = {abs/2508.02182},
year = {2025}
}
@article{DBLP:journals/corr/abs-2509-05157,
author = {Monika Henzinger and
Evangelos Kosinas and
Robin M{\"{u}}nk and
Harald R{\"{a}}cke},
title = {Efficient Contractions of Dynamic Graphs - with Applications},
journal = {CoRR},
volume = {abs/2509.05157},
year = {2025}
}
@article{DBLP:journals/corr/abs-2509-14334,
author = {Monika Henzinger and
Nikita P. Kalinin and
Jalaj Upadhyay},
title = {Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially
Private Continual Counting},
journal = {CoRR},
volume = {abs/2509.14334},
year = {2025}
}
@inproceedings{DBLP:conf/alenex/HenzingerSS24,
author = {Monika Henzinger and
David Saulpic and
Leonhard Sidl},
title = {Experimental Evaluation of Fully Dynamic \emph{k}-Means via Coresets},
booktitle = {{ALENEX}},
pages = {220--233},
publisher = {{SIAM}},
year = {2024}
}
@inproceedings{DBLP:conf/approx/HenzingerSS24,
author = {Monika Henzinger and
A. R. Sricharan and
Teresa Anna Steiner},
title = {Private Counting of Distinct Elements in the Turnstile Model and Extensions},
booktitle = {{APPROX/RANDOM}},
series = {LIPIcs},
volume = {317},
pages = {40:1--40:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2024}
}
@inproceedings{DBLP:conf/esa/TourHS24,
author = {Max Dupr{\'{e}} la Tour and
Monika Henzinger and
David Saulpic},
title = {Fully Dynamic k-Means Coreset in Near-Optimal Update Time},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {308},
pages = {100:1--100:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2024}
}
@inproceedings{DBLP:conf/gd/Henzinger24,
author = {Monika Henzinger},
title = {How Can Algorithms Help in Protecting Our Privacy (Invited Talk)},
booktitle = {{GD}},
series = {LIPIcs},
volume = {320},
pages = {2:1--2:1},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2024}
}
@inproceedings{DBLP:conf/icml/AxiotisCHJMSWW24,
author = {Kyriakos Axiotis and
Vincent Cohen{-}Addad and
Monika Henzinger and
Sammy Jerome and
Vahab Mirrokni and
David Saulpic and
David P. Woodruff and
Michael Wunder},
title = {Data-Efficient Learning via Clustering-Based Sensitivity Sampling:
Foundation Models and Beyond},
booktitle = {{ICML}},
publisher = {OpenReview.net},
year = {2024}
}
@inproceedings{DBLP:conf/icml/TourHS24,
author = {Max Dupr{\'{e}} la Tour and
Monika Henzinger and
David Saulpic},
title = {Making Old Things New: {A} Unified Algorithm for Differentially Private
Clustering},
booktitle = {{ICML}},
publisher = {OpenReview.net},
year = {2024}
}
@inproceedings{DBLP:conf/innovations/GoranciHRSS24,
author = {Gramoz Goranci and
Monika Henzinger and
Harald R{\"{a}}cke and
Sushant Sachdeva and
A. R. Sricharan},
title = {Electrical Flows for Polylogarithmic Competitive Oblivious Routing},
booktitle = {{ITCS}},
series = {LIPIcs},
volume = {287},
pages = {55:1--55:22},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2024}
}
@inproceedings{DBLP:conf/innovations/HenzingerSSY24,
author = {Monika Henzinger and
Barna Saha and
Martin P. Seybold and
Christopher Ye},
title = {On the Complexity of Algorithms with Predictions for Dynamic Graph
Problems},
booktitle = {{ITCS}},
series = {LIPIcs},
volume = {287},
pages = {62:1--62:25},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2024}
}
@inproceedings{DBLP:conf/kdd/HanauerHMRV24,
author = {Kathrin Hanauer and
Monika Henzinger and
Robin M{\"{u}}nk and
Harald R{\"{a}}cke and
Maximilian V{\"{o}}tsch},
title = {Expander Hierarchies for Normalized Cuts on Graphs},
booktitle = {{KDD}},
pages = {1016--1027},
publisher = {{ACM}},
year = {2024}
}
@inproceedings{DBLP:conf/nips/AnderssonHPSU24,
author = {Joel Daniel Andersson and
Monika Henzinger and
Rasmus Pagh and
Teresa Anna Steiner and
Jalaj Upadhyay},
title = {Continual Counting with Gradual Privacy Expiration},
booktitle = {NeurIPS},
year = {2024}
}
@inproceedings{DBLP:conf/soda/MontesanoEHO24,
author = {Sebastiano Cultrera di Montesano and
Herbert Edelsbrunner and
Monika Henzinger and
Lara Ost},
title = {Dynamically Maintaining the Persistent Homology of Time Series},
booktitle = {{SODA}},
pages = {243--295},
publisher = {{SIAM}},
year = {2024}
}
@inproceedings{DBLP:conf/soda/HenzingerUU24,
author = {Monika Henzinger and
Jalaj Upadhyay and
Sarvagya Upadhyay},
title = {A Unifying Framework for Differentially Private Sums under Continual
Observation},
booktitle = {{SODA}},
pages = {995--1018},
publisher = {{SIAM}},
year = {2024}
}
@inproceedings{DBLP:conf/soda/HenzingerLRW24,
author = {Monika Henzinger and
Jason Li and
Satish Rao and
Di Wang},
title = {Deterministic Near-Linear Time Minimum Cut in Weighted Graphs},
booktitle = {{SODA}},
pages = {3089--3139},
publisher = {{SIAM}},
year = {2024}
}
@inproceedings{DBLP:conf/wdag/El-HayekH024,
author = {Antoine El{-}Hayek and
Monika Henzinger and
Stefan Schmid},
title = {Broadcast and Consensus in Stochastic Dynamic Networks with Byzantine
Nodes and Adversarial Edges},
booktitle = {{DISC}},
series = {LIPIcs},
volume = {319},
pages = {21:1--21:15},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2024}
}
@misc{DBLP:data/11/HanauerHMRV24,
author = {Kathrin Hanauer and
Monika Henzinger and
Robin M{\"{u}}nk and
Harald R{\"{a}}cke and
Maximilian V{\"{o}}tsch},
title = {XCut/XCut v1.0.0 (Version 1.0.0)},
publisher = {Zenodo},
year = {2024},
month = jun,
howpublished = {\url{https://doi.org/10.5281/zenodo.12108189}},
note = {Accessed on YYYY-MM-DD.}
}
@article{DBLP:journals/corr/abs-2401-05627,
author = {Monika Henzinger and
Jason Li and
Satish Rao and
Di Wang},
title = {Deterministic Near-Linear Time Minimum Cut in Weighted Graphs},
journal = {CoRR},
volume = {abs/2401.05627},
year = {2024}
}
@article{DBLP:journals/corr/abs-2402-17327,
author = {Kyriakos Axiotis and
Vincent Cohen{-}Addad and
Monika Henzinger and
Sammy Jerome and
Vahab Mirrokni and
David Saulpic and
David P. Woodruff and
Michael Wunder},
title = {Data-Efficient Learning via Clustering-Based Sensitivity Sampling:
Foundation Models and Beyond},
journal = {CoRR},
volume = {abs/2402.17327},
year = {2024}
}
@article{DBLP:journals/corr/abs-2402-18020,
author = {Monika Henzinger and
A. R. Sricharan and
Leqi Zhu},
title = {Tighter Bounds for Local Differentially Private Core Decomposition
and Densest Subgraph},
journal = {CoRR},
volume = {abs/2402.18020},
year = {2024}
}
@article{DBLP:journals/corr/abs-2406-03802,
author = {Joel Daniel Andersson and
Monika Henzinger and
Rasmus Pagh and
Teresa Anna Steiner and
Jalaj Upadhyay},
title = {Continual Counting with Gradual Privacy Expiration},
journal = {CoRR},
volume = {abs/2406.03802},
year = {2024}
}
@article{DBLP:journals/corr/abs-2406-11649,
author = {Max Dupr{\'{e}} la Tour and
Monika Henzinger and
David Saulpic},
title = {Making Old Things New: {A} Unified Algorithm for Differentially Private
Clustering},
journal = {CoRR},
volume = {abs/2406.11649},
year = {2024}
}
@article{DBLP:journals/corr/abs-2406-14111,
author = {Kathrin Hanauer and
Monika Henzinger and
Robin M{\"{u}}nk and
Harald R{\"{a}}cke and
Maximilian V{\"{o}}tsch},
title = {Expander Hierarchies for Normalized Cuts on Graphs},
journal = {CoRR},
volume = {abs/2406.14111},
year = {2024}
}
@article{DBLP:journals/corr/abs-2406-19926,
author = {Max Dupr{\'{e}} la Tour and
Monika Henzinger and
David Saulpic},
title = {Fully Dynamic k-Means Coreset in Near-Optimal Update Time},
journal = {CoRR},
volume = {abs/2406.19926},
year = {2024}
}
@article{DBLP:journals/corr/abs-2408-11637,
author = {Monika Henzinger and
A. R. Sricharan and
Teresa Anna Steiner},
title = {Private Counting of Distinct Elements in the Turnstile Model and Extensions},
journal = {CoRR},
volume = {abs/2408.11637},
year = {2024}
}
@article{DBLP:journals/corr/abs-2411-03299,
author = {Monika Henzinger and
Roodabeh Safavi and
Salil P. Vadhan},
title = {Concurrent Composition for Continual Mechanisms},
journal = {CoRR},
volume = {abs/2411.03299},
year = {2024}
}
@article{DBLP:journals/corr/abs-2412-02840,
author = {Monika Henzinger and
Jalaj Upadhyay},
title = {Improved Differentially Private Continual Observation Using Group
Algebra},
journal = {CoRR},
volume = {abs/2412.02840},
year = {2024}
}
@article{DBLP:journals/corr/abs-2412-15069,
author = {Antoine El{-}Hayek and
Monika Henzinger and
Jason Li},
title = {Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation},
journal = {CoRR},
volume = {abs/2412.15069},
year = {2024}
}
@article{DBLP:journals/algorithmica/HenzingerJPW23,
author = {Monika Henzinger and
Billy Jin and
Richard Peng and
David P. Williamson},
title = {A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear
Systems},
journal = {Algorithmica},
volume = {85},
number = {12},
pages = {3680--3716},
year = {2023}
}
@article{DBLP:journals/siamcomp/BhattacharyaHNW23,
author = {Sayan Bhattacharya and
Monika Henzinger and
Danupon Nanongkai and
Xiaowei Wu},
title = {Deterministic Near-Optimal Approximation Algorithms for Dynamic Set
Cover},
journal = {{SIAM} J. Comput.},
volume = {52},
number = {5},
pages = {1132--1192},
year = {2023}
}
@inproceedings{DBLP:conf/icalp/GoranciH23,
author = {Gramoz Goranci and
Monika Henzinger},
title = {Efficient Data Structures for Incremental Exact and Approximate Maximum
Flow},
booktitle = {{ICALP}},
series = {LIPIcs},
volume = {261},
pages = {69:1--69:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023}
}
@inproceedings{DBLP:conf/icalp/HenzingerLVZ23,
author = {Monika Henzinger and
Paul Liu and
Jan Vondr{\'{a}}k and
Da Wei Zheng},
title = {Faster Submodular Maximization for Several Classes of Matroids},
booktitle = {{ICALP}},
series = {LIPIcs},
volume = {261},
pages = {74:1--74:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023}
}
@inproceedings{DBLP:conf/icml/FichtenbergerHU23,
author = {Hendrik Fichtenberger and
Monika Henzinger and
Jalaj Upadhyay},
title = {Constant Matters: Fine-grained Error Bound on Differentially Private
Continual Observation},
booktitle = {{ICML}},
series = {Proceedings of Machine Learning Research},
volume = {202},
pages = {10072--10092},
publisher = {{PMLR}},
year = {2023}
}
@inproceedings{DBLP:conf/infocom/HanauerHOS23,
author = {Kathrin Hanauer and
Monika Henzinger and
Lara Ost and
Stefan Schmid},
title = {Dynamic Demand-Aware Link Scheduling for Reconfigurable Datacenters},
booktitle = {{INFOCOM}},
pages = {1--10},
publisher = {{IEEE}},
year = {2023}
}
@inproceedings{DBLP:conf/innovations/El-HayekH023,
author = {Antoine El{-}Hayek and
Monika Henzinger and
Stefan Schmid},
title = {Asymptotically Tight Bounds on the Time Complexity of Broadcast and
Its Variants in Dynamic Networks},
booktitle = {{ITCS}},
series = {LIPIcs},
volume = {251},
pages = {47:1--47:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023}
}
@inproceedings{DBLP:conf/innovations/HenzingerJPW23,
author = {Monika Henzinger and
Billy Jin and
Richard Peng and
David P. Williamson},
title = {A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear
Systems},
booktitle = {{ITCS}},
series = {LIPIcs},
volume = {251},
pages = {69:1--69:22},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023}
}
@inproceedings{DBLP:conf/ipco/ZhengH23,
author = {Da Wei Zheng and
Monika Henzinger},
title = {Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite
Matching},
booktitle = {{IPCO}},
series = {Lecture Notes in Computer Science},
volume = {13904},
pages = {453--465},
publisher = {Springer},
year = {2023}
}
@inproceedings{DBLP:conf/nips/CharikarHHVW23,
author = {Moses Charikar and
Monika Henzinger and
Lunjia Hu and
Maximilian V{\"{o}}tsch and
Erik Waingarten},
title = {Simple, Scalable and Effective Clustering via One-Dimensional Projections},
booktitle = {NeurIPS},
year = {2023}
}
@inproceedings{DBLP:conf/soda/GoranciHNSTW23,
author = {Gramoz Goranci and
Monika Henzinger and
Danupon Nanongkai and
Thatchaphol Saranurak and
Mikkel Thorup and
Christian Wulff{-}Nilsen},
title = {Fully Dynamic Exact Edge Connectivity in Sublinear Time},
booktitle = {{SODA}},
pages = {70--86},
publisher = {{SIAM}},
year = {2023}
}
@inproceedings{DBLP:conf/soda/ChiplunkarHKV23,
author = {Ashish Chiplunkar and
Monika Henzinger and
Sagar Sudhir Kale and
Maximilian V{\"{o}}tsch},
title = {Online Min-Max Paging},
booktitle = {{SODA}},
pages = {1545--1565},
publisher = {{SIAM}},
year = {2023}
}
@inproceedings{DBLP:conf/soda/BateniEFHJMW23,
author = {MohammadHossein Bateni and
Hossein Esfandiari and
Hendrik Fichtenberger and
Monika Henzinger and
Rajesh Jayaram and
Vahab Mirrokni and
Andreas Wiese},
title = {Optimal Fully Dynamic \emph{k}-Center Clustering for Adaptive and
Oblivious Adversaries},
booktitle = {{SODA}},
pages = {2677--2727},
publisher = {{SIAM}},
year = {2023}
}
@inproceedings{DBLP:conf/soda/HenzingerUU23,
author = {Monika Henzinger and
Jalaj Upadhyay and
Sarvagya Upadhyay},
title = {Almost Tight Error Bounds on Differentially Private Continual Counting},
booktitle = {{SODA}},
pages = {5003--5039},
publisher = {{SIAM}},
year = {2023}
}
@inproceedings{DBLP:conf/stacs/Henzinger0R023,
author = {Monika Henzinger and
Stefan Neumann and
Harald R{\"{a}}cke and
Stefan Schmid},
title = {Dynamic Maintenance of Monotone Dynamic Programs and Applications},
booktitle = {{STACS}},
series = {LIPIcs},
volume = {254},
pages = {36:1--36:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023}
}
@article{DBLP:journals/corr/abs-2301-01744,
author = {Monika Henzinger and
Stefan Neumann and
Harald R{\"{a}}cke and
Stefan Schmid},
title = {Dynamic Maintenance of Monotone Dynamic Programs and Applications},
journal = {CoRR},
volume = {abs/2301.01744},
year = {2023}
}
@article{DBLP:journals/corr/abs-2301-05751,
author = {Kathrin Hanauer and
Monika Henzinger and
Lara Ost and
Stefan Schmid},
title = {Dynamic Demand-Aware Link Scheduling for Reconfigurable Datacenters},
journal = {CoRR},
volume = {abs/2301.05751},
year = {2023}
}
@article{DBLP:journals/corr/abs-2301-09217,
author = {Da Wei Zheng and
Monika Henzinger},
title = {Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite
Matching},
journal = {CoRR},
volume = {abs/2301.09217},
year = {2023}
}
@article{DBLP:journals/corr/abs-2302-05951,
author = {Gramoz Goranci and
Monika Henzinger and
Danupon Nanongkai and
Thatchaphol Saranurak and
Mikkel Thorup and
Christian Wulff{-}Nilsen},
title = {Fully Dynamic Exact Edge Connectivity in Sublinear Time},
journal = {CoRR},
volume = {abs/2302.05951},
year = {2023}
}
@article{DBLP:journals/corr/abs-2302-11341,
author = {Monika Henzinger and
A. R. Sricharan and
Teresa Anna Steiner},
title = {Differentially Private Data Structures under Continual Observation
for Histograms and Related Queries},
journal = {CoRR},
volume = {abs/2302.11341},
year = {2023}
}
@article{DBLP:journals/corr/abs-2302-11988,
author = {Antoine El{-}Hayek and
Monika Henzinger and
Stefan Schmid},
title = {Time Complexity of Broadcast and Consensus for Randomized Oblivious
Message Adversaries},
journal = {CoRR},
volume = {abs/2302.11988},
year = {2023}
}
@article{DBLP:journals/corr/abs-2303-02491,
author = {Gramoz Goranci and
Monika Henzinger and
Harald R{\"{a}}cke and
Sushant Sachdeva and
A. R. Sricharan},
title = {Electrical Flows for Polylogarithmic Competitive Oblivious Routing},
journal = {CoRR},
volume = {abs/2303.02491},
year = {2023}
}
@article{DBLP:journals/corr/abs-2303-11843,
author = {MohammadHossein Bateni and
Hossein Esfandiari and
Hendrik Fichtenberger and
Monika Henzinger and
Rajesh Jayaram and
Vahab Mirrokni and
Andreas Wiese},
title = {Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious
Adversaries},
journal = {CoRR},
volume = {abs/2303.11843},
year = {2023}
}
@article{DBLP:journals/corr/abs-2305-00122,
author = {Monika Henzinger and
Paul Liu and
Jan Vondr{\'{a}}k and
Da Wei Zheng},
title = {Faster Submodular Maximization for Several Classes of Matroids},
journal = {CoRR},
volume = {abs/2305.00122},
year = {2023}
}
@article{DBLP:journals/corr/abs-2306-10428,
author = {Monika Henzinger and
A. R. Sricharan and
Teresa Anna Steiner},
title = {Differentially Private Histogram, Predecessor, and Set Cardinality
under Continual Observation},
journal = {CoRR},
volume = {abs/2306.10428},
year = {2023}
}
@article{DBLP:journals/corr/abs-2307-03430,
author = {Max Dupr{\'{e}} la Tour and
Monika Henzinger and
David Saulpic},
title = {Differential Privacy for Clustering Under Continual Observation},
journal = {CoRR},
volume = {abs/2307.03430},
year = {2023}
}
@article{DBLP:journals/corr/abs-2307-08970,
author = {Monika Henzinger and
Jalaj Upadhyay and
Sarvagya Upadhyay},
title = {A Unifying Framework for Differentially Private Sums under Continual
Observation},
journal = {CoRR},
volume = {abs/2307.08970},
year = {2023}
}
@article{DBLP:journals/corr/abs-2307-16771,
author = {Monika Henzinger and
Andrea Lincoln and
Barna Saha and
Martin P. Seybold and
Christopher Ye},
title = {On the Complexity of Algorithms with Predictions for Dynamic Graph
Problems},
journal = {CoRR},
volume = {abs/2307.16771},
year = {2023}
}
@article{DBLP:journals/corr/abs-2310-01149,
author = {Antoine El{-}Hayek and
Kathrin Hanauer and
Monika Henzinger},
title = {On b-Matching and Fully-Dynamic Maximum k-Edge Coloring},
journal = {CoRR},
volume = {abs/2310.01149},
year = {2023}
}
@article{DBLP:journals/corr/abs-2310-16752,
author = {Moses Charikar and
Monika Henzinger and
Lunjia Hu and
Maximilian V{\"{o}}tsch and
Erik Waingarten},
title = {Simple, Scalable and Effective Clustering via One-Dimensional Projections},
journal = {CoRR},
volume = {abs/2310.16752},
year = {2023}
}
@article{DBLP:journals/corr/abs-2310-18034,
author = {Monika Henzinger and
David Saulpic and
Leonhard Sidl},
title = {Experimental Evaluation of Fully Dynamic k-Means via Coresets},
journal = {CoRR},
volume = {abs/2310.18034},
year = {2023}
}
@article{DBLP:journals/corr/abs-2311-01115,
author = {Sebastiano Cultrera di Montesano and
Herbert Edelsbrunner and
Monika Henzinger and
Lara Ost},
title = {Dynamically Maintaining the Persistent Homology of Time Series},
journal = {CoRR},
volume = {abs/2311.01115},
year = {2023}
}
@article{DBLP:journals/jea/HanauerHS22,
author = {Kathrin Hanauer and
Monika Henzinger and
Christian Schulz},
title = {Recent Advances in Fully Dynamic Graph Algorithms - {A} Quick Reference
Guide},
journal = {{ACM} J. Exp. Algorithmics},
volume = {27},
pages = {1.11:1--1.11:45},
year = {2022}
}
@article{DBLP:journals/talg/HenzingerP22,
author = {Monika Henzinger and
Pan Peng},
title = {Constant-time Dynamic ({\(\Delta\)} +1)-Coloring},
journal = {{ACM} Trans. Algorithms},
volume = {18},
number = {2},
pages = {16:1--16:21},
year = {2022}
}
@inproceedings{DBLP:conf/alenex/HenzingerN022,
author = {Monika Henzinger and
Alexander Noe and
Christian Schulz},
title = {Practical Fully Dynamic Minimum Cut Algorithms},
booktitle = {{ALENEX}},
pages = {13--26},
publisher = {{SIAM}},
year = {2022}
}
@inproceedings{DBLP:conf/birthday/Henzinger22,
author = {Monika Henzinger},
title = {Fine-Grained Complexity Lower Bounds for Problems in Computer Aided
Verification},
booktitle = {Principles of Systems Design},
series = {Lecture Notes in Computer Science},
volume = {13660},
pages = {292--305},
publisher = {Springer},
year = {2022}
}
@inproceedings{DBLP:conf/esa/HenzingerPS22,
author = {Monika Henzinger and
Ami Paz and
A. R. Sricharan},
title = {Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {244},
pages = {65:1--65:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022}
}
@inproceedings{DBLP:conf/forc/HenzingerPRS22,
author = {Monika Henzinger and
Charlotte Peale and
Omer Reingold and
Judy Hanwen Shen},
title = {Leximax Approximations and Representative Cohort Selection},
booktitle = {{FORC}},
series = {LIPIcs},
volume = {218},
pages = {2:1--2:22},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022}
}
@inproceedings{DBLP:conf/infocom/HanauerHST22,
author = {Kathrin Hanauer and
Monika Henzinger and
Stefan Schmid and
Jonathan Trummer},
title = {Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter
Topologies},
booktitle = {{INFOCOM}},
pages = {1649--1658},
publisher = {{IEEE}},
year = {2022}
}
@inproceedings{DBLP:conf/mfcs/Henzinger22,
author = {Monika Henzinger},
title = {Modern Dynamic Data Structures (Invited Talk)},
booktitle = {{MFCS}},
series = {LIPIcs},
volume = {241},
pages = {2:1--2:2},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022}
}
@inproceedings{DBLP:conf/podc/El-HayekH022,
author = {Antoine El{-}Hayek and
Monika Henzinger and
Stefan Schmid},
title = {Brief Announcement: Broadcasting Time in Dynamic Rooted Trees is Linear},
booktitle = {{PODC}},
pages = {54--56},
publisher = {{ACM}},
year = {2022}
}
@inproceedings{DBLP:conf/sand/HanauerH022,
author = {Kathrin Hanauer and
Monika Henzinger and
Christian Schulz},
title = {Recent Advances in Fully Dynamic Graph Algorithms (Invited Talk)},
booktitle = {{SAND}},
series = {LIPIcs},
volume = {221},
pages = {1:1--1:47},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022}
}
@inproceedings{DBLP:conf/sand/HanauerHH22,
author = {Kathrin Hanauer and
Monika Henzinger and
Qi Cheng Hua},
title = {Fully Dynamic Four-Vertex Subgraph Counting},
booktitle = {{SAND}},
series = {LIPIcs},
volume = {221},
pages = {18:1--18:17},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022}
}
@inproceedings{DBLP:conf/soda/HenzingerLS22,
author = {Monika Henzinger and
Andrea Lincoln and
Barna Saha},
title = {The Complexity of Average-Case Dynamic Subgraph Counting},
booktitle = {{SODA}},
pages = {459--498},
publisher = {{SIAM}},
year = {2022}
}
@inproceedings{DBLP:conf/sosr/HenzingerPP022,
author = {Monika Henzinger and
Ami Paz and
Arash Pourdamghani and
Stefan Schmid},
title = {The augmentation-speed tradeoff for consistent network updates},
booktitle = {{SOSR}},
pages = {67--80},
publisher = {{ACM}},
year = {2022}
}
@misc{DBLP:data/10/HanauerHST22,
author = {Kathrin Hanauer and
Monika Henzinger and
Stefan Schmid and
Jonathan Trummer},
title = {DJ-Match/DJ-Match: Version 1.0.0 (Version v1.0.0)},
publisher = {Zenodo},
year = {2022},
month = jan,
howpublished = {\url{https://doi.org/10.5281/zenodo.5851268}},
note = {Accessed on YYYY-MM-DD.}
}
@article{DBLP:journals/corr/abs-2201-06621,
author = {Kathrin Hanauer and
Monika Henzinger and
Stefan Schmid and
Jonathan Trummer},
title = {Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter
Topologies},
journal = {CoRR},
volume = {abs/2201.06621},
year = {2022}
}
@article{DBLP:journals/corr/abs-2202-11205,
author = {Monika Henzinger and
Jalaj Upadhyay},
title = {Constant matters: Fine-grained Complexity of Differentially Private
Continual Observation Using Completely Bounded Norms},
journal = {CoRR},
volume = {abs/2202.11205},
year = {2022}
}
@article{DBLP:journals/corr/abs-2205-01157,
author = {Monika Henzinger and
Charlotte Peale and
Omer Reingold and
Judy Hanwen Shen},
title = {Leximax Approximations and Representative Cohort Selection},
journal = {CoRR},
volume = {abs/2205.01157},
year = {2022}
}
@article{DBLP:journals/corr/abs-2208-07572,
author = {Monika Henzinger and
Ami Paz and
A. R. Sricharan},
title = {Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs},
journal = {CoRR},
volume = {abs/2208.07572},
year = {2022}
}
@article{DBLP:journals/corr/abs-2211-03716,
author = {Monika Henzinger and
Ami Paz and
Arash Pourdamghani and
Stefan Schmid},
title = {The Augmentation-Speed Tradeoff for Consistent Network Updates},
journal = {CoRR},
volume = {abs/2211.03716},
year = {2022}
}
@article{DBLP:journals/corr/abs-2211-05006,
author = {Monika Henzinger and
Jalaj Upadhyay and
Sarvagya Upadhyay},
title = {Almost Tight Error Bounds on Differentially Private Continual Counting},
journal = {CoRR},
volume = {abs/2211.05006},
year = {2022}
}
@article{DBLP:journals/corr/abs-2211-09606,
author = {Gramoz Goranci and
Monika Henzinger},
title = {Incremental Approximate Maximum Flow in m\({}^{\mbox{1/2+o(1)}}\)
update time},
journal = {CoRR},
volume = {abs/2211.09606},
year = {2022}
}
@article{DBLP:journals/corr/abs-2211-10151,
author = {Antoine El{-}Hayek and
Monika Henzinger and
Stefan Schmid},
title = {Asymptotically Tight Bounds on the Time Complexity of Broadcast and
its Variants in Dynamic Networks},
journal = {CoRR},
volume = {abs/2211.10151},
year = {2022}
}
@article{DBLP:journals/corr/abs-2211-11352,
author = {Antoine El{-}Hayek and
Monika Henzinger and
Stefan Schmid},
title = {Brief Announcement: Broadcasting Time in Dynamic Rooted Trees is Linear},
journal = {CoRR},
volume = {abs/2211.11352},
year = {2022}
}
@article{DBLP:journals/corr/abs-2212-03016,
author = {Ashish Chiplunkar and
Monika Henzinger and
Sagar Sudhir Kale and
Maximilian V{\"{o}}tsch},
title = {Online Min-Max Paging},
journal = {CoRR},
volume = {abs/2212.03016},
year = {2022}
}
@article{DBLP:journals/iacr/HenzingerU22,
author = {Monika Henzinger and
Jalaj Upadhyay},
title = {Constant matters: Fine-grained Complexity of Differentially Private
Continual Observation Using Completely Bounded Norms},
journal = {{IACR} Cryptol. ePrint Arch.},
pages = {225},
year = {2022}
}
@article{DBLP:journals/ai/ChatterjeeDHS21,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Alexander Svozil},
title = {Algorithms and conditional lower bounds for planning problems},
journal = {Artif. Intell.},
volume = {297},
pages = {103499},
year = {2021}
}
@article{DBLP:journals/iandc/HenzingerP21,
author = {Monika Henzinger and
Pan Peng},
title = {Constant-time dynamic weight approximation for minimum spanning forest},
journal = {Inf. Comput.},
volume = {281},
pages = {104805},
year = {2021}
}
@article{DBLP:journals/siamcomp/HenzingerKN21,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {A Deterministic Almost-Tight Distributed Algorithm for Approximating
Single-Source Shortest Paths},
journal = {{SIAM} J. Comput.},
volume = {50},
number = {3},
year = {2021}
}
@article{DBLP:journals/talg/BernsteinFH21,
author = {Aaron Bernstein and
Sebastian Forster and
Monika Henzinger},
title = {A Deamortization Approach for Dynamic Spanner and Dynamic Maximal
Matching},
journal = {{ACM} Trans. Algorithms},
volume = {17},
number = {4},
pages = {29:1--29:51},
year = {2021}
}
@inproceedings{DBLP:conf/acda/HenzingerN021,
author = {Monika Henzinger and
Alexander Noe and
Christian Schulz},
title = {Faster Parallel Multiterminal Cuts},
booktitle = {{ACDA}},
pages = {100--110},
publisher = {{SIAM}},
year = {2021}
}
@inproceedings{DBLP:conf/alenex/GoranciHLSS21,
author = {Gramoz Goranci and
Monika Henzinger and
Dariusz Leniowski and
Christian Schulz and
Alexander Svozil},
title = {Fully Dynamic \emph{k}-Center Clustering in Low Dimensional Metrics},
booktitle = {{ALENEX}},
pages = {143--153},
publisher = {{SIAM}},
year = {2021}
}
@inproceedings{DBLP:conf/esa/FichtenbergerHO21,
author = {Hendrik Fichtenberger and
Monika Henzinger and
Lara Ost},
title = {Differentially Private Algorithms for Graphs Under Continual Observation},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {204},
pages = {42:1--42:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021}
}
@inproceedings{DBLP:conf/icalp/ChatterjeeHKS21,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Sagar Kale and
Alexander Svozil},
title = {Faster Algorithms for Bounded Liveness in Graphs and Game Graphs},
booktitle = {{ICALP}},
series = {LIPIcs},
volume = {198},
pages = {124:1--124:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021}
}
@inproceedings{DBLP:conf/lics/ChatterjeeDHS21,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Alexander Svozil},
title = {Symbolic Time and Space Tradeoffs for Probabilistic Verification},
booktitle = {{LICS}},
pages = {1--13},
publisher = {{IEEE}},
year = {2021}
}
@inproceedings{DBLP:conf/networking/HenzingerP021,
author = {Monika Henzinger and
Ami Paz and
Stefan Schmid},
title = {On the Complexity of Weight-Dynamic Network Algorithms},
booktitle = {Networking},
pages = {1--9},
publisher = {{IEEE}},
year = {2021}
}
@inproceedings{DBLP:conf/soda/ForsterGH21,
author = {Sebastian Forster and
Gramoz Goranci and
Monika Henzinger},
title = {Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with
Applications},
booktitle = {{SODA}},
pages = {1226--1245},
publisher = {{SIAM}},
year = {2021}
}
@inproceedings{DBLP:conf/soda/BergamaschiHGWW21,
author = {Thiago Bergamaschi and
Monika Henzinger and
Maximilian Probst Gutenberg and
Virginia {Vassilevska Williams} and
Nicole Wein},
title = {New Techniques and Fine-Grained Hardness for Dynamic Near-Additive
Spanners},
booktitle = {{SODA}},
pages = {1836--1855},
publisher = {{SIAM}},
year = {2021}
}
@inproceedings{DBLP:conf/soda/BhattacharyaHNW21,
author = {Sayan Bhattacharya and
Monika Henzinger and
Danupon Nanongkai and
Xiaowei Wu},
title = {Dynamic Set Cover: Improved Amortized and Worst-Case Update Time},
booktitle = {{SODA}},
pages = {2537--2549},
publisher = {{SIAM}},
year = {2021}
}
@inproceedings{DBLP:conf/soda/HenzingerNRS21,
author = {Monika Henzinger and
Stefan Neumann and
Harald R{\"{a}}cke and
Stefan Schmid},
title = {Tight Bounds for Online Graph Partitioning},
booktitle = {{SODA}},
pages = {2799--2818},
publisher = {{SIAM}},
year = {2021}
}
@inproceedings{DBLP:conf/wads/HenzingerW21,
author = {Monika Henzinger and
Xiaowei Wu},
title = {Upper and Lower Bounds for Fully Retroactive Graph Problems},
booktitle = {{WADS}},
series = {Lecture Notes in Computer Science},
volume = {12808},
pages = {471--484},
publisher = {Springer},
year = {2021}
}
@article{DBLP:journals/corr/abs-2101-05033,
author = {Monika Henzinger and
Alexander Noe and
Christian Schulz},
title = {Practical Fully Dynamic Minimum Cut Algorithms},
journal = {CoRR},
volume = {abs/2101.05033},
year = {2021}
}
@article{DBLP:journals/corr/abs-2102-11169,
author = {Kathrin Hanauer and
Monika Henzinger and
Christian Schulz},
title = {Recent Advances in Fully Dynamic Graph Algorithms},
journal = {CoRR},
volume = {abs/2102.11169},
year = {2021}
}
@article{DBLP:journals/corr/abs-2104-07466,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Alexander Svozil},
title = {Symbolic Time and Space Tradeoffs for Probabilistic Verification},
journal = {CoRR},
volume = {abs/2104.07466},
year = {2021}
}
@article{DBLP:journals/corr/abs-2105-13172,
author = {Monika Henzinger and
Ami Paz and
Stefan Schmid},
title = {On the Complexity of Weight-Dynamic Network Algorithms},
journal = {CoRR},
volume = {abs/2105.13172},
year = {2021}
}
@article{DBLP:journals/corr/abs-2106-14756,
author = {Hendrik Fichtenberger and
Monika Henzinger and
Lara Ost},
title = {Differentially Private Algorithms for Graphs Under Continual Observation},
journal = {CoRR},
volume = {abs/2106.14756},
year = {2021}
}
@article{DBLP:journals/corr/abs-2106-15524,
author = {Kathrin Hanauer and
Monika Henzinger and
Qi Cheng Hua},
title = {Fully Dynamic Four-Vertex Subgraph Counting},
journal = {CoRR},
volume = {abs/2106.15524},
year = {2021}
}
@article{DBLP:journals/corr/abs-2108-04564,
author = {Monika Henzinger and
Alexander Noe},
title = {Random Rank-Based, Hierarchical or Trivial: Which Dynamic Graph Algorithm
Performs Best in Practice?},
journal = {CoRR},
volume = {abs/2108.04564},
year = {2021}
}
@article{DBLP:journals/corr/abs-2109-00653,
author = {Monika Henzinger and
Billy Jin and
Richard Peng and
David P. Williamson},
title = {Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm
Flows},
journal = {CoRR},
volume = {abs/2109.00653},
year = {2021}
}
@article{DBLP:journals/corr/abs-2112-07217,
author = {Hendrik Fichtenberger and
Monika Henzinger and
Andreas Wiese},
title = {On fully dynamic constant-factor approximation algorithms for clustering
problems},
journal = {CoRR},
volume = {abs/2112.07217},
year = {2021}
}
@article{DBLP:journals/eccc/HenzingerLS21,
author = {Monika Henzinger and
Andrea Lincoln and
Barna Saha},
title = {The Complexity of Average-Case Dynamic Subgraph Counting},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR21-157}},
year = {2021}
}
@article{DBLP:journals/algorithmica/BhattacharyaCH20,
author = {Sayan Bhattacharya and
Deeparnab Chakrabarty and
Monika Henzinger},
title = {Deterministic Dynamic Matching in {O(1)} Update Time},
journal = {Algorithmica},
volume = {82},
number = {4},
pages = {1057--1080},
year = {2020}
}
@article{DBLP:journals/algorithmica/HenzingerLM20,
author = {Monika Henzinger and
Dariusz Leniowski and
Claire Mathieu},
title = {Dynamic Clustering to Minimize the Sum of Radii},
journal = {Algorithmica},
volume = {82},
number = {11},
pages = {3183--3194},
year = {2020}
}
@article{DBLP:journals/siamcomp/HenzingerRW20,
author = {Monika Henzinger and
Satish Rao and
Di Wang},
title = {Local Flow Partitioning for Faster Edge Connectivity},
journal = {{SIAM} J. Comput.},
volume = {49},
number = {1},
pages = {1--36},
year = {2020}
}
@article{DBLP:journals/siamdm/GoranciHP20,
author = {Gramoz Goranci and
Monika Henzinger and
Pan Peng},
title = {Improved Guarantees for Vertex Sparsification in Planar Graphs},
journal = {{SIAM} J. Discret. Math.},
volume = {34},
number = {1},
pages = {130--162},
year = {2020}
}
@inproceedings{DBLP:conf/alenex/HenzingerN020,
author = {Monika Henzinger and
Alexander Noe and
Christian Schulz},
title = {Shared-Memory Branch-and-Reduce for Multiterminal Cuts},
booktitle = {{ALENEX}},
pages = {42--55},
publisher = {{SIAM}},
year = {2020}
}
@inproceedings{DBLP:conf/alenex/HanauerH020,
author = {Kathrin Hanauer and
Monika Henzinger and
Christian Schulz},
title = {Fully Dynamic Single-Source Reachability in Practice: An Experimental
Study},
booktitle = {{ALENEX}},
pages = {106--119},
publisher = {{SIAM}},
year = {2020}
}
@inproceedings{DBLP:conf/compgeom/Henzinger0W20,
author = {Monika Henzinger and
Stefan Neumann and
Andreas Wiese},
title = {Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes
and Hyperrectangles},
booktitle = {SoCG},
series = {LIPIcs},
volume = {164},
pages = {51:1--51:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020}
}
@inproceedings{DBLP:conf/esa/HenzingerK20,
author = {Monika Henzinger and
Sagar Kale},
title = {Fully-Dynamic Coresets},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {173},
pages = {57:1--57:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020}
}
@inproceedings{DBLP:conf/esa/Henzinger0P020,
author = {Monika Henzinger and
Shahbaz Khan and
Richard D. Paul and
Christian Schulz},
title = {Dynamic Matching Algorithms in Practice},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {173},
pages = {58:1--58:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020}
}
@inproceedings{DBLP:conf/esa/HenzingerN0S20,
author = {Monika Henzinger and
Alexander Noe and
Christian Schulz and
Darren Strash},
title = {Finding All Global Minimum Cuts in Practice},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {173},
pages = {59:1--59:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020}
}
@inproceedings{DBLP:conf/focs/ChenGHPS20,
author = {Li Chen and
Gramoz Goranci and
Monika Henzinger and
Richard Peng and
Thatchaphol Saranurak},
title = {Fast Dynamic Cuts, Distances and Effective Resistances via Vertex
Sparsifiers},
booktitle = {{FOCS}},
pages = {1135--1146},
publisher = {{IEEE}},
year = {2020}
}
@inproceedings{DBLP:conf/stacs/Henzinger020,
author = {Monika Henzinger and
Pan Peng},
title = {Constant-Time Dynamic ({\(\Delta\)}+1)-Coloring},
booktitle = {{STACS}},
series = {LIPIcs},
volume = {154},
pages = {53:1--53:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020}
}
@inproceedings{DBLP:conf/wea/HanauerH020,
author = {Kathrin Hanauer and
Monika Henzinger and
Christian Schulz},
title = {Faster Fully Dynamic Transitive Closure in Practice},
booktitle = {{SEA}},
series = {LIPIcs},
volume = {160},
pages = {14:1--14:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020}
}
@incollection{DBLP:series/mimb/BiedermannHSS20,
author = {Sonja Biedermann and
Monika Henzinger and
Christian Schulz and
Bernhard Schuster},
title = {Vienna Graph Clustering},
booktitle = {Protein-Protein Interaction Networks},
series = {Methods in Molecular Biology},
volume = {2074},
pages = {215--231},
publisher = {Springer},
year = {2020}
}
@article{DBLP:journals/corr/abs-2002-00813,
author = {Kathrin Hanauer and
Monika Henzinger and
Christian Schulz},
title = {Faster Fully Dynamic Transitive Closure in Practice},
journal = {CoRR},
volume = {abs/2002.00813},
year = {2020}
}
@article{DBLP:journals/corr/abs-2002-06948,
author = {Monika Henzinger and
Alexander Noe and
Christian Schulz and
Darren Strash},
title = {Finding All Global Minimum Cuts In Practice},
journal = {CoRR},
volume = {abs/2002.06948},
year = {2020}
}
@article{DBLP:journals/corr/abs-2002-10142,
author = {Monika Henzinger and
Stefan Neumann and
Andreas Wiese},
title = {Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity},
journal = {CoRR},
volume = {abs/2002.10142},
year = {2020}
}
@article{DBLP:journals/corr/abs-2002-11171,
author = {Sayan Bhattacharya and
Monika Henzinger and
Danupon Nanongkai and
Xiaowei Wu},
title = {An Improved Algorithm for Dynamic Set Cover},
journal = {CoRR},
volume = {abs/2002.11171},
year = {2020}
}
@article{DBLP:journals/corr/abs-2003-02605,
author = {Monika Henzinger and
Stefan Neumann and
Andreas Wiese},
title = {Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes
and Hyperrectangles},
journal = {CoRR},
volume = {abs/2003.02605},
year = {2020}
}
@article{DBLP:journals/corr/abs-2004-09099,
author = {Monika Henzinger and
Shahbaz Khan and
Richard D. Paul and
Christian Schulz},
title = {Dynamic Matching Algorithms in Practice},
journal = {CoRR},
volume = {abs/2004.09099},
year = {2020}
}
@article{DBLP:journals/corr/abs-2004-10319,
author = {Sebastian Forster and
Gramoz Goranci and
Monika Henzinger},
title = {Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with
Applications},
journal = {CoRR},
volume = {abs/2004.10319},
year = {2020}
}
@article{DBLP:journals/corr/abs-2004-11666,
author = {Monika Henzinger and
Alexander Noe and
Christian Schulz},
title = {Faster Parallel Multiterminal Cuts},
journal = {CoRR},
volume = {abs/2004.11666},
year = {2020}
}
@article{DBLP:journals/corr/abs-2004-14891,
author = {Monika Henzinger and
Sagar Kale},
title = {Fully-Dynamic Coresets},
journal = {CoRR},
volume = {abs/2004.14891},
year = {2020}
}
@article{DBLP:journals/corr/abs-2005-02368,
author = {Li Chen and
Gramoz Goranci and
Monika Henzinger and
Richard Peng and
Thatchaphol Saranurak},
title = {Fast Dynamic Cuts, Distances and Effective Resistances via Vertex
Sparsifiers},
journal = {CoRR},
volume = {abs/2005.02368},
year = {2020}
}
@article{DBLP:journals/corr/abs-2010-10134,
author = {Thiago Bergamaschi and
Monika Henzinger and
Maximilian Probst Gutenberg and
Virginia {Vassilevska Williams} and
Nicole Wein},
title = {New Techniques and Fine-Grained Hardness for Dynamic Near-Additive
Spanners},
journal = {CoRR},
volume = {abs/2010.10134},
year = {2020}
}
@article{DBLP:journals/corr/abs-2010-16316,
author = {Monika Henzinger and
Billy Jin and
David P. Williamson},
title = {A Combinatorial Cut-Based Algorithm for Solving Laplacian Linear Systems},
journal = {CoRR},
volume = {abs/2010.16316},
year = {2020}
}
@article{DBLP:journals/corr/abs-2011-00977,
author = {Monika Henzinger and
Pan Peng},
title = {Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest},
journal = {CoRR},
volume = {abs/2011.00977},
year = {2020}
}
@article{DBLP:journals/corr/abs-2011-01017,
author = {Monika Henzinger and
Stefan Neumann and
Harald R{\"{a}}cke and
Stefan Schmid},
title = {Tight Bounds for Online Graph Partitioning},
journal = {CoRR},
volume = {abs/2011.01017},
year = {2020}
}
@article{DBLP:journals/pomacs/Henzinger0019,
author = {Monika Henzinger and
Stefan Neumann and
Stefan Schmid},
title = {Efficient Distributed Workload (Re-)Embedding},
journal = {Proc. {ACM} Meas. Anal. Comput. Syst.},
volume = {3},
number = {1},
pages = {13:1--13:38},
year = {2019}
}
@article{DBLP:journals/tcs/BhattacharyaHN19,
author = {Sayan Bhattacharya and
Monika Henzinger and
Stefan Neumann},
title = {New amortized cell-probe lower bounds for dynamic problems},
journal = {Theor. Comput. Sci.},
volume = {779},
pages = {72--87},
year = {2019}
}
@inproceedings{DBLP:conf/concur/ChatterjeeDHS19,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Alexander Svozil},
title = {Near-Linear Time Algorithms for Streett Objectives in Graphs and MDPs},
booktitle = {{CONCUR}},
series = {LIPIcs},
volume = {140},
pages = {7:1--7:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019}
}
@inproceedings{DBLP:conf/focs/BhattacharyaHN19,
author = {Sayan Bhattacharya and
Monika Henzinger and
Danupon Nanongkai},
title = {A New Deterministic Algorithm for Dynamic Set Cover},
booktitle = {{FOCS}},
pages = {406--423},
publisher = {{IEEE} Computer Society},
year = {2019}
}
@inproceedings{DBLP:conf/icalp/AnconaHRWW19,
author = {Bertie Ancona and
Monika Henzinger and
Liam Roditty and
Virginia {Vassilevska Williams} and
Nicole Wein},
title = {Algorithms and Hardness for Diameter in Dynamic Graphs},
booktitle = {{ICALP}},
series = {LIPIcs},
volume = {132},
pages = {13:1--13:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019}
}
@inproceedings{DBLP:conf/ipps/HenzingerN019,
author = {Monika Henzinger and
Alexander Noe and
Christian Schulz},
title = {Shared-Memory Exact Minimum Cuts},
booktitle = {{IPDPS}},
pages = {13--22},
publisher = {{IEEE}},
year = {2019}
}
@inproceedings{DBLP:conf/sigmetrics/Henzinger0019,
author = {Monika Henzinger and
Stefan Neumann and
Stefan Schmid},
title = {Efficient Distributed Workload (Re-)Embedding},
booktitle = {{SIGMETRICS} (Abstracts)},
pages = {43--44},
publisher = {{ACM}},
year = {2019}
}
@inproceedings{DBLP:conf/soda/BernsteinFH19,
author = {Aaron Bernstein and
Sebastian Forster and
Monika Henzinger},
title = {A Deamortization Approach for Dynamic Spanner and Dynamic Maximal
Matching},
booktitle = {{SODA}},
pages = {1899--1918},
publisher = {{SIAM}},
year = {2019}
}
@inproceedings{DBLP:conf/stoc/DagaHNS19,
author = {Mohit Daga and
Monika Henzinger and
Danupon Nanongkai and
Thatchaphol Saranurak},
title = {Distributed edge connectivity in sublinear time},
booktitle = {{STOC}},
pages = {343--354},
publisher = {{ACM}},
year = {2019}
}
@article{DBLP:journals/corr/abs-1902-02304,
author = {Sayan Bhattacharya and
Monika Henzinger and
Stefan Neumann},
title = {New Amortized Cell-Probe Lower Bounds for Dynamic Problems},
journal = {CoRR},
volume = {abs/1902.02304},
year = {2019}
}
@article{DBLP:journals/corr/abs-1904-04341,
author = {Mohit Daga and
Monika Henzinger and
Danupon Nanongkai and
Thatchaphol Saranurak},
title = {Distributed Edge Connectivity in Sublinear Time},
journal = {CoRR},
volume = {abs/1904.04341},
year = {2019}
}
@article{DBLP:journals/corr/abs-1904-05474,
author = {Monika Henzinger and
Stefan Neumann and
Stefan Schmid},
title = {Efficient Distributed Workload (Re-)Embedding},
journal = {CoRR},
volume = {abs/1904.05474},
year = {2019}
}
@article{DBLP:journals/corr/abs-1905-01216,
author = {Kathrin Hanauer and
Monika Henzinger and
Christian Schulz},
title = {Fully Dynamic Single-Source Reachability in Practice: An Experimental
Study},
journal = {CoRR},
volume = {abs/1905.01216},
year = {2019}
}
@article{DBLP:journals/corr/abs-1907-04745,
author = {Monika Henzinger and
Pan Peng},
title = {Constant-Time Dynamic ({\(\Delta\)}+1)-Coloring and Weight Approximation
for Minimum Spanning Forest: Dynamic Algorithms Meet Property Testing},
journal = {CoRR},
volume = {abs/1907.04745},
year = {2019}
}
@article{DBLP:journals/corr/abs-1908-03948,
author = {Gramoz Goranci and
Monika Henzinger and
Dariusz Leniowski and
Alexander Svozil},
title = {Fully Dynamic k-Center Clustering in Doubling Metrics},
journal = {CoRR},
volume = {abs/1908.03948},
year = {2019}
}
@article{DBLP:journals/corr/abs-1908-04141,
author = {Monika Henzinger and
Alexander Noe and
Christian Schulz},
title = {Shared-Memory Branch-and-Reduce for Multiterminal Cuts},
journal = {CoRR},
volume = {abs/1908.04141},
year = {2019}
}
@article{DBLP:journals/corr/abs-1909-04983,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Alexander Svozil},
title = {Quasipolynomial Set-Based Symbolic Algorithms for Parity Games},
journal = {CoRR},
volume = {abs/1909.04983},
year = {2019}
}
@article{DBLP:journals/corr/abs-1909-05539,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Alexander Svozil},
title = {Near-Linear Time Algorithms for Streett Objectives in Graphs and MDPs},
journal = {CoRR},
volume = {abs/1909.05539},
year = {2019}
}
@article{DBLP:journals/corr/abs-1909-06653,
author = {Gramoz Goranci and
Monika Henzinger and
Dariusz Leniowski},
title = {A Tree Structure For Dynamic Facility Location},
journal = {CoRR},
volume = {abs/1909.06653},
year = {2019}
}
@article{DBLP:journals/corr/abs-1909-11600,
author = {Sayan Bhattacharya and
Monika Henzinger and
Danupon Nanongkai},
title = {A New Deterministic Algorithm for Dynamic Set Cover},
journal = {CoRR},
volume = {abs/1909.11600},
year = {2019}
}
@article{DBLP:journals/corr/abs-1910-03332,
author = {Monika Henzinger and
Xiaowei Wu},
title = {Upper and Lower Bounds for Fully Retroactive Graph Problems},
journal = {CoRR},
volume = {abs/1910.03332},
year = {2019}
}
@article{DBLP:journals/iandc/BhattacharyaHI18,
author = {Sayan Bhattacharya and
Monika Henzinger and
Giuseppe F. Italiano},
title = {Dynamic algorithms via the primal-dual method},
journal = {Inf. Comput.},
volume = {261},
pages = {219--239},
year = {2018}
}
@article{DBLP:journals/jacm/HenzingerKN18,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear
Total Update Time},
journal = {J. {ACM}},
volume = {65},
number = {6},
pages = {36:1--36:40},
year = {2018}
}
@article{DBLP:journals/jea/HenzingerNSS18,
author = {Monika Henzinger and
Alexander Noe and
Christian Schulz and
Darren Strash},
title = {Practical Minimum Cut Algorithms},
journal = {{ACM} J. Exp. Algorithmics},
volume = {23},
year = {2018}
}
@article{DBLP:journals/siamcomp/BhattacharyaHI18,
author = {Sayan Bhattacharya and
Monika Henzinger and
Giuseppe F. Italiano},
title = {Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching},
journal = {{SIAM} J. Comput.},
volume = {47},
number = {3},
pages = {859--887},
year = {2018}
}
@article{DBLP:journals/talg/GoranciHT18,
author = {Gramoz Goranci and
Monika Henzinger and
Mikkel Thorup},
title = {Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time},
journal = {{ACM} Trans. Algorithms},
volume = {14},
number = {2},
pages = {17:1--17:21},
year = {2018}
}
@article{DBLP:journals/teco/DuttingHS18,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Martin Starnberger},
title = {Valuation Compressions in VCG-Based Combinatorial Auctions},
journal = {{ACM} Trans. Economics and Comput.},
volume = {6},
number = {2},
pages = {5:1--5:18},
year = {2018}
}
@inproceedings{DBLP:conf/aips/ChatterjeeDHS18,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Alexander Svozil},
title = {Algorithms and Conditional Lower Bounds for Planning Problems},
booktitle = {{ICAPS}},
pages = {56--64},
publisher = {{AAAI} Press},
year = {2018}
}
@inproceedings{DBLP:conf/alenex/HenzingerN0S18,
author = {Monika Henzinger and
Alexander Noe and
Christian Schulz and
Darren Strash},
title = {Practical Minimum Cut Algorithms},
booktitle = {{ALENEX}},
pages = {48--61},
publisher = {{SIAM}},
year = {2018}
}
@inproceedings{DBLP:conf/cav/ChatterjeeHLOT18,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Veronika Loitzenbauer and
Simin Oraee and
Viktor Toman},
title = {Symbolic Algorithms for Graphs and Markov Decision Processes with
Fairness Objectives},
booktitle = {{CAV} {(2)}},
series = {Lecture Notes in Computer Science},
volume = {10982},
pages = {178--197},
publisher = {Springer},
year = {2018}
}
@inproceedings{DBLP:conf/esa/GoranciHL18,
author = {Gramoz Goranci and
Monika Henzinger and
Dariusz Leniowski},
title = {A Tree Structure For Dynamic Facility Location},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {112},
pages = {39:1--39:13},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018}
}
@inproceedings{DBLP:conf/esa/GoranciHP18,
author = {Gramoz Goranci and
Monika Henzinger and
Pan Peng},
title = {Dynamic Effective Resistances and Approximate Schur Complement on
Separable Graphs},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {112},
pages = {40:1--40:15},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018}
}
@inproceedings{DBLP:conf/lpar/ChatterjeeDHS18,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Alexander Svozil},
title = {Quasipolynomial Set-Based Symbolic Algorithms for Parity Games},
booktitle = {{LPAR}},
series = {EPiC Series in Computing},
volume = {57},
pages = {233--253},
publisher = {EasyChair},
year = {2018}
}
@inproceedings{DBLP:conf/soda/BhattacharyaCHN18,
author = {Sayan Bhattacharya and
Deeparnab Chakrabarty and
Monika Henzinger and
Danupon Nanongkai},
title = {Dynamic Algorithms for Graph Coloring},
booktitle = {{SODA}},
pages = {1--20},
publisher = {{SIAM}},
year = {2018}
}
@inproceedings{DBLP:conf/soda/ChatterjeeDHL18,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Veronika Loitzenbauer},
title = {Lower Bounds for Symbolic Computation on Graphs: Strongly Connected
Components, Liveness, Safety, and Diameter},
booktitle = {{SODA}},
pages = {2341--2356},
publisher = {{SIAM}},
year = {2018}
}
@inproceedings{DBLP:conf/sofsem/Henzinger18,
author = {Monika Henzinger},
title = {The State of the Art in Dynamic Graph Algorithms},
booktitle = {{SOFSEM}},
series = {Lecture Notes in Computer Science},
volume = {10706},
pages = {40--44},
publisher = {Springer},
year = {2018}
}
@inproceedings{DBLP:conf/wea/BiedermannH0S18,
author = {Sonja Biedermann and
Monika Henzinger and
Christian Schulz and
Bernhard Schuster},
title = {Memetic Graph Clustering},
booktitle = {{SEA}},
series = {LIPIcs},
volume = {103},
pages = {3:1--3:15},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018}
}
@proceedings{DBLP:conf/stoc/2018,
editor = {Ilias Diakonikolas and
David Kempe and
Monika Henzinger},
title = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
publisher = {{ACM}},
year = {2018}
}
@article{DBLP:journals/corr/abs-1802-07034,
author = {Sonja Biedermann and
Monika Henzinger and
Christian Schulz and
Bernhard Schuster},
title = {Memetic Graph Clustering},
journal = {CoRR},
volume = {abs/1802.07034},
year = {2018}
}
@article{DBLP:journals/corr/abs-1802-09111,
author = {Gramoz Goranci and
Monika Henzinger and
Pan Peng},
title = {Dynamic Effective Resistances and Approximate Schur Complement on
Separable Graphs},
journal = {CoRR},
volume = {abs/1802.09111},
year = {2018}
}
@article{DBLP:journals/corr/abs-1804-00206,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Veronika Loitzenbauer and
Simin Oraee and
Viktor Toman},
title = {Symbolic Algorithms for Graphs and Markov Decision Processes with
Fairness Objectives},
journal = {CoRR},
volume = {abs/1804.00206},
year = {2018}
}
@article{DBLP:journals/corr/abs-1804-07031,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Alexander Svozil},
title = {Algorithms and Conditional Lower Bounds for Planning Problems},
journal = {CoRR},
volume = {abs/1804.07031},
year = {2018}
}
@article{DBLP:journals/corr/abs-1808-05458,
author = {Monika Henzinger and
Alexander Noe and
Christian Schulz},
title = {Shared-memory Exact Minimum Cuts},
journal = {CoRR},
volume = {abs/1808.05458},
year = {2018}
}
@article{DBLP:journals/corr/abs-1810-10932,
author = {Aaron Bernstein and
Sebastian Forster and
Monika Henzinger},
title = {A Deamortization Approach for Dynamic Spanner and Dynamic Maximal
Matching},
journal = {CoRR},
volume = {abs/1810.10932},
year = {2018}
}
@article{DBLP:journals/corr/abs-1811-12527,
author = {Bertie Ancona and
Monika Henzinger and
Liam Roditty and
Virginia {Vassilevska Williams} and
Nicole Wein},
title = {Algorithms and Hardness for Diameter in Dynamic Graphs},
journal = {CoRR},
volume = {abs/1811.12527},
year = {2018}
}
@article{DBLP:journals/algorithmica/DvorakHW17,
author = {Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
David P. Williamson},
title = {Maximizing a Submodular Function with Viability Constraints},
journal = {Algorithmica},
volume = {77},
number = {1},
pages = {152--172},
year = {2017}
}
@article{DBLP:journals/lmcs/ChatterjeeHL17,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Veronika Loitzenbauer},
title = {Improved Algorithms for Parity and Streett objectives},
journal = {Log. Methods Comput. Sci.},
volume = {13},
number = {3},
year = {2017}
}
@article{DBLP:journals/mst/BhattacharyaDHS17,
author = {Sayan Bhattacharya and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Martin Starnberger},
title = {Welfare Maximization with Friends-of-Friends Network Externalities},
journal = {Theory Comput. Syst.},
volume = {61},
number = {4},
pages = {948--986},
year = {2017}
}
@article{DBLP:journals/sigir/BharatH17,
author = {Krishna Bharat and
Monika Henzinger},
title = {Improved Algorithms for Topic Distillation in a Hyperlinked Environment},
journal = {{SIGIR} Forum},
volume = {51},
number = {2},
pages = {194--201},
year = {2017}
}
@article{DBLP:journals/talg/HenzingerKN17,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially
Dynamic Networks},
journal = {{ACM} Trans. Algorithms},
volume = {13},
number = {4},
pages = {51:1--51:24},
year = {2017}
}
@inproceedings{DBLP:conf/csl/ChatterjeeDHL17,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Veronika Loitzenbauer},
title = {Improved Set-Based Symbolic Algorithms for Parity Games},
booktitle = {{CSL}},
series = {LIPIcs},
volume = {82},
pages = {18:1--18:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017}
}
@inproceedings{DBLP:conf/esa/GoranciHP17,
author = {Gramoz Goranci and
Monika Henzinger and
Pan Peng},
title = {Improved Guarantees for Vertex Sparsification in Planar Graphs},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {87},
pages = {44:1--44:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017}
}
@inproceedings{DBLP:conf/esa/GoranciHP17a,
author = {Gramoz Goranci and
Monika Henzinger and
Pan Peng},
title = {The Power of Vertex Sparsifiers in Dynamic Graph Algorithms},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {87},
pages = {45:1--45:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017}
}
@inproceedings{DBLP:conf/esa/HenzingerLM17,
author = {Monika Henzinger and
Dariusz Leniowski and
Claire Mathieu},
title = {Dynamic Clustering to Minimize the Sum of Radii},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {87},
pages = {48:1--48:10},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017}
}
@inproceedings{DBLP:conf/icalp/Henzinger17,
author = {Monika Henzinger},
title = {Efficient Algorithms for Graph-Related Problems in Computer-Aided
Verification (Invited Talk)},
booktitle = {{ICALP}},
series = {LIPIcs},
volume = {80},
pages = {2:1--2:1},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017}
}
@inproceedings{DBLP:conf/icml/WangFHMR17,
author = {Di Wang and
Kimon Fountoulakis and
Monika Henzinger and
Michael W. Mahoney and
Satish Rao},
title = {Capacity Releasing Diffusion for Speed and Locality},
booktitle = {{ICML}},
series = {Proceedings of Machine Learning Research},
volume = {70},
pages = {3598--3607},
publisher = {{PMLR}},
year = {2017}
}
@inproceedings{DBLP:conf/innovations/HenzingerL0W17,
author = {Monika Henzinger and
Andrea Lincoln and
Stefan Neumann and
Virginia {Vassilevska Williams}},
title = {Conditional Hardness for Sensitivity Problems},
booktitle = {{ITCS}},
series = {LIPIcs},
volume = {67},
pages = {26:1--26:31},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017}
}
@inproceedings{DBLP:conf/ipco/BhattacharyaCH17,
author = {Sayan Bhattacharya and
Deeparnab Chakrabarty and
Monika Henzinger},
title = {Deterministic Fully Dynamic Approximate Vertex Cover and Fractional
Matching in {O(1)} Amortized Update Time},
booktitle = {{IPCO}},
series = {Lecture Notes in Computer Science},
volume = {10328},
pages = {86--98},
publisher = {Springer},
year = {2017}
}
@inproceedings{DBLP:conf/mfcs/ChatterjeeHS17,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Alexander Svozil},
title = {Faster Algorithms for Mean-Payoff Parity Games},
booktitle = {{MFCS}},
series = {LIPIcs},
volume = {83},
pages = {39:1--39:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017}
}
@inproceedings{DBLP:conf/soda/BhattacharyaHN17,
author = {Sayan Bhattacharya and
Monika Henzinger and
Danupon Nanongkai},
title = {Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover
in \emph{O}(log\({}^{\mbox{3}}\) \emph{n}) Worst Case Update Time},
booktitle = {{SODA}},
pages = {470--489},
publisher = {{SIAM}},
year = {2017}
}
@inproceedings{DBLP:conf/soda/HenzingerRW17,
author = {Monika Henzinger and
Satish Rao and
Di Wang},
title = {Local Flow Partitioning for Faster Edge Connectivity},
booktitle = {{SODA}},
pages = {1919--1938},
publisher = {{SIAM}},
year = {2017}
}
@article{DBLP:journals/corr/GoranciHP17,
author = {Gramoz Goranci and
Monika Henzinger and
Pan Peng},
title = {Improved Guarantees for Vertex Sparsification in Planar Graphs},
journal = {CoRR},
volume = {abs/1702.01136},
year = {2017}
}
@article{DBLP:journals/corr/HenzingerL0W17,
author = {Monika Henzinger and
Andrea Lincoln and
Stefan Neumann and
Virginia {Vassilevska Williams}},
title = {Conditional Hardness for Sensitivity Problems},
journal = {CoRR},
volume = {abs/1703.01638},
year = {2017}
}
@article{DBLP:journals/corr/HenzingerRW17,
author = {Monika Henzinger and
Satish Rao and
Di Wang},
title = {Local Flow Partitioning for Faster Edge Connectivity},
journal = {CoRR},
volume = {abs/1704.01254},
year = {2017}
}
@article{DBLP:journals/corr/BhattacharyaHN17,
author = {Sayan Bhattacharya and
Monika Henzinger and
Danupon Nanongkai},
title = {Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover
in O(log\({}^{\mbox{3}}\)n) Worst Case Update Time},
journal = {CoRR},
volume = {abs/1704.02844},
year = {2017}
}
@article{DBLP:journals/corr/ChatterjeeDHL17,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Veronika Loitzenbauer},
title = {Improved Set-based Symbolic Algorithms for Parity Games},
journal = {CoRR},
volume = {abs/1706.04889},
year = {2017}
}
@article{DBLP:journals/corr/WangFHMR17,
author = {Di Wang and
Kimon Fountoulakis and
Monika Henzinger and
Michael W. Mahoney and
Satish Rao},
title = {Capacity Releasing Diffusion for Speed and Locality},
journal = {CoRR},
volume = {abs/1706.05826},
year = {2017}
}
@article{DBLP:journals/corr/ChatterjeeHS17,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Alexander Svozil},
title = {Faster Algorithms for Mean-Payoff Parity Games},
journal = {CoRR},
volume = {abs/1706.06139},
year = {2017}
}
@article{DBLP:journals/corr/HenzingerLM17,
author = {Monika Henzinger and
Dariusz Leniowski and
Claire Mathieu},
title = {Dynamic clustering to minimize the sum of radii},
journal = {CoRR},
volume = {abs/1707.02577},
year = {2017}
}
@article{DBLP:journals/corr/abs-1708-06127,
author = {Monika Henzinger and
Alexander Noe and
Christian Schulz and
Darren Strash},
title = {Practical Minimum Cut Algorithms},
journal = {CoRR},
volume = {abs/1708.06127},
year = {2017}
}
@article{DBLP:journals/corr/abs-1711-04355,
author = {Sayan Bhattacharya and
Deeparnab Chakrabarty and
Monika Henzinger and
Danupon Nanongkai},
title = {Dynamic Algorithms for Graph Coloring},
journal = {CoRR},
volume = {abs/1711.04355},
year = {2017}
}
@article{DBLP:journals/corr/abs-1711-09148,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Veronika Loitzenbauer},
title = {Lower Bounds for Symbolic Computation on Graphs: Strongly Connected
Components, Liveness, Safety, and Diameter},
journal = {CoRR},
volume = {abs/1711.09148},
year = {2017}
}
@article{DBLP:journals/corr/abs-1712-06473,
author = {Gramoz Goranci and
Monika Henzinger and
Pan Peng},
title = {The Power of Vertex Sparsifiers in Dynamic Graph Algorithms},
journal = {CoRR},
volume = {abs/1712.06473},
year = {2017}
}
@article{DBLP:journals/eatcs/AcetoDGHHISST16,
author = {Luca Aceto and
Mariangiola Dezani{-}Ciancaglini and
Yuri Gurevich and
David Harel and
Monika Henzinger and
Giuseppe F. Italiano and
Scott A. Smolka and
Paul G. Spirakis and
Wolfgang Thomas},
title = {{EATCS} Fellows' Advice to the Young Theoretical Computer Scientist},
journal = {Bull. {EATCS}},
volume = {119},
year = {2016}
}
@article{DBLP:journals/siamcomp/HenzingerKN16,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier
and Derandomization},
journal = {{SIAM} J. Comput.},
volume = {45},
number = {3},
pages = {947--1006},
year = {2016}
}
@inproceedings{DBLP:conf/esa/GoranciHT16,
author = {Gramoz Goranci and
Monika Henzinger and
Mikkel Thorup},
title = {Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {57},
pages = {46:1--46:17},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016}
}
@inproceedings{DBLP:conf/esa/HenzingerN16,
author = {Monika Henzinger and
Stefan Neumann},
title = {Incremental and Fully Dynamic Subgraph Connectivity For Emergency
Planning},
booktitle = {{ESA}},
series = {LIPIcs},
volume = {57},
pages = {48:1--48:11},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016}
}
@inproceedings{DBLP:conf/icalp/CheungGH16,
author = {Yun Kuen Cheung and
Gramoz Goranci and
Monika Henzinger},
title = {Graph Minors for Preserving Terminal Distances Approximately - Lower
and Upper Bounds},
booktitle = {{ICALP}},
series = {LIPIcs},
volume = {55},
pages = {131:1--131:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016}
}
@inproceedings{DBLP:conf/lics/ChatterjeeDHL16,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Veronika Loitzenbauer},
title = {Model and Objective Separation with Conditional Lower Bounds: Disjunction
is Harder than Conjunction},
booktitle = {{LICS}},
pages = {197--206},
publisher = {{ACM}},
year = {2016}
}
@inproceedings{DBLP:conf/mfcs/ChatterjeeDHL16,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Veronika Loitzenbauer},
title = {Conditionally Optimal Algorithms for Generalized B{\"{u}}chi
Games},
booktitle = {{MFCS}},
series = {LIPIcs},
volume = {58},
pages = {25:1--25:15},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016}
}
@inproceedings{DBLP:conf/stoc/BhattacharyaHN16,
author = {Sayan Bhattacharya and
Monika Henzinger and
Danupon Nanongkai},
title = {New deterministic approximation algorithms for fully dynamic matching},
booktitle = {{STOC}},
pages = {398--411},
publisher = {{ACM}},
year = {2016}
}
@inproceedings{DBLP:conf/stoc/HenzingerKN16,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {A deterministic almost-tight distributed algorithm for approximating
single-source shortest paths},
booktitle = {{STOC}},
pages = {489--498},
publisher = {{ACM}},
year = {2016}
}
@incollection{DBLP:reference/algo/HenzingerKN16,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrierand
Derandomization},
booktitle = {Encyclopedia of Algorithms},
pages = {600--602},
year = {2016}
}
@incollection{DBLP:reference/algo/Henzinger16,
author = {Monika Henzinger},
title = {PageRank Algorithm},
booktitle = {Encyclopedia of Algorithms},
pages = {1509--1511},
year = {2016}
}
@article{DBLP:journals/corr/ChatterjeeDHL16,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Veronika Loitzenbauer},
title = {Model and Objective Separation with Conditional Lower Bounds: Disjunction
is Harder than Conjunction},
journal = {CoRR},
volume = {abs/1602.02670},
year = {2016}
}
@article{DBLP:journals/corr/BhattacharyaHI16,
author = {Sayan Bhattacharya and
Monika Henzinger and
Giuseppe F. Italiano},
title = {Design of Dynamic Algorithms via Primal-Dual Method},
journal = {CoRR},
volume = {abs/1604.05337},
year = {2016}
}
@article{DBLP:journals/corr/Ben-ZwiHL16,
author = {Oren Ben{-}Zwi and
Monika Henzinger and
Veronika Loitzenbauer},
title = {Ad Exchange: Envy-Free Auctions with Mediators},
journal = {CoRR},
volume = {abs/1604.05562},
year = {2016}
}
@article{DBLP:journals/corr/DvorakH16,
author = {Wolfgang Dvor{\'{a}}k and
Monika Henzinger},
title = {Online Ad Assignment with an Ad Exchange},
journal = {CoRR},
volume = {abs/1604.05603},
year = {2016}
}
@article{DBLP:journals/corr/BhattacharyaHN16,
author = {Sayan Bhattacharya and
Monika Henzinger and
Danupon Nanongkai},
title = {New Deterministic Approximation Algorithms for Fully Dynamic Matching},
journal = {CoRR},
volume = {abs/1604.05765},
year = {2016}
}
@article{DBLP:journals/corr/ChatterjeeHKK16,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Polynomial-Time Algorithms for Energy Games with Special Weight Structures},
journal = {CoRR},
volume = {abs/1604.08234},
year = {2016}
}
@article{DBLP:journals/corr/CheungGH16,
author = {Yun Kuen Cheung and
Gramoz Goranci and
Monika Henzinger},
title = {Graph Minors for Preserving Terminal Distances Approximately - Lower
and Upper Bounds},
journal = {CoRR},
volume = {abs/1604.08342},
year = {2016}
}
@article{DBLP:journals/corr/ChatterjeeDHL16a,
author = {Krishnendu Chatterjee and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Veronika Loitzenbauer},
title = {Conditionally Optimal Algorithms for Generalized B{\"{u}}chi
Games},
journal = {CoRR},
volume = {abs/1607.05850},
year = {2016}
}
@article{DBLP:journals/corr/BhattacharyaCH16,
author = {Sayan Bhattacharya and
Deeparnab Chakrabarty and
Monika Henzinger},
title = {Deterministic Fully Dynamic Approximate Vertex Cover and Fractional
Matching in {\textdollar}O(1){\textdollar} Amortized Update Time},
journal = {CoRR},
volume = {abs/1611.00198},
year = {2016}
}
@article{DBLP:journals/corr/Henzinger016,
author = {Monika Henzinger and
Stefan Neumann},
title = {Incremental and Fully Dynamic Subgraph Connectivity For Emergency
Planning},
journal = {CoRR},
volume = {abs/1611.05248},
year = {2016}
}
@article{DBLP:journals/corr/DvorakHW16,
author = {Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
David P. Williamson},
title = {Maximizing a Submodular Function with Viability Constraints},
journal = {CoRR},
volume = {abs/1611.05753},
year = {2016}
}
@article{DBLP:journals/corr/GoranciHT16,
author = {Gramoz Goranci and
Monika Henzinger and
Mikkel Thorup},
title = {Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time},
journal = {CoRR},
volume = {abs/1611.06500},
year = {2016}
}
@article{DBLP:journals/corr/HenzingerKN16,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Improved Algorithms for Decremental Single-Source Reachability on
Directed Graphs},
journal = {CoRR},
volume = {abs/1612.03856},
year = {2016}
}
@article{DBLP:journals/tcs/HenzingerL15,
author = {Monika Henzinger and
Veronika Loitzenbauer},
title = {Truthful unit-demand auctions with budgets revisited},
journal = {Theor. Comput. Sci.},
volume = {573},
pages = {1--15},
year = {2015}
}
@article{DBLP:journals/teco/DuttingHW15,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Ingmar Weber},
title = {An Expressive Mechanism for Auctions on the Web},
journal = {{ACM} Trans. Economics and Comput.},
volume = {4},
number = {1},
pages = {1:1--1:34},
year = {2015}
}
@article{DBLP:journals/teco/Colini-Baldeschi15,
author = {Riccardo Colini{-}Baldeschi and
Stefano Leonardi and
Monika Henzinger and
Martin Starnberger},
title = {On Multiple Keyword Sponsored Search Auctions with Budgets},
journal = {{ACM} Trans. Economics and Comput.},
volume = {4},
number = {1},
pages = {2:1--2:34},
year = {2015}
}
@article{DBLP:journals/teco/DuttingHS15,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Martin Starnberger},
title = {Auctions for Heterogeneous Items and Budget Limits},
journal = {{ACM} Trans. Economics and Comput.},
volume = {4},
number = {1},
pages = {4:1--4:17},
year = {2015}
}
@inproceedings{DBLP:conf/icalp/BhattacharyaHI15,
author = {Sayan Bhattacharya and
Monika Henzinger and
Giuseppe F. Italiano},
title = {Design of Dynamic Algorithms via Primal-Dual Method},
booktitle = {{ICALP} {(1)}},
series = {Lecture Notes in Computer Science},
volume = {9134},
pages = {206--218},
publisher = {Springer},
year = {2015}
}
@inproceedings{DBLP:conf/icalp/HenzingerKL15,
author = {Monika Henzinger and
Sebastian Krinninger and
Veronika Loitzenbauer},
title = {Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic
Time},
booktitle = {{ICALP} {(1)}},
series = {Lecture Notes in Computer Science},
volume = {9134},
pages = {713--724},
publisher = {Springer},
year = {2015}
}
@inproceedings{DBLP:conf/icalp/HenzingerKN15,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Improved Algorithms for Decremental Single-Source Reachability on
Directed Graphs},
booktitle = {{ICALP} {(1)}},
series = {Lecture Notes in Computer Science},
volume = {9134},
pages = {725--736},
publisher = {Springer},
year = {2015}
}
@inproceedings{DBLP:conf/lics/ChatterjeeHL15,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Veronika Loitzenbauer},
title = {Improved Algorithms for One-Pair and k-Pair Streett Objectives},
booktitle = {{LICS}},
pages = {269--280},
publisher = {{IEEE} Computer Society},
year = {2015}
}
@inproceedings{DBLP:conf/soda/BhattacharyaHI15,
author = {Sayan Bhattacharya and
Monika Henzinger and
Giuseppe F. Italiano},
title = {Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching},
booktitle = {{SODA}},
pages = {785--804},
publisher = {{SIAM}},
year = {2015}
}
@inproceedings{DBLP:conf/stacs/BhattacharyaDHS15,
author = {Sayan Bhattacharya and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Martin Starnberger},
title = {Welfare Maximization with Friends-of-Friends Network Externalities},
booktitle = {{STACS}},
series = {LIPIcs},
volume = {30},
pages = {90--102},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2015}
}
@inproceedings{DBLP:conf/stoc/HenzingerKNS15,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai and
Thatchaphol Saranurak},
title = {Unifying and Strengthening Hardness for Dynamic Problems via the Online
Matrix-Vector Multiplication Conjecture},
booktitle = {{STOC}},
pages = {21--30},
publisher = {{ACM}},
year = {2015}
}
@inproceedings{DBLP:conf/stoc/BhattacharyaHNT15,
author = {Sayan Bhattacharya and
Monika Henzinger and
Danupon Nanongkai and
Charalampos E. Tsourakakis},
title = {Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs
on One-Pass Dynamic Streams},
booktitle = {{STOC}},
pages = {173--182},
publisher = {{ACM}},
year = {2015}
}
@inproceedings{DBLP:conf/wine/Ben-ZwiHL15,
author = {Oren Ben{-}Zwi and
Monika Henzinger and
Veronika Loitzenbauer},
title = {Ad Exchange: Envy-Free Auctions with Mediators},
booktitle = {{WINE}},
series = {Lecture Notes in Computer Science},
volume = {9470},
pages = {104--117},
publisher = {Springer},
year = {2015}
}
@inproceedings{DBLP:conf/wine/CheungHHS15,
author = {Yun Kuen Cheung and
Monika Henzinger and
Martin Hoefer and
Martin Starnberger},
title = {Combinatorial Auctions with Conflict-Based Externalities},
booktitle = {{WINE}},
series = {Lecture Notes in Computer Science},
volume = {9470},
pages = {230--243},
publisher = {Springer},
year = {2015}
}
@article{DBLP:journals/corr/BhattacharyaHNT15,
author = {Sayan Bhattacharya and
Monika Henzinger and
Danupon Nanongkai and
Charalampos E. Tsourakakis},
title = {Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs
on One-Pass Dynamic Streams},
journal = {CoRR},
volume = {abs/1504.02268},
year = {2015}
}
@article{DBLP:journals/corr/HenzingerKN15,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {An Almost-Tight Distributed Algorithm for Computing Single-Source
Shortest Paths},
journal = {CoRR},
volume = {abs/1504.07056},
year = {2015}
}
@article{DBLP:journals/corr/HenzingerKN15a,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Sublinear-Time Decremental Algorithms for Single-Source Reachability
and Shortest Paths on Directed Graphs},
journal = {CoRR},
volume = {abs/1504.07959},
year = {2015}
}
@article{DBLP:journals/corr/CheungHHS15,
author = {Yun Kuen Cheung and
Monika Henzinger and
Martin Hoefer and
Martin Starnberger},
title = {Combinatorial Auctions with Conflict-Based Externalities},
journal = {CoRR},
volume = {abs/1509.09147},
year = {2015}
}
@article{DBLP:journals/corr/HenzingerKNS15,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai and
Thatchaphol Saranurak},
title = {Unifying and Strengthening Hardness for Dynamic Problems via the Online
Matrix-Vector Multiplication Conjecture},
journal = {CoRR},
volume = {abs/1511.06773},
year = {2015}
}
@article{DBLP:journals/corr/HenzingerKN15b,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially
Dynamic Networks},
journal = {CoRR},
volume = {abs/1512.08147},
year = {2015}
}
@article{DBLP:journals/corr/HenzingerKN15c,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear
Total Update Time},
journal = {CoRR},
volume = {abs/1512.08148},
year = {2015}
}
@article{DBLP:journals/algorithmica/ChatterjeeHKN14,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Polynomial-Time Algorithms for Energy Games with Special Weight Structures},
journal = {Algorithmica},
volume = {70},
number = {3},
pages = {457--492},
year = {2014}
}
@article{DBLP:journals/jacm/ChatterjeeH14,
author = {Krishnendu Chatterjee and
Monika Henzinger},
title = {Efficient and Dynamic Algorithms for Alternating B{\"{u}}chi
Games and Maximal End-Component Decomposition},
journal = {J. {ACM}},
volume = {61},
number = {3},
pages = {15:1--15:40},
year = {2014}
}
@article{DBLP:journals/tcs/ChatterjeeHKLR14,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Sebastian Krinninger and
Veronika Loitzenbauer and
Michael A. Raskin},
title = {Approximating the minimum cycle mean},
journal = {Theor. Comput. Sci.},
volume = {547},
pages = {104--116},
year = {2014}
}
@inproceedings{DBLP:conf/esa/CharikarHN14,
author = {Moses Charikar and
Monika Henzinger and
Huy L. Nguyen},
title = {Online Bipartite Matching with Decomposable Weights},
booktitle = {{ESA}},
series = {Lecture Notes in Computer Science},
volume = {8737},
pages = {260--271},
publisher = {Springer},
year = {2014}
}
@inproceedings{DBLP:conf/focs/HenzingerKN14,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear
Total Update Time},
booktitle = {{FOCS}},
pages = {146--155},
publisher = {{IEEE} Computer Society},
year = {2014}
}
@inproceedings{DBLP:conf/soda/HenzingerKN14,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {A Subquadratic-Time Algorithm for Decremental Single-Source Shortest
Paths},
booktitle = {{SODA}},
pages = {1053--1072},
publisher = {{SIAM}},
year = {2014}
}
@inproceedings{DBLP:conf/stoc/HenzingerKN14,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Sublinear-time decremental algorithms for single-source reachability
and shortest paths on directed graphs},
booktitle = {{STOC}},
pages = {674--683},
publisher = {{ACM}},
year = {2014}
}
@inproceedings{DBLP:conf/waoa/DvorakH14,
author = {Wolfgang Dvor{\'{a}}k and
Monika Henzinger},
title = {Online Ad Assignment with an Ad Exchange},
booktitle = {{WAOA}},
series = {Lecture Notes in Computer Science},
volume = {8952},
pages = {156--167},
publisher = {Springer},
year = {2014}
}
@inproceedings{DBLP:conf/wine/CiglerDHS14,
author = {Ludek Cigler and
Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
Martin Starnberger},
title = {Limiting Price Discrimination when Selling Products with Positive
Network Externalities},
booktitle = {{WINE}},
series = {Lecture Notes in Computer Science},
volume = {8877},
pages = {44--57},
publisher = {Springer},
year = {2014}
}
@article{DBLP:journals/corr/CharikarHN14,
author = {Moses Charikar and
Monika Henzinger and
Huy L. Nguyen},
title = {Online Bipartite Matching with Decomposable Weights},
journal = {CoRR},
volume = {abs/1409.2139},
year = {2014}
}
@article{DBLP:journals/corr/ChatterjeeHL14,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Veronika Loitzenbauer},
title = {Improved Algorithms for One-Pair and k-Pair Streett Objectives},
journal = {CoRR},
volume = {abs/1410.0833},
year = {2014}
}
@article{DBLP:journals/corr/BhattacharyaHI14,
author = {Sayan Bhattacharya and
Monika Henzinger and
Giuseppe F. Italiano},
title = {Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching},
journal = {CoRR},
volume = {abs/1412.1318},
year = {2014}
}
@article{DBLP:journals/corr/HenzingerKL14,
author = {Monika Henzinger and
Sebastian Krinninger and
Veronika Loitzenbauer},
title = {Finding 2-edge and 2-vertex strongly connected components in quadratic
time},
journal = {CoRR},
volume = {abs/1412.6466},
year = {2014}
}
@article{DBLP:journals/fmsd/ChatterjeeHJS13,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Manas Joglekar and
Nisarg Shah},
title = {Symbolic algorithms for qualitative analysis of Markov decision processes
with B{\"{u}}chi objectives},
journal = {Formal Methods Syst. Des.},
volume = {42},
number = {3},
pages = {301--327},
year = {2013}
}
@article{DBLP:journals/iandc/AcetoHS13,
author = {Luca Aceto and
Monika Henzinger and
Jir{\'{\i}} Sgall},
title = {38th International Colloquium on Automata, Languages and Programming},
journal = {Inf. Comput.},
volume = {222},
pages = {1},
year = {2013}
}
@article{DBLP:journals/ipl/DuttingHW13,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Ingmar Weber},
title = {Sponsored search, market equilibria, and the Hungarian Method},
journal = {Inf. Process. Lett.},
volume = {113},
number = {3},
pages = {67--73},
year = {2013}
}
@article{DBLP:journals/tcs/DuttingHW13,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Ingmar Weber},
title = {Bidder optimal assignments for general utilities},
journal = {Theor. Comput. Sci.},
volume = {478},
pages = {22--32},
year = {2013}
}
@article{DBLP:journals/tweb/BaykanHW13,
author = {Eda Baykan and
Monika Henzinger and
Ingmar Weber},
title = {A Comprehensive Study of Techniques for URL-Based Web Page Language
Classification},
journal = {{ACM} Trans. Web},
volume = {7},
number = {1},
pages = {3:1--3:37},
year = {2013}
}
@inproceedings{DBLP:conf/esa/DvorakHW13,
author = {Wolfgang Dvor{\'{a}}k and
Monika Henzinger and
David P. Williamson},
title = {Maximizing a Submodular Function with Viability Constraints},
booktitle = {{ESA}},
series = {Lecture Notes in Computer Science},
volume = {8125},
pages = {409--420},
publisher = {Springer},
year = {2013}
}
@inproceedings{DBLP:conf/focs/HenzingerKN13,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier
and Derandomization},
booktitle = {{FOCS}},
pages = {538--547},
publisher = {{IEEE} Computer Society},
year = {2013}
}
@inproceedings{DBLP:conf/icalp/HenzingerKN13,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially
Dynamic Networks},
booktitle = {{ICALP} {(2)}},
series = {Lecture Notes in Computer Science},
volume = {7966},
pages = {607--619},
publisher = {Springer},
year = {2013}
}
@inproceedings{DBLP:conf/wine/DuttingHS13,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Martin Starnberger},
title = {Valuation Compressions in VCG-Based Combinatorial Auctions},
booktitle = {{WINE}},
series = {Lecture Notes in Computer Science},
volume = {8289},
pages = {146--159},
publisher = {Springer},
year = {2013}
}
@inproceedings{DBLP:journals/corr/ChatterjeeHKL13,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Sebastian Krinninger and
Veronika Loitzenbauer},
title = {Approximating the minimum cycle mean},
booktitle = {GandALF},
series = {{EPTCS}},
volume = {119},
pages = {136--149},
year = {2013}
}
@article{DBLP:journals/corr/HenzingerKN13,
author = {Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier
and Derandomization},
journal = {CoRR},
volume = {abs/1308.0776},
year = {2013}
}
@article{DBLP:journals/corr/DuettingHS13,
author = {Paul Duetting and
Monika Henzinger and
Martin Starnberger},
title = {Valuation Compressions in VCG-Based Combinatorial Auctions},
journal = {CoRR},
volume = {abs/1310.3153},
year = {2013}
}
@article{DBLP:journals/eatcs/Henzinger12,
author = {Monika Henzinger},
title = {The Presburger Award 2013: Call for Nominations},
journal = {Bull. {EATCS}},
volume = {108},
pages = {22--23},
year = {2012}
}
@inproceedings{DBLP:conf/cikm/DuttingHW12,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Ingmar Weber},
title = {Maximizing revenue from strategic recommendations under decaying trust},
booktitle = {{CIKM}},
pages = {2283--2286},
publisher = {{ACM}},
year = {2012}
}
@inproceedings{DBLP:conf/esa/ChatterjeeHKN12,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai},
title = {Polynomial-Time Algorithms for Energy Games with Special Weight Structures},
booktitle = {{ESA}},
series = {Lecture Notes in Computer Science},
volume = {7501},
pages = {301--312},
publisher = {Springer},
year = {2012}
}
@inproceedings{DBLP:conf/icalp/BaldeschiHLS12,
author = {Riccardo Colini{-}Baldeschi and
Monika Henzinger and
Stefano Leonardi and
Martin Starnberger},
title = {On Multiple Keyword Sponsored Search Auctions with Budgets},
booktitle = {{ICALP} {(2)}},
series = {Lecture Notes in Computer Science},
volume = {7392},
pages = {1--12},
publisher = {Springer},
year = {2012}
}
@inproceedings{DBLP:conf/soda/ChatterjeeH12,
author = {Krishnendu Chatterjee and
Monika Henzinger},
title = {An \emph{O}(\emph{n}\({}^{\mbox{2}}\)) time algorithm for alternating
B{\"{u}}chi games},
booktitle = {{SODA}},
pages = {1386--1399},
publisher = {{SIAM}},
year = {2012}
}
@inproceedings{DBLP:conf/wine/DuttingHS12,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Martin Starnberger},
title = {Auctions with Heterogeneous Items and Budget Limits},
booktitle = {{WINE}},
series = {Lecture Notes in Computer Science},
volume = {7695},
pages = {44--57},
publisher = {Springer},
year = {2012}
}
@article{DBLP:journals/corr/abs-1209-6448,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Martin Starnberger},
title = {Auctions with Heterogeneous Items and Budget Limits},
journal = {CoRR},
volume = {abs/1209.6448},
year = {2012}
}
@article{DBLP:journals/ipl/DuttingHW11,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Ingmar Weber},
title = {Offline file assignments for online load balancing},
journal = {Inf. Process. Lett.},
volume = {111},
number = {4},
pages = {178--183},
year = {2011}
}
@article{DBLP:journals/tweb/BaykanHMW11,
author = {Eda Baykan and
Monika Henzinger and
Ludmila Marian and
Ingmar Weber},
title = {A Comprehensive Study of Features and Algorithms for URL-Based Topic
Classification},
journal = {{ACM} Trans. Web},
volume = {5},
number = {3},
pages = {15:1--15:29},
year = {2011}
}
@inproceedings{DBLP:conf/cav/ChatterjeeHJS11,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Manas Joglekar and
Nisarg Shah},
title = {Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes
with B{\"{u}}chi Objectives},
booktitle = {{CAV}},
series = {Lecture Notes in Computer Science},
volume = {6806},
pages = {260--276},
publisher = {Springer},
year = {2011}
}
@inproceedings{DBLP:conf/esa/HenzingerV11,
author = {Monika Henzinger and
Angelina Vidali},
title = {Multi-parameter Mechanism Design under Budget and Matroid Constraints},
booktitle = {{ESA}},
series = {Lecture Notes in Computer Science},
volume = {6942},
pages = {192--202},
publisher = {Springer},
year = {2011}
}
@inproceedings{DBLP:conf/soda/ChatterjeeH11,
author = {Krishnendu Chatterjee and
Monika Henzinger},
title = {Faster and Dynamic Algorithms for Maximal End-Component Decomposition
and Related Graph Problems in Probabilistic Verification},
booktitle = {{SODA}},
pages = {1318--1336},
publisher = {{SIAM}},
year = {2011}
}
@inproceedings{DBLP:conf/www/DuttingHW11,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Ingmar Weber},
title = {An expressive mechanism for auctions on the web},
booktitle = {{WWW}},
pages = {127--136},
publisher = {{ACM}},
year = {2011}
}
@proceedings{DBLP:conf/icalp/2011-1,
editor = {Luca Aceto and
Monika Henzinger and
Jir{\'{\i}} Sgall},
title = {Automata, Languages and Programming - 38th International Colloquium,
{ICALP} 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {6755},
publisher = {Springer},
year = {2011}
}
@proceedings{DBLP:conf/icalp/2011-2,
editor = {Luca Aceto and
Monika Henzinger and
Jir{\'{\i}} Sgall},
title = {Automata, Languages and Programming - 38th International Colloquium,
{ICALP} 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part
{II}},
series = {Lecture Notes in Computer Science},
volume = {6756},
publisher = {Springer},
year = {2011}
}
@article{DBLP:journals/corr/abs-1104-3348,
author = {Krishnendu Chatterjee and
Monika Henzinger and
Manas Joglekar and
Nisarg Shah},
title = {Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes
with B{\"{u}}chi Objectives},
journal = {CoRR},
volume = {abs/1104.3348},
year = {2011}
}
@article{DBLP:journals/corr/abs-1109-5018,
author = {Krishnendu Chatterjee and
Monika Henzinger},
title = {An O(n{\^{}}2) Time Algorithm for Alternating B{\"{u}}chi Games},
journal = {CoRR},
volume = {abs/1109.5018},
year = {2011}
}
@article{DBLP:journals/corr/abs-1112-6361,
author = {Riccardo Colini{-}Baldeschi and
Monika Henzinger and
Stefano Leonardi and
Martin Starnberger},
title = {On Multiple Round Sponsored Search Auctions with Budgets},
journal = {CoRR},
volume = {abs/1112.6361},
year = {2011}
}
@article{DBLP:journals/scientometrics/HenzingerSW10,
author = {Monika Henzinger and
Jacob Su{\~{n}}ol and
Ingmar Weber},
title = {The stability of the \emph{h}-index},
journal = {Scientometrics},
volume = {84},
number = {2},
pages = {465--479},
year = {2010}
}
@inproceedings{DBLP:conf/ciac/DuttingH10,
author = {Paul D{\"{u}}tting and
Monika Henzinger},
title = {Mechanisms for the Marriage and the Assignment Game},
booktitle = {{CIAC}},
series = {Lecture Notes in Computer Science},
volume = {6078},
pages = {6--12},
publisher = {Springer},
year = {2010}
}
@inproceedings{DBLP:conf/esa/FeldmanHKMS10,
author = {Jon Feldman and
Monika Henzinger and
Nitish Korula and
Vahab S. Mirrokni and
Clifford Stein},
title = {Online Stochastic Packing Applied to Display Ad Allocation},
booktitle = {{ESA} {(1)}},
series = {Lecture Notes in Computer Science},
volume = {6346},
pages = {182--194},
publisher = {Springer},
year = {2010}
}
@inproceedings{DBLP:conf/stacs/DuttingHW10,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Ingmar Weber},
title = {Sponsored Search, Market Equilibria, and the Hungarian Method},
booktitle = {{STACS}},
series = {LIPIcs},
volume = {5},
pages = {287--298},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2010}
}
@inproceedings{DBLP:conf/www/DuttingHW10,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Ingmar Weber},
title = {How much is your personal recommendation worth?},
booktitle = {{WWW}},
pages = {1085--1086},
publisher = {{ACM}},
year = {2010}
}
@article{DBLP:journals/corr/abs-1001-5076,
author = {Jon Feldman and
Monika Henzinger and
Nitish Korula and
Vahab S. Mirrokni and
Clifford Stein},
title = {Online Stochastic Ad Allocation: Efficiency and Fairness},
journal = {CoRR},
volume = {abs/1001.5076},
year = {2010}
}
@inproceedings{DBLP:conf/stacs/BaykanHKCK09,
author = {Eda Baykan and
Monika Henzinger and
Stefan F. Keller and
Sebastian De Castelberg and
Markus Kinzler},
title = {A Comparison of Techniques for Sampling Web Pages},
booktitle = {{STACS}},
series = {LIPIcs},
volume = {3},
pages = {13--30},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2009}
}
@inproceedings{DBLP:conf/wine/DuttingHW09,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Ingmar Weber},
title = {Bidder Optimal Assignments for General Utilities},
booktitle = {{WINE}},
series = {Lecture Notes in Computer Science},
volume = {5929},
pages = {575--582},
publisher = {Springer},
year = {2009}
}
@inproceedings{DBLP:conf/www/HamidBCH09,
author = {Ossama Abdel Hamid and
Behshad Behzadi and
Stefan Christoph and
Monika Henzinger},
title = {Detecting the origin of text segments efficiently},
booktitle = {{WWW}},
pages = {61--70},
publisher = {{ACM}},
year = {2009}
}
@inproceedings{DBLP:conf/www/BaykanHMW09,
author = {Eda Baykan and
Monika Henzinger and
Ludmila Marian and
Ingmar Weber},
title = {Purely URL-based topic classification},
booktitle = {{WWW}},
pages = {1109--1110},
publisher = {{ACM}},
year = {2009}
}
@article{DBLP:journals/corr/abs-0902-1604,
author = {Eda Baykan and
Monika Henzinger and
Stefan F. Keller and
Sebastian De Castelberg and
Markus Kinzler},
title = {A Comparison of Techniques for Sampling Web Pages},
journal = {CoRR},
volume = {abs/0902.1604},
year = {2009}
}
@article{DBLP:journals/corr/abs-0911-1619,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Ingmar Weber},
title = {On the Pricing of Recommendations and Recommending Strategically},
journal = {CoRR},
volume = {abs/0911.1619},
year = {2009}
}
@article{DBLP:journals/corr/abs-0912-1934,
author = {Paul D{\"{u}}tting and
Monika Henzinger and
Ingmar Weber},
title = {Sponsored Search, Market Equilibria, and the Hungarian Method},
journal = {CoRR},
volume = {abs/0912.1934},
year = {2009}
}
@article{DBLP:journals/pvldb/BaykanHW08,
author = {Eda Baykan and
Monika Henzinger and
Ingmar Weber},
title = {Web page language identification based on URLs},
journal = {Proc. {VLDB} Endow.},
volume = {1},
number = {1},
pages = {176--187},
year = {2008}
}
@article{DBLP:journals/sigact/AggarwalACEFFHMNPSS08,
author = {Gagan Aggarwal and
Nir Ailon and
Florin Constantin and
Eyal Even{-}Dar and
Jon Feldman and
Gereon Frahling and
Monika Rauch Henzinger and
S. Muthukrishnan and
Noam Nisan and
Martin P{\'{a}}l and
Mark Sandler and
Anastasios Sidiropoulos},
title = {Theory research at Google},
journal = {{SIGACT} News},
volume = {39},
number = {2},
pages = {10--28},
year = {2008}
}
@incollection{DBLP:reference/algo/Henzinger08,
author = {Monika Henzinger},
title = {PageRank Algorithm},
booktitle = {Encyclopedia of Algorithms},
publisher = {Springer},
year = {2008}
}
@inproceedings{DBLP:conf/soda/Henzinger07,
author = {Monika Henzinger},
title = {Combinatorial algorithms for web search engines: three success stories},
booktitle = {{SODA}},
pages = {1022--1026},
publisher = {{SIAM}},
year = {2007}
}
@inproceedings{DBLP:conf/sigir/Henzinger06,
author = {Monika Henzinger},
title = {Finding near-duplicate web pages: a large-scale evaluation of algorithms},
booktitle = {{SIGIR}},
pages = {284--291},
publisher = {{ACM}},
year = {2006}
}
@article{DBLP:journals/jal/GoelHP05,
author = {Ashish Goel and
Monika Rauch Henzinger and
Serge A. Plotkin},
title = {An online throughput-competitive algorithm for multicast routing and
admission control},
journal = {J. Algorithms},
volume = {55},
number = {1},
pages = {1--20},
year = {2005}
}
@article{DBLP:journals/www/HenzingerCMB05,
author = {Monika Henzinger and
Bay{-}Wei Chang and
Brian Milch and
Sergey Brin},
title = {Query-Free News Search},
journal = {World Wide Web},
volume = {8},
number = {2},
pages = {101--126},
year = {2005}
}
@inproceedings{DBLP:conf/ht/Henzinger05,
author = {Monika Henzinger},
title = {Hyperlink analysis on the world wide web},
booktitle = {Hypertext},
pages = {1--3},
publisher = {{ACM}},
year = {2005}
}
@inproceedings{DBLP:conf/drr/Henzinger04,
author = {Monika Henzinger},
title = {The past, present, and future of web information retrieval},
booktitle = {{DRR}},
series = {{SPIE} Proceedings},
volume = {5296},
pages = {23--26},
publisher = {{SPIE}},
year = {2004}
}
@inproceedings{DBLP:conf/esa/Henzinger04,
author = {Monika Henzinger},
title = {Algorithmic Aspects of Web Search Engines},
booktitle = {{ESA}},
series = {Lecture Notes in Computer Science},
volume = {3221},
pages = {3},
publisher = {Springer},
year = {2004}
}
@inproceedings{DBLP:conf/icalp/Henzinger04,
author = {Monika Henzinger},
title = {The Past, Present, and Future of Web Search Engines p},
booktitle = {{ICALP}},
series = {Lecture Notes in Computer Science},
volume = {3142},
pages = {3},
publisher = {Springer},
year = {2004}
}
@inproceedings{DBLP:conf/pods/Henzinger04,
author = {Monika Henzinger},
title = {The Past, Present and Future of Web Information Retrieval},
booktitle = {{PODS}},
pages = {46},
publisher = {{ACM}},
year = {2004}
}
@incollection{DBLP:reference/crc/Henzinger04,
author = {Monika Henzinger},
title = {Data Structures in Web Information Retrieval},
booktitle = {Handbook of Data Structures and Applications},
publisher = {Chapman and Hall/CRC},
year = {2004}
}
@article{DBLP:journals/im/Henzinger03,
author = {Monika Rauch Henzinger},
title = {Algorithmic Challenges in Web Search Engines},
journal = {Internet Math.},
volume = {1},
number = {1},
pages = {115--123},
year = {2003}
}
@article{DBLP:journals/jal/GoelHPT03,
author = {Ashish Goel and
Monika Rauch Henzinger and
Serge A. Plotkin and
{\'{E}}va Tardos},
title = {Scheduling data transfers in a network and the set scheduling problem},
journal = {J. Algorithms},
volume = {48},
number = {2},
pages = {314--332},
year = {2003}
}
@article{DBLP:journals/jcss/HenzingerL03,
author = {Monika Rauch Henzinger and
Stefano Leonardi},
title = {Scheduling multicasts on unit-capacity trees and meshes},
journal = {J. Comput. Syst. Sci.},
volume = {66},
number = {3},
pages = {567--611},
year = {2003}
}
@inproceedings{DBLP:conf/ijcai/HenzingerMS03,
author = {Monika Rauch Henzinger and
Rajeev Motwani and
Craig Silverstein},
title = {Challenges in Web Search Engines},
booktitle = {{IJCAI}},
pages = {1573--1579},
publisher = {Morgan Kaufmann},
year = {2003}
}
@inproceedings{DBLP:conf/schule/Henzinger03,
author = {Monika Henzinger},
title = {The Past, Present and Future of Web Information Retrieval},
booktitle = {{INFOS}},
series = {{LNI}},
volume = {{P-32}},
pages = {52},
publisher = {{GI}},
year = {2003}
}
@inproceedings{DBLP:conf/www/HenzingerCMB03,
author = {Monika Henzinger and
Bay{-}Wei Chang and
Brian Milch and
Sergey Brin},
title = {Query-free news search},
booktitle = {{WWW}},
pages = {1--10},
publisher = {{ACM}},
year = {2003}
}
@article{DBLP:journals/sigir/HenzingerMS02,
author = {Monika Rauch Henzinger and
Rajeev Motwani and
Craig Silverstein},
title = {Challenges in web search engines},
journal = {{SIGIR} Forum},
volume = {36},
number = {2},
pages = {11--22},
year = {2002}
}
@inproceedings{DBLP:conf/cluster/Henzinger02,
author = {Monika Henzinger},
title = {Indexing the Web - {A} Challenge for Supercomputers},
booktitle = {{CLUSTER}},
pages = {343},
publisher = {{IEEE} Computer Society},
year = {2002}
}
@article{DBLP:journals/internet/Henzinger01,
author = {Monika Rauch Henzinger},
title = {Hyperlink Analysis for the Web},
journal = {{IEEE} Internet Comput.},
volume = {5},
number = {1},
pages = {45--50},
year = {2001}
}
@article{DBLP:journals/siamcomp/HenzingerK01,
author = {Monika Rauch Henzinger and
Valerie King},
title = {Maintaining Minimum Spanning Forests in Dynamic Graphs},
journal = {{SIAM} J. Comput.},
volume = {31},
number = {2},
pages = {364--374},
year = {2001}
}
@inproceedings{DBLP:conf/icdm/BharatCHR01,
author = {Krishna Bharat and
Bay{-}Wei Chang and
Monika Henzinger and
Matthias Ruhl},
title = {Who Links to Whom: Mining Linkage between Web Sites},
booktitle = {{ICDM}},
pages = {51--58},
publisher = {{IEEE} Computer Society},
year = {2001}
}
@article{DBLP:journals/cn/HenzingerHMN00,
author = {Monika Rauch Henzinger and
Allan Heydon and
Michael Mitzenmacher and
Marc Najork},
title = {On near-uniform {URL} sampling},
journal = {Comput. Networks},
volume = {33},
number = {1-6},
pages = {295--308},
year = {2000}
}
@article{DBLP:journals/debu/Henzinger00,
author = {Monika Rauch Henzinger},
title = {Link Analysis in Web Information Retrieval},
journal = {{IEEE} Data Eng. Bull.},
volume = {23},
number = {3},
pages = {3--8},
year = {2000}
}
@article{DBLP:journals/debu/BharatBDH00,
author = {Krishna Bharat and
Andrei Z. Broder and
Jeffrey Dean and
Monika Rauch Henzinger},
title = {A Comparison of Techniques to Find Mirrored Hosts on the {WWW}},
journal = {{IEEE} Data Eng. Bull.},
volume = {23},
number = {4},
pages = {21--26},
year = {2000}
}
@article{DBLP:journals/jal/HenzingerRG00,
author = {Monika Rauch Henzinger and
Satish Rao and
Harold N. Gabow},
title = {Computing Vertex Connectivity: New Bounds from Old Techniques},
journal = {J. Algorithms},
volume = {34},
number = {2},
pages = {222--250},
year = {2000}
}
@article{DBLP:journals/jasis/BharatBDH00,
author = {Krishna Bharat and
Andrei Z. Broder and
Jeffrey Dean and
Monika Rauch Henzinger},
title = {A comparison of techniques to find mirrored hosts on the {WWW}},
journal = {J. Am. Soc. Inf. Sci.},
volume = {51},
number = {12},
pages = {1114--1122},
year = {2000}
}
@article{DBLP:journals/siamcomp/AlbersH00,
author = {Susanne Albers and
Monika Rauch Henzinger},
title = {Exploring Unknown Environments},
journal = {{SIAM} J. Comput.},
volume = {29},
number = {4},
pages = {1164--1188},
year = {2000}
}
@article{DBLP:journals/siamcomp/Henzinger00,
author = {Monika Rauch Henzinger},
title = {Improved Data Structures for Fully Dynamic Biconnectivity},
journal = {{SIAM} J. Comput.},
volume = {29},
number = {6},
pages = {1761--1815},
year = {2000}
}
@inproceedings{DBLP:conf/esa/Henzinger00,
author = {Monika Henzinger},
title = {Web Information Retrieval - an Algorithmic Perspective},
booktitle = {{ESA}},
series = {Lecture Notes in Computer Science},
volume = {1879},
pages = {1--8},
publisher = {Springer},
year = {2000}
}
@inproceedings{DBLP:conf/icde/Henzinger00,
author = {Monika Rauch Henzinger},
title = {Web Information Retrieval},
booktitle = {{ICDE}},
pages = {693},
publisher = {{IEEE} Computer Society},
year = {2000}
}
@article{DBLP:journals/algorithmica/HenzingerKW99,
author = {Monika Rauch Henzinger and
Valerie King and
Tandy J. Warnow},
title = {Constructing a Tree from Homeomorphic Subtrees, with Applications
to Computational Evolutionary Biology},
journal = {Algorithmica},
volume = {24},
number = {1},
pages = {1--13},
year = {1999}
}
@article{DBLP:journals/cn/HenzingerHMN99,
author = {Monika Rauch Henzinger and
Allan Heydon and
Michael Mitzenmacher and
Marc Najork},
title = {Measuring Index Quality Using Random Walks on the Web},
journal = {Comput. Networks},
volume = {31},
number = {11-16},
pages = {1291--1303},
year = {1999}
}
@article{DBLP:journals/cn/DeanH99,
author = {Jeffrey Dean and
Monika Rauch Henzinger},
title = {Finding Related Pages in the World Wide Web},
journal = {Comput. Networks},
volume = {31},
number = {11-16},
pages = {1467--1479},
year = {1999}
}
@article{DBLP:journals/jacm/HenzingerK99,
author = {Monika Rauch Henzinger and
Valerie King},
title = {Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time
per Operation},
journal = {J. {ACM}},
volume = {46},
number = {4},
pages = {502--516},
year = {1999}
}
@article{DBLP:journals/sigir/SilversteinHMM99,
author = {Craig Silverstein and
Monika Henzinger and
Hannes Marais and
Michael Moricz},
title = {Analysis of a Very Large Web Search Engine Query Log},
journal = {{SIGIR} Forum},
volume = {33},
number = {1},
pages = {6--12},
year = {1999}
}
@inproceedings{DBLP:conf/dl/BharatBDH99,
author = {Krishna Bharat and
Andrei Z. Broder and
Jeffrey Dean and
Monika Rauch Henzinger},
title = {A Comparison of Techniques to Find Mirrored Hosts on the {WWW}},
booktitle = {{WOWS}},
pages = {2--12},
year = {1999}
}
@inproceedings{DBLP:conf/soda/HenzingerL99,
author = {Monika Rauch Henzinger and
Stefano Leonardi},
title = {Scheduling Multicasts on Unit-Capacity Trees and Meshes},
booktitle = {{SODA}},
pages = {438--447},
publisher = {{ACM/SIAM}},
year = {1999}
}
@inproceedings{DBLP:conf/stoc/GoelHPT99,
author = {Ashish Goel and
Monika Rauch Henzinger and
Serge A. Plotkin and
{\'{E}}va Tardos},
title = {Scheduling Data Transfers in a Network and the Set Scheduling Problem},
booktitle = {{STOC}},
pages = {189--197},
publisher = {{ACM}},
year = {1999}
}
@article{DBLP:journals/algorithmica/AlbertsH98,
author = {David Alberts and
Monika Rauch Henzinger},
title = {Average-Case Analysis of Dynamic Graph Algorithms},
journal = {Algorithmica},
volume = {20},
number = {1},
pages = {31--60},
year = {1998}
}
@article{DBLP:journals/algorithmica/HenzingerF98,
author = {Monika Rauch Henzinger and
Michael L. Fredman},
title = {Lower Bounds for Fully Dynamic Connectivity Problems in Graphs},
journal = {Algorithmica},
volume = {22},
number = {3},
pages = {351--362},
year = {1998}
}
@article{DBLP:journals/cn/BharatBHKV98,
author = {Krishna Bharat and
Andrei Z. Broder and
Monika Henzinger and
Puneet Kumar and
Suresh Venkatasubramanian},
title = {The Connectivity Server: Fast Access to Linkage Information on the
Web},
journal = {Comput. Networks},
volume = {30},
number = {1-7},
pages = {469--477},
year = {1998}
}
@inproceedings{DBLP:conf/dimacs/HenzingerRR98,
author = {Monika Rauch Henzinger and
Prabhakar Raghavan and
Sridhar Rajagopalan},
title = {Computing on data streams},
booktitle = {External Memory Algorithms},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {50},
pages = {107--118},
publisher = {{DIMACS/AMS}},
year = {1998}
}
@inproceedings{DBLP:conf/focs/BroderH98,
author = {Andrei Z. Broder and
Monika Rauch Henzinger},
title = {Information Retrieval on the Web},
booktitle = {{FOCS}},
pages = {6},
publisher = {{IEEE} Computer Society},
year = {1998}
}
@inproceedings{DBLP:conf/focs/AgarwalEGH98,
author = {Pankaj K. Agarwal and
David Eppstein and
Leonidas J. Guibas and
Monika Rauch Henzinger},
title = {Parametric and Kinetic Minimum Spanning Trees},
booktitle = {{FOCS}},
pages = {596--605},
publisher = {{IEEE} Computer Society},
year = {1998}
}
@inproceedings{DBLP:conf/sigir/BharatH98,
author = {Krishna Bharat and
Monika Rauch Henzinger},
title = {Improved Algorithms for Topic Distillation in a Hyperlinked Environment},
booktitle = {{SIGIR}},
pages = {104--111},
publisher = {{ACM}},
year = {1998}
}
@inproceedings{DBLP:conf/soda/GoelHP98,
author = {Ashish Goel and
Monika Rauch Henzinger and
Serge A. Plotkin},
title = {Online Throughput-Competitive Algorithm for Multicast Routing and
Admission Control},
booktitle = {{SODA}},
pages = {97--106},
publisher = {{ACM/SIAM}},
year = {1998}
}
@article{DBLP:journals/jal/Henzinger97,
author = {Monika Rauch Henzinger},
title = {A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental
Approximation Algorithms for Edge and Vertex Connectivity},
journal = {J. Algorithms},
volume = {24},
number = {1},
pages = {194--220},
year = {1997}
}
@article{DBLP:journals/jcss/HenzingerKRS97,
author = {Monika Rauch Henzinger and
Philip N. Klein and
Satish Rao and
Sairam Subramanian},
title = {Faster Shortest-Path Algorithms for Planar Graphs},
journal = {J. Comput. Syst. Sci.},
volume = {55},
number = {1},
pages = {3--23},
year = {1997}
}
@article{DBLP:journals/rsa/HenzingerT97,
author = {Monika Rauch Henzinger and
Mikkel Thorup},
title = {Sampling to provide or to bound: With applications to fully dynamic
graph algorithms},
journal = {Random Struct. Algorithms},
volume = {11},
number = {4},
pages = {369--379},
year = {1997}
}
@article{DBLP:journals/tocs/AndersonBDGHLSVWW97,
author = {Jennifer{-}Ann M. Anderson and
Lance M. Berc and
Jeffrey Dean and
Sanjay Ghemawat and
Monika Rauch Henzinger and
Shun{-}Tak Leung and
Richard L. Sites and
Mark T. Vandevoorde and
Carl A. Waldspurger and
William E. Weihl},
title = {Continuous Profiling: Where Have All the Cycles Gone?},
journal = {{ACM} Trans. Comput. Syst.},
volume = {15},
number = {4},
pages = {357--390},
year = {1997}
}
@inproceedings{DBLP:conf/icalp/HenzingerK97,
author = {Monika Rauch Henzinger and
Valerie King},
title = {Maintaining Minimum Spanning Trees in Dynamic Graphs},
booktitle = {{ICALP}},
series = {Lecture Notes in Computer Science},
volume = {1256},
pages = {594--604},
publisher = {Springer},
year = {1997}
}
@inproceedings{DBLP:conf/sosp/AndersonBDGHLSVWW97,
author = {Jennifer{-}Ann M. Anderson and
Lance M. Berc and
Jeffrey Dean and
Sanjay Ghemawat and
Monika Rauch Henzinger and
Shun{-}Tak Leung and
Richard L. Sites and
Mark T. Vandevoorde and
Carl A. Waldspurger and
William E. Weihl},
title = {Continuous Profiling: Where Have All the Cycles Gone?},
booktitle = {{SOSP}},
pages = {1--14},
publisher = {{ACM}},
year = {1997}
}
@inproceedings{DBLP:conf/stoc/AlbersH97,
author = {Susanne Albers and
Monika Rauch Henzinger},
title = {Exploring Unknown Environments},
booktitle = {{STOC}},
pages = {416--425},
publisher = {{ACM}},
year = {1997}
}
@article{DBLP:journals/ipl/HenzingerW96,
author = {Monika Henzinger and
David P. Williamson},
title = {On the Number of Small Cuts in a Graph},
journal = {Inf. Process. Lett.},
volume = {59},
number = {1},
pages = {41--44},
year = {1996}
}
@inproceedings{DBLP:conf/focs/HenzingerRG96,
author = {Monika Rauch Henzinger and
Satish Rao and
Harold N. Gabow},
title = {Computing Vertex Connectivity: New Bounds from Old Techniques},
booktitle = {{FOCS}},
pages = {462--471},
publisher = {{IEEE} Computer Society},
year = {1996}
}
@inproceedings{DBLP:conf/icalp/HenzingerT96,
author = {Monika Rauch Henzinger and
Mikkel Thorup},
title = {Improved Sampling with Applications to Dynamic Graph Algorithms},
booktitle = {{ICALP}},
series = {Lecture Notes in Computer Science},
volume = {1099},
pages = {290--299},
publisher = {Springer},
year = {1996}
}
@inproceedings{DBLP:conf/soda/HenzingerKW96,
author = {Monika Rauch Henzinger and
Valerie King and
Tandy J. Warnow},
title = {Constructing a Tree from Homeomorphic Subtrees, with Applications
to Computational Evolutionary Biology},
booktitle = {{SODA}},
pages = {333--340},
publisher = {{ACM/SIAM}},
year = {1996}
}
@inproceedings{DBLP:conf/swat/HenzingerT96,
author = {Monika Rauch Henzinger and
Jan Arne Telle},
title = {Faster Algorithms for the Nonemptiness of Streett Automata and for
Communication Protocol Pruning},
booktitle = {{SWAT}},
series = {Lecture Notes in Computer Science},
volume = {1097},
pages = {16--27},
publisher = {Springer},
year = {1996}
}
@article{DBLP:journals/algorithmica/Henzinger95,
author = {Monika Rauch Henzinger},
title = {Fully Dynamic Biconnectivity in Graphs},
journal = {Algorithmica},
volume = {13},
number = {6},
pages = {503--538},
year = {1995}
}
@inproceedings{DBLP:conf/esa/HenzingerP95,
author = {Monika Rauch Henzinger and
Johannes A. La Poutr{\'{e}}},
title = {Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic
Graphs},
booktitle = {{ESA}},
series = {Lecture Notes in Computer Science},
volume = {979},
pages = {171--184},
publisher = {Springer},
year = {1995}
}
@inproceedings{DBLP:conf/focs/HenzingerHK95,
author = {Monika Rauch Henzinger and
Thomas A. Henzinger and
Peter W. Kopke},
title = {Computing Simulations on Finite and Infinite Graphs},
booktitle = {{FOCS}},
pages = {453--462},
publisher = {{IEEE} Computer Society},
year = {1995}
}
@inproceedings{DBLP:conf/focs/HenzingerK95,
author = {Monika Rauch Henzinger and
Valerie King},
title = {Fully Dynamic Biconnectivity and Transitive Closure},
booktitle = {{FOCS}},
pages = {664--672},
publisher = {{IEEE} Computer Society},
year = {1995}
}
@inproceedings{DBLP:conf/icalp/Henzinger95,
author = {Monika Rauch Henzinger},
title = {Approximating Minimum Cuts under Insertions},
booktitle = {{ICALP}},
series = {Lecture Notes in Computer Science},
volume = {944},
pages = {280--291},
publisher = {Springer},
year = {1995}
}
@inproceedings{DBLP:conf/soda/AlbertsH95,
author = {David Alberts and
Monika Rauch Henzinger},
title = {Average Case Analysis of Dynamic Graph Algorithms},
booktitle = {{SODA}},
pages = {312--321},
publisher = {{ACM/SIAM}},
year = {1995}
}
@inproceedings{DBLP:conf/stoc/HenzingerK95,
author = {Monika Rauch Henzinger and
Valerie King},
title = {Randomized dynamic graph algorithms with polylogarithmic time per
operation},
booktitle = {{STOC}},
pages = {519--527},
publisher = {{ACM}},
year = {1995}
}
@article{DBLP:journals/tcs/HershbergerRS94,
author = {John Hershberger and
Monika Rauch and
Subhash Suri},
title = {Data Structures for Two-Edge Connectivity in Planar Graphs},
journal = {Theor. Comput. Sci.},
volume = {130},
number = {1},
pages = {139--161},
year = {1994}
}
@inproceedings{DBLP:conf/focs/Henzinger94,
author = {Monika Rauch Henzinger},
title = {Fully Dynamic Cycle-Equivalence in Graphs},
booktitle = {{FOCS}},
pages = {744--755},
publisher = {{IEEE} Computer Society},
year = {1994}
}
@inproceedings{DBLP:conf/stoc/KleinRRS94,
author = {Philip N. Klein and
Satish Rao and
Monika Rauch and
Sairam Subramanian},
title = {Faster shortest-path algorithms for planar graphs},
booktitle = {{STOC}},
pages = {27--37},
publisher = {{ACM}},
year = {1994}
}
@inproceedings{DBLP:conf/stoc/Rauch94,
author = {Monika Rauch},
title = {Improved data structures for fully dynamic biconnectivity},
booktitle = {{STOC}},
pages = {686--695},
publisher = {{ACM}},
year = {1994}
}
@inproceedings{DBLP:conf/esa/ItalianoPR93,
author = {Giuseppe F. Italiano and
Johannes A. La Poutr{\'{e}} and
Monika Rauch},
title = {Fully Dynamic Planarity Testing in Planar Embedded Graphs (Extended
Abstract)},
booktitle = {{ESA}},
series = {Lecture Notes in Computer Science},
volume = {726},
pages = {212--223},
publisher = {Springer},
year = {1993}
}
@inproceedings{DBLP:conf/wads/MaggsR93,
author = {Bruce M. Maggs and
Monika Rauch},
title = {An Algorithm for Finding Predecessors in Integer Sets},
booktitle = {{WADS}},
series = {Lecture Notes in Computer Science},
volume = {709},
pages = {483--493},
publisher = {Springer},
year = {1993}
}
@article{DBLP:journals/siamcomp/DixonRT92,
author = {Brandon Dixon and
Monika Rauch and
Robert Endre Tarjan},
title = {Verification and Sensitivity Analysis of Minimum Spanning Trees in
Linear Time},
journal = {{SIAM} J. Comput.},
volume = {21},
number = {6},
pages = {1184--1192},
year = {1992}
}
@inproceedings{DBLP:conf/focs/Rauch92,
author = {Monika Rauch},
title = {Fully Dynamic Biconnectivity in Graphs},
booktitle = {{FOCS}},
pages = {50--59},
publisher = {{IEEE} Computer Society},
year = {1992}
}
@inproceedings{DBLP:conf/swat/HershbergerRS92,
author = {John Hershberger and
Monika Rauch and
Subhash Suri},
title = {Fully Dynamic 2-Edge-Connectivity in Planar Graphs},
booktitle = {{SWAT}},
series = {Lecture Notes in Computer Science},
volume = {621},
pages = {233--244},
publisher = {Springer},
year = {1992}
}
@article{DBLP:journals/siamcomp/MehlhornNR90,
author = {Kurt Mehlhorn and
Stefan N{\"{a}}her and
Monika Rauch},
title = {On the Complexity of a Game Related to the Dictionary Problem},
journal = {{SIAM} J. Comput.},
volume = {19},
number = {5},
pages = {902--906},
year = {1990}
}
@inproceedings{DBLP:conf/focs/MehlhornNR89,
author = {Kurt Mehlhorn and
Stefan N{\"{a}}her and
Monika Rauch},
title = {On the Complexity of a Game Related to the Dictionary Problem},
booktitle = {{FOCS}},
pages = {546--548},
publisher = {{IEEE} Computer Society},
year = {1989}
}
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-16 00:38 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: