Monika Henzinger
According to our database1,
Monika Henzinger
authored at least 156 papers
between 1989 and 2019.
Collaborative distances:
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 OtherLinks
Homepages:
-
at zbmath.org
-
at www.idref.fr
-
at www.acm.org
-
at viaf.org
-
at id.loc.gov
-
at d-nb.info
-
at dl.acm.org
On csauthors.net:
Bibliography
2019
New amortized cell-probe lower bounds for dynamic problems.
Theor. Comput. Sci., 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
Efficient Distributed Workload (Re-)Embedding.
Proceedings of the Abstracts of the 2019 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems, 2019
Algorithms and Hardness for Diameter in Dynamic Graphs.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 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 Edition, 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