Monika Henzinger

According to our database1, Monika Henzinger authored at least 184 papers between 1990 and 2021.

Collaborative distances:

Awards

ACM Fellow

ACM Fellow 2016, "For contributions to computer theory and its practical application".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2021
Recent Advances in Fully Dynamic Graph Algorithms.
CoRR, 2021

Practical Fully Dynamic Minimum Cut Algorithms.
CoRR, 2021

Tight Bounds for Online Graph Partitioning.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Dynamic Set Cover: Improved Amortized and Worst-Case Update Time.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Fully Dynamic <i>k</i>-Center Clustering in Low Dimensional Metrics.
Proceedings of the Symposium on Algorithm Engineering and Experiments, 2021

2020
Vienna Graph Clustering.
Proceedings of the Protein-Protein Interaction Networks, Methods and Protocols., 2020

Improved Guarantees for Vertex Sparsification in Planar Graphs.
SIAM J. Discret. Math., 2020

Local Flow Partitioning for Faster Edge Connectivity.
SIAM J. Comput., 2020

Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest.
CoRR, 2020

A Combinatorial Cut-Based Algorithm for Solving Laplacian Linear Systems.
CoRR, 2020

Faster Parallel Multiterminal Cuts.
CoRR, 2020

An Improved Algorithm for Dynamic Set Cover.
CoRR, 2020

Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity.
CoRR, 2020

Dynamic Clustering to Minimize the Sum of Radii.
Algorithmica, 2020

Deterministic Dynamic Matching in O(1) Update Time.
Algorithmica, 2020

Faster Fully Dynamic Transitive Closure in Practice.
Proceedings of the 18th International Symposium on Experimental Algorithms, 2020

Constant-Time Dynamic (Δ+1)-Coloring.
Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Finding All Global Minimum Cuts in Practice.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Fully-Dynamic Coresets.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Dynamic Matching Algorithms in Practice.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles.
Proceedings of the 36th International Symposium on Computational Geometry, 2020

Shared-Memory Branch-and-Reduce for Multiterminal Cuts.
Proceedings of the Symposium on Algorithm Engineering and Experiments, 2020

Fully Dynamic Single-Source Reachability in Practice: An Experimental Study.
Proceedings of the Symposium on Algorithm Engineering and Experiments, 2020

2019
New amortized cell-probe lower bounds for dynamic problems.
Theor. Comput. Sci., 2019

Efficient Distributed Workload (Re-)Embedding.
Proc. ACM Meas. Anal. Comput. Syst., 2019

Upper and Lower Bounds for Fully Retroactive Graph Problems.
CoRR, 2019

Fully Dynamic k-Center Clustering in Doubling Metrics.
CoRR, 2019

Constant-Time Dynamic (Δ+1)-Coloring and Weight Approximation for Minimum Spanning Forest: Dynamic Algorithms Meet Property Testing.
CoRR, 2019

Distributed edge connectivity in sublinear time.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Shared-Memory Exact Minimum Cuts.
Proceedings of the 2019 IEEE International Parallel and Distributed Processing Symposium, 2019

Algorithms and Hardness for Diameter in Dynamic Graphs.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

A New Deterministic Algorithm for Dynamic Set Cover.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Near-Linear Time Algorithms for Streett Objectives in Graphs and MDPs.
Proceedings of the 30th International Conference on Concurrency Theory, 2019

2018
Valuation Compressions in VCG-Based Combinatorial Auctions.
ACM Trans. Economics and Comput., 2018

Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time.
ACM Trans. Algorithms, 2018

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.
SIAM J. Comput., 2018

Practical Minimum Cut Algorithms.
ACM J. Exp. Algorithmics, 2018

Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time.
J. ACM, 2018

Dynamic algorithms via the primal-dual method.
Inf. Comput., 2018

Memetic Graph Clustering.
Proceedings of the 17th International Symposium on Experimental Algorithms, 2018

The State of the Art in Dynamic Graph Algorithms.
Proceedings of the SOFSEM 2018: Theory and Practice of Computer Science - 44th International Conference on Current Trends in Theory and Practice of Computer Science, Krems, Austria, January 29, 2018

Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Dynamic Algorithms for Graph Coloring.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Quasipolynomial Set-Based Symbolic Algorithms for Parity Games.
Proceedings of the LPAR-22. 22nd International Conference on Logic for Programming, 2018

Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

A Tree Structure For Dynamic Facility Location.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Symbolic Algorithms for Graphs and Markov Decision Processes with Fairness Objectives.
Proceedings of the Computer Aided Verification - 30th International Conference, 2018

Algorithms and Conditional Lower Bounds for Planning Problems.
Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling, 2018

2017
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.
ACM Trans. Algorithms, 2017

Improved Algorithms for Topic Distillation in a Hyperlinked Environment.
SIGIR Forum, 2017

Welfare Maximization with Friends-of-Friends Network Externalities.
Theory Comput. Syst., 2017

Improved Algorithms for Parity and Streett objectives.
Log. Methods Comput. Sci., 2017

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log<sup>3</sup>n) Worst Case Update Time.
CoRR, 2017

Maximizing a Submodular Function with Viability Constraints.
Algorithmica, 2017

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in <i>O</i>(log<sup>3</sup> <i>n</i>) Worst Case Update Time.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Faster Algorithms for Mean-Payoff Parity Games.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time.
Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Conditional Hardness for Sensitivity Problems.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Capacity Releasing Diffusion for Speed and Locality.
Proceedings of the 34th International Conference on Machine Learning, 2017

Efficient Algorithms for Graph-Related Problems in Computer-Aided Verification (Invited Talk).
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Improved Set-Based Symbolic Algorithms for Parity Games.
Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

2016
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrierand Derandomization.
Encyclopedia of Algorithms, 2016

PageRank Algorithm.
Encyclopedia of Algorithms, 2016

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization.
SIAM J. Comput., 2016

EATCS Fellows' Advice to the Young Theoretical Computer Scientist.
Bull. EATCS, 2016

A deterministic almost-tight distributed algorithm for approximating single-source shortest paths.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

New deterministic approximation algorithms for fully dynamic matching.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Conditionally Optimal Algorithms for Generalized Büchi Games.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Model and Objective Separation with Conditional Lower Bounds: Disjunction is Harder than Conjunction.
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015
An Expressive Mechanism for Auctions on the Web.
ACM Trans. Economics and Comput., 2015

Auctions for Heterogeneous Items and Budget Limits.
ACM Trans. Economics and Comput., 2015

On Multiple Keyword Sponsored Search Auctions with Budgets.
ACM Trans. Economics and Comput., 2015

Truthful unit-demand auctions with budgets revisited.
Theor. Comput. Sci., 2015

An Almost-Tight Distributed Algorithm for Computing Single-Source Shortest Paths.
CoRR, 2015

Combinatorial Auctions with Conflict-Based Externalities.
Proceedings of the Web and Internet Economics - 11th International Conference, 2015

Ad Exchange: Envy-Free Auctions with Mediators.
Proceedings of the Web and Internet Economics - 11th International Conference, 2015

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Improved Algorithms for One-Pair and k-Pair Streett Objectives.
Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Design of Dynamic Algorithms via Primal-Dual Method.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
Approximating the minimum cycle mean.
Theor. Comput. Sci., 2014

Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition.
J. ACM, 2014

Polynomial-Time Algorithms for Energy Games with Special Weight Structures.
Algorithmica, 2014

Limiting Price Discrimination when Selling Products with Positive Network Externalities.
Proceedings of the Web and Internet Economics - 10th International Conference, 2014

Online Ad Assignment with an Ad Exchange.
Proceedings of the Approximation and Online Algorithms - 12th International Workshop, 2014

Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs.
Proceedings of the Symposium on Theory of Computing, 2014

A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Online Bipartite Matching with Decomposable Weights.
Proceedings of the Algorithms - ESA 2014, 2014

2013
A Comprehensive Study of Techniques for URL-Based Web Page Language Classification.
ACM Trans. Web, 2013

Bidder optimal assignments for general utilities.
Theor. Comput. Sci., 2013

Sponsored search, market equilibria, and the Hungarian Method.
Inf. Process. Lett., 2013

38th International Colloquium on Automata, Languages and Programming.
Inf. Comput., 2013

Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives.
Formal Methods Syst. Des., 2013

Approximating the minimum cycle mean.
Proceedings of the Proceedings Fourth International Symposium on Games, 2013

Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012
The Presburger Award 2013: Call for Nominations.
Bull. EATCS, 2012

An <i>O</i>(<i>n</i><sup>2</sup>) time algorithm for alternating Büchi games.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Maximizing revenue from strategic recommendations under decaying trust.
Proceedings of the 21st ACM International Conference on Information and Knowledge Management, 2012

2011
A Comprehensive Study of Features and Algorithms for URL-Based Topic Classification.
ACM Trans. Web, 2011

Offline file assignments for online load balancing.
Inf. Process. Lett., 2011

On Multiple Round Sponsored Search Auctions with Budgets
CoRR, 2011

An O(n^2) Time Algorithm for Alternating Büchi Games
CoRR, 2011

Faster and Dynamic Algorithms for Maximal End-Component Decomposition and Related Graph Problems in Probabilistic Verification.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Multi-parameter Mechanism Design under Budget and Matroid Constraints.
Proceedings of the Algorithms - ESA 2011, 2011

2010
The stability of the <i>h</i>-index.
Scientometrics, 2010

Online Stochastic Ad Allocation: Efficiency and Fairness
CoRR, 2010

How much is your personal recommendation worth?
Proceedings of the 19th International Conference on World Wide Web, 2010

Online Stochastic Packing Applied to Display Ad Allocation.
Proceedings of the Algorithms, 2010

Mechanisms for the Marriage and the Assignment Game.
Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

2009
On the Pricing of Recommendations and Recommending Strategically
CoRR, 2009

Detecting the origin of text segments efficiently.
Proceedings of the 18th International Conference on World Wide Web, 2009

Purely URL-based topic classification.
Proceedings of the 18th International Conference on World Wide Web, 2009

A Comparison of Techniques for Sampling Web Pages.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

2008
PageRank Algorithm.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Theory research at Google.
SIGACT News, 2008

Web page language identification based on URLs.
Proc. VLDB Endow., 2008

2007
Combinatorial algorithms for web search engines: three success stories.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006
Finding near-duplicate web pages: a large-scale evaluation of algorithms.
Proceedings of the SIGIR 2006: Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2006

2005
Query-Free News Search.
World Wide Web, 2005

An online throughput-competitive algorithm for multicast routing and admission control.
J. Algorithms, 2005

Hyperlink analysis on the world wide web.
Proceedings of the HYPERTEXT 2005, 2005

2004
Data Structures in Web Information Retrieval.
Proceedings of the Handbook of Data Structures and Applications., 2004

The Past, Present and Future of Web Information Retrieval.
Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

The Past, Present, and Future of Web Search Engines p.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Algorithmic Aspects of Web Search Engines.
Proceedings of the Algorithms, 2004

2003
Scheduling multicasts on unit-capacity trees and meshes.
J. Comput. Syst. Sci., 2003

Scheduling data transfers in a network and the set scheduling problem.
J. Algorithms, 2003

Algorithmic Challenges in Web Search Engines.
Internet Math., 2003

2002
Challenges in web search engines.
SIGIR Forum, 2002

Indexing the Web - A Challenge for Supercomputers.
Proceedings of the 2002 IEEE International Conference on Cluster Computing (CLUSTER 2002), 2002

2001
Maintaining Minimum Spanning Forests in Dynamic Graphs.
SIAM J. Comput., 2001

Hyperlink Analysis for the Web.
IEEE Internet Comput., 2001

Who Links to Whom: Mining Linkage between Web Sites.
Proceedings of the 2001 IEEE International Conference on Data Mining, 29 November, 2001

2000
Improved Data Structures for Fully Dynamic Biconnectivity.
SIAM J. Comput., 2000

Exploring Unknown Environments.
SIAM J. Comput., 2000

A comparison of techniques to find mirrored hosts on the WWW.
J. Am. Soc. Inf. Sci., 2000

Computing Vertex Connectivity: New Bounds from Old Techniques.
J. Algorithms, 2000

Link Analysis in Web Information Retrieval.
IEEE Data Eng. Bull., 2000

On near-uniform URL sampling.
Comput. Networks, 2000

Web Information Retrieval.
Proceedings of the 16th International Conference on Data Engineering, San Diego, California, USA, February 28, 2000

Web Information Retrieval - an Algorithmic Perspective.
Proceedings of the Algorithms, 2000

1999
Analysis of a Very Large Web Search Engine Query Log.
SIGIR Forum, 1999

Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation.
J. ACM, 1999

Measuring Index Quality Using Random Walks on the Web.
Comput. Networks, 1999

Finding Related Pages in the World Wide Web.
Comput. Networks, 1999

Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.
Algorithmica, 1999

1998
The Connectivity Server: Fast Access to Linkage Information on the Web.
Comput. Networks, 1998

Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.
Algorithmica, 1998

Average-Case Analysis of Dynamic Graph Algorithms.
Algorithmica, 1998

Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Information Retrieval on the Web.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Parametric and Kinetic Minimum Spanning Trees.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Computing on data streams.
Proceedings of the External Memory Algorithms, 1998

1997
Continuous Profiling: Where Have All the Cycles Gone?
ACM Trans. Comput. Syst., 1997

Sampling to provide or to bound: With applications to fully dynamic graph algorithms.
Random Struct. Algorithms, 1997

Faster Shortest-Path Algorithms for Planar Graphs.
J. Comput. Syst. Sci., 1997

A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity.
J. Algorithms, 1997

Maintaining Minimum Spanning Trees in Dynamic Graphs.
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

1996
On the Number of Small Cuts in a Graph.
Inf. Process. Lett., 1996

Faster Algorithms for the Nonemptiness of Streett Automata and for Communication Protocol Pruning.
Proceedings of the Algorithm Theory, 1996

Improved Sampling with Applications to Dynamic Graph Algorithms.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995
Fully Dynamic Biconnectivity in Graphs.
Algorithmica, 1995

Randomized dynamic graph algorithms with polylogarithmic time per operation.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Approximating Minimum Cuts under Insertions.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Fully Dynamic Biconnectivity and Transitive Closure.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Computing Simulations on Finite and Infinite Graphs.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs.
Proceedings of the Algorithms, 1995

1994
Data Structures for Two-Edge Connectivity in Planar Graphs.
Theor. Comput. Sci., 1994

Fully Dynamic Cycle-Equivalence in Graphs
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
An Algorithm for Finding Predecessors in Integer Sets.
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Fully Dynamic Planarity Testing in Planar Embedded Graphs (Extended Abstract).
Proceedings of the Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30, 1993

1992
Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time.
SIAM J. Comput., 1992

Fully Dynamic 2-Edge-Connectivity in Planar Graphs.
Proceedings of the Algorithm Theory, 1992

1990
On the Complexity of a Game Related to the Dictionary Problem.
SIAM J. Comput., 1990


  Loading...