Monika Henzinger

According to our database1, Monika Henzinger authored at least 153 papers between 1989 and 2019.

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

Homepages:

On csauthors.net:

Bibliography

2019
Efficient Distributed Workload (Re-)Embedding.
POMACS, 2019

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

2018
Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time.
ACM Trans. Algorithms, 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

Practical Minimum Cut Algorithms.
Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments, 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 Parity and Streett objectives.
Logical Methods in Computer Science, 2017

Local Flow Partitioning for Faster Edge Connectivity.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) 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

Dynamic Clustering to Minimize the Sum of Radii.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

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

Improved Guarantees for Vertex Sparsification in Planar Graphs.
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

EATCS Fellows' Advice to the Young Theoretical Computer Scientist.
Bulletin of the 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
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

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

Welfare Maximization with Friends-of-Friends Network Externalities.
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

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

Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 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.
TWEB, 2013

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

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

Valuation Compressions in VCG-Based Combinatorial Auctions.
Proceedings of the Web and Internet Economics - 9th International Conference, 2013

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

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Maximizing a Submodular Function with Viability Constraints.
Proceedings of the Algorithms - ESA 2013, 2013

2012
The Presburger Award 2013: Call for Nominations.
Bulletin of the EATCS, 2012

Auctions with Heterogeneous Items and Budget Limits.
Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

An O(n2) time algorithm for alternating Büchi games.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

On Multiple Keyword Sponsored Search Auctions with Budgets.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Polynomial-Time Algorithms for Energy Games with Special Weight Structures.
Proceedings of the Algorithms - ESA 2012, 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.
TWEB, 2011

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

An expressive mechanism for auctions on the web.
Proceedings of the 20th International Conference on World Wide Web, 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

Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives.
Proceedings of the Computer Aided Verification - 23rd International Conference, 2011

2010
The stability of the h-index.
Scientometrics, 2010

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

Sponsored Search, Market Equilibria, and the Hungarian Method.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 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
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

Bidder Optimal Assignments for General Utilities.
Proceedings of the Internet and Network Economics, 5th International Workshop, 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

Theory research at Google.
SIGACT News, 2008

Web page language identification based on URLs.
PVLDB, 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
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

The past, present, and future of web information retrieval.
Proceedings of the Document Recognition and Retrieval XI, 2004

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

Query-free news search.
Proceedings of the Twelfth International World Wide Web Conference, 2003

The Past, Present and Future of Web Information Retrieval.
Proceedings of the Informatische Fachkonzepte im Unterricht, 2003

Challenges in Web Search Engines.
Proceedings of the IJCAI-03, 2003

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 Computing, 2001

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

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

On near-uniform URL sampling.
Computer 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.
Computer Networks, 1999

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

Scheduling Data Transfers in a Network and the Set Scheduling Problem.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Scheduling Multicasts on Unit-Capacity Trees and Meshes.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

A Comparison of Techniques to Find Mirrored Hosts on the WWW.
Proceedings of the 1999 ACM Digital Library Workshop on Organizing Web Space (WOWS), 1999

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

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

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

Improved Algorithms for Topic Distillation in a Hyperlinked Environment.
Proceedings of the SIGIR '98: Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 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
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

Exploring Unknown Environments.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Continuous Profiling: Where Have All the Cycles Gone?
Proceedings of the Sixteenth ACM Symposium on Operating System Principles, 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

Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

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

Computing Vertex Connectivity: New Bounds from Old Techniques.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 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

Average Case Analysis of Dynamic Graph Algorithms.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Improved data structures for fully dynamic biconnectivity.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Faster shortest-path algorithms for planar graphs.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 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

Fully Dynamic Biconnectivity in Graphs
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

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

1989
On the Complexity of a Game Related to the Dictionary Problem
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989


  Loading...