Monika Henzinger
#33,270
Most Influential Person Now
German computer scientist
Monika Henzinger's AcademicInfluence.com Rankings
Monika Henzingercomputer-science Degrees
Computer Science
#1924
World Rank
#1998
Historical Rank
Algorithms
#94
World Rank
#94
Historical Rank
Database
#4140
World Rank
#4306
Historical Rank
Download Badge
Computer Science
Monika Henzinger's Degrees
- PhD Computer Science Princeton University
Similar Degrees You Can Earn
Why Is Monika Henzinger Influential?
(Suggest an Edit or Addition)According to Wikipedia, Monika Henzinger is a German computer scientist, and is a former director of research at Google. She is currently a professor at the University of Vienna. Her expertise is mainly on algorithms with a focus on data structures, algorithmic game theory, information retrieval, search algorithms and Web data mining. She is married to Thomas Henzinger and has three children.
Monika Henzinger's Published Works
Number of citations in a given year to any of this author's works
Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author
Published Works
- Analysis of a very large web search engine query log (1999) (1307)
- Improved algorithms for topic distillation in a hyperlinked environment (1998) (744)
- Finding Related Pages in the World Wide Web (1999) (586)
- Computing simulations on finite and infinite graphs (1995) (565)
- Faster shortest-path algorithms for planar graphs (1994) (549)
- Finding near-duplicate web pages: a large-scale evaluation of algorithms (2006) (512)
- Computing on data streams (1999) (498)
- Analysis of a Very Large Altavista Query Log" SRC Technical note #1998-14 (1998) (386)
- Challenges in web search engines (2002) (368)
- On near-uniform URL sampling (2000) (291)
- Exploring unknown environments (1997) (284)
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation (1999) (269)
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture (2015) (251)
- Hyperlink Analysis for the Web (2001) (230)
- The Connectivity Server: Fast Access to Linkage Information on the Web (1998) (229)
- Online Stochastic Packing Applied to Display Ad Allocation (2010) (225)
- Who links to whom: mining linkage between Web sites (2001) (198)
- Query-Free News Search (2003) (175)
- Measuring Index Quality Using Random Walks on the Web (1999) (154)
- Fully dynamic biconnectivity and transitive closure (1995) (153)
- Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time (1992) (145)
- Computing vertex connectivity: new bounds from old techniques (1996) (140)
- Randomized dynamic graph algorithms with polylogarithmic time per operation (1995) (139)
- Link Analysis in Web Information Retrieval (2000) (136)
- Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology (1996) (126)
- Purely URL-based topic classification (2009) (125)
- Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams (2015) (120)
- A Comparison of Techniques to Find Mirrored Hosts on the WWW (2000) (109)
- Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching (2014) (108)
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths (2015) (104)
- Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time (2014) (102)
- Maintaining Minimum Spanning Trees in Dynamic Graphs (1997) (96)
- New deterministic approximation algorithms for fully dynamic matching (2016) (90)
- Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification (2011) (88)
- Local Flow Partitioning for Faster Edge Connectivity (2017) (79)
- Search Technologies for the Internet (2007) (76)
- Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization (2013) (75)
- Algorithmic Challenges in Web Search Engines (2004) (73)
- Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition (2014) (70)
- Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time (2017) (68)
- A Comprehensive Study of Features and Algorithms for URL-Based Topic Classification (2011) (67)
- Lower Bounds for Fully Dynamic Connectivity Problems in Graphs (1995) (65)
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs (2014) (63)
- Dynamic Algorithms for Graph Coloring (2017) (62)
- Parametric and kinetic minimum spanning trees (1998) (61)
- Maintaining Minimum Spanning Forests in Dynamic Graphs (2002) (58)
- Extracting knowledge from the World Wide Web (2004) (56)
- Sampling to provide or to bound: With applications to fully dynamic graph algorithms (1997) (56)
- A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching (2018) (54)
- Faster Algorithms for the Nonemptiness of Streett Automata and for Communication Protocol Pruning (1995) (54)
- Improved Data Structures for Fully Dynamic Biconnectivity (2000) (53)
- An O(n2) time algorithm for alternating Büchi games (2011) (49)
- Web page language identification based on URLs (2008) (48)
- Detecting the origin of text segments efficiently (2009) (43)
- Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time (2016) (42)
- A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths (2014) (41)
- The stability of the h-index (2009) (40)
- Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs (2015) (37)
- Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time (2014) (36)
- Split diversity in constrained conservation prioritization using integer linear programming (2014) (36)
- On the Number of Small Cuts in a Graph (1996) (35)
- Distributed edge connectivity in sublinear time (2019) (35)
- Capacity Releasing Diffusion for Speed and Locality (2017) (34)
- A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity (1997) (33)
- Hyperlink analysis on the world wide web (2005) (29)
- Fully Dynamic Planarity Testing in Planar Embedded Graphs (Extended Abstract) (1993) (29)
- Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs (1995) (28)
- Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers (2020) (26)
- An expressive mechanism for auctions on the web (2011) (26)
- Scheduling data transfers in a network and the set scheduling problem (1999) (26)
- Average-Case Analysis of Dynamic Graph Algorithms (1995) (26)
- Improved Guarantees for Vertex Sparsification in Planar Graphs (2017) (26)
- Fully Dynamic 2-Edge Connectivity Algorithm in Polylogarithmic Time per Operation (1997) (26)
- Conditionally Optimal Algorithms for Generalized Büchi Games (2016) (26)
- On Multiple Keyword Sponsored Search Auctions with Budgets (2012) (25)
- Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds (2016) (25)
- Design of Dynamic Algorithms via Primal-Dual Method (2015) (24)
- Algorithms and Hardness for Diameter in Dynamic Graphs (2018) (23)
- Auctions for Heterogeneous Items and Budget Limits (2012) (22)
- Polynomial-Time Algorithms for Energy Games with Special Weight Structures (2012) (22)
- Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives (2011) (22)
- Online througput-competitive algorithm for multicast routing and admission control (2005) (21)
- Conditional Hardness for Sensitivity Problems (2017) (21)
- A Comprehensive Study of Techniques for URL-Based Web Page Language Classification (2013) (21)
- Improved Sampling with Applications to Dynamic Graph Algorithms (1996) (20)
- An O(n^2) Time Algorithm for Alternating B\"uchi Games (2011) (20)
- Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time (2018) (19)
- Practical Minimum Cut Algorithms (2017) (18)
- A Comparison of Techniques for Sampling Web Pages (2009) (18)
- Valuation Compressions in VCG-Based Combinatorial Auctions (2013) (18)
- Improved Algorithms for One-Pair and k-Pair Streett Objectives (2014) (17)
- Sponsored search, market equilibria, and the Hungarian Method (2009) (17)
- A New Deterministic Algorithm for Dynamic Set Cover (2019) (17)
- Recent Advances in Fully Dynamic Graph Algorithms (2021) (16)
- Model and Objective Separation with Conditional Lower Bounds: Disjunction is Harder than Conjunction * (2016) (16)
- Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs (2018) (16)
- Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles (2020) (15)
- Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity (2020) (15)
- Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications (2020) (15)
- The Power of Vertex Sparsifiers in Dynamic Graph Algorithms (2017) (15)
- Fully Dynamic 2-Edge-Connectivity in Planar Graphs (1992) (15)
- Improved Algorithms for Topic Distillation in a Hyperlinked Environment (1998) (14)
- Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks (2013) (14)
- On the complexity of a game related to the dictionary problem (1989) (14)
- Differentially Private Algorithms for Graphs Under Continual Observation (2021) (13)
- Constant-Time Dynamic (Δ+1)-Coloring (2020) (13)
- Fully-Dynamic Coresets (2020) (12)
- Web Information Retrieval - an Algorithmic Perspective (2000) (12)
- Bidder optimal assignments for general utilities (2009) (12)
- Algorithmic aspects of information retrieval on the web (2002) (12)
- Efficient Distributed Workload (Re-)Embedding (2019) (12)
- Dynamic algorithms via the primal-dual method (2018) (11)
- A Tree Structure For Dynamic Facility Location (2019) (11)
- The State of the Art in Dynamic Graph Algorithms (2018) (11)
- New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners (2020) (11)
- Fully dynamic biconnectivity in graphs (1995) (11)
- Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time (2016) (10)
- Scheduling multicasts on unit-capacity trees and meshes (2003) (10)
- Theory research at Google (2008) (10)
- Memetic Graph Clustering (2018) (10)
- Online Bipartite Matching with Decomposable Weights (2014) (9)
- Dynamic Matching Algorithms in Practice (2020) (9)
- Improved Set-based Symbolic Algorithms for Parity Games (2017) (9)
- Data Structures for Two-Edge Connectivity in Planar Graphs (1994) (9)
- Deterministic Dynamic Matching in O(1) Update Time (2019) (9)
- Dynamic Clustering to Minimize the Sum of Radii (2017) (9)
- Tight Bounds for Online Graph Partitioning (2020) (9)
- Shared-Memory Exact Minimum Cuts (2018) (9)
- Combinatorial algorithms for web search engines: three success stories (2007) (9)
- 38th International Colloquium on Automata, Languages and Programming (2013) (8)
- Approximating Minimum Cuts under Insertions (1995) (8)
- Constant matters: Fine-grained Complexity of Differentially Private Continual Observation Using Completely Bounded Norms (2022) (8)
- Quasipolynomial Set-Based Symbolic Algorithms for Parity Games (2018) (8)
- Fully dynamic cycle-equivalence in graphs (1994) (8)
- Approximating the minimum cycle mean (2013) (8)
- Constant-Time Dynamic (Δ+1)-Coloring and Weight Approximation for Minimum Spanning Forest: Dynamic Algorithms Meet Property Testing (2019) (8)
- Faster Fully Dynamic Transitive Closure in Practice (2020) (8)
- The Past, Present, and Future of Web Search Engines p (2004) (8)
- Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning (2016) (8)
- Fully Dynamic k-Center Clustering in Low Dimensional Metrics (2021) (7)
- Dynamic Set Cover: Improved Amortized and Worst-Case Update Time (2020) (7)
- An Expressive Mechanism for Auctions on the Web (2016) (7)
- Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference Guide (2022) (7)
- Ad Exchange: Envy-Free Auctions with Mediators (2015) (7)
- Fully Dynamic Single-Source Reachability in Practice: An Experimental Study (2019) (7)
- Online Stochastic Ad Allocation: Efficiency and Fairness (2010) (7)
- The Complexity of Average-Case Dynamic Subgraph Counting (2022) (7)
- Shared-Memory Branch-and-Reduce for Multiterminal Cuts (2019) (6)
- Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter (2017) (6)
- Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks (2015) (6)
- Near-Linear Time Algorithms for Streett Objectives in Graphs and MDPs (2019) (6)
- Limiting Price Discrimination when Selling Products with Positive Network Externalities (2014) (6)
- On Multiple Round Sponsored Search Auctions with Budgets (2011) (6)
- Hyperlink Analysis for the Web Hyperlink analysis algorithms allow search engines to deliver focused results to user queries.This article surveys ranking algorithms used to retrieve information on the Web. (2001) (6)
- An Improved Algorithm for Dynamic Set Cover (2020) (6)
- Fully Dynamic Four-Vertex Subgraph Counting (2021) (5)
- Indexing the web - a challenge for supercomputers (2002) (5)
- Efficient Distributed Workload (Re-)Embedding (2019) (5)
- Tutorial 1: Web Information Retrieval (2000) (5)
- Almost Tight Error Bounds on Differentially Private Continual Counting (2022) (5)
- Symbolic Algorithms for Graphs and Markov Decision Processes with Fairness Objectives (2018) (5)
- The past, present and future of web information retrieval (2004) (5)
- PageRank Algorithm (2008) (5)
- On the Complexity of Weight-Dynamic Network Algorithms (2021) (5)
- Offline file assignments for online load balancing (2011) (4)
- Practical Fully Dynamic Minimum Cut Algorithms (2021) (4)
- Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter Topologies (2022) (4)
- Short-Length Menger Theorems (1997) (4)
- Online Ad Assignment with an Ad Exchange (2014) (4)
- Finding All Global Minimum Cuts In Practice (2020) (4)
- Welfare Maximization with Friends-of-Friends Network Externalities (2017) (4)
- Algorithms and Conditional Lower Bounds for Planning Problems (2018) (4)
- Maximizing revenue from strategic recommendations under decaying trust (2012) (4)
- Fully Dynamic k-Center Clustering in Doubling Metrics (2019) (4)
- Recent Advances in Fully Dynamic Graph Algorithms (Invited Talk) (2022) (3)
- Web Information Retrieval. (2000) (3)
- How much is your personal recommendation worth? (2010) (3)
- Finding anything in the billion page Web: are algorithms the key? (1999) (2)
- Upper and Lower Bounds for Fully Retroactive Graph Problems (2019) (2)
- Welfare Maximization with Friends-of-Friends Network Externalities (2017) (2)
- Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs (2022) (2)
- Random Rank-Based, Hierarchical or Trivial: Which Dynamic Graph Algorithm Performs Best in Practice? (2021) (2)
- Vienna Graph Clustering (2020) (2)
- Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks (2022) (2)
- Brief Announcement: Broadcasting Time in Dynamic Rooted Trees is Linear (2022) (2)
- Mechanisms for the Marriage and the Assignment Game (2010) (2)
- Edinburgh Research Explorer Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds (2011) (2)
- Faster Parallel Multiterminal Cuts (2020) (2)
- Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching (2023) (2)
- Multi-parameter Mechanism Design under Budget and Matroid Constraints (2011) (2)
- Algorithmic Aspects of Web Search Engines (2004) (2)
- Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest (2020) (2)
- On the Pricing of Recommendations and Recommending Strategically (2009) (1)
- Polynomial-Time Algorithms for Energy Games with Special Weight Structures (2013) (1)
- Truthful unit-demand auctions with budgets revisited (2015) (1)
- Proceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part I (2011) (1)
- Informatin Retrieval on the Web (1998) (1)
- Constructing differential categories and deconstructing categories of games (2011) (1)
- Efficient DistributedWorkload (Re-)Embedding (2019) (1)
- Maximizing a Submodular Function with Viability Constraints (2015) (1)
- Faster Algorithms for Bounded Liveness in Graphs and Game Graphs (2021) (1)
- Combinatorial Auctions with Conflict-Based Externalities (2015) (1)
- Automata, Languages and Programming : 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011. Proceedings (2011) (1)
- Incremental Approximate Maximum Flow in m1/2+o(1) update time (2022) (1)
- Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives (2012) (1)
- Deterministic Dynamic Matching in O(1) Update Time (2019) (1)
- Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries (2023) (1)
- Faster Algorithms for Mean-Payoff Parity Games (2017) (1)
- The past, present, and future of web information retrieval (2003) (1)
- A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems (2020) (1)
- Approximating the minimum cycle mean I,II (2014) (1)
- Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows (2021) (1)
- Comparative Analysis of Dynamic Graph Techniques and Data Structure (2019) (1)
- Constant-time Dynamic (Δ +1)-Coloring (2022) (1)
- An Algorithm for Finding Predecessors in Integer Sets (1993) (1)
- Leximax Approximations and Representative Cohort Selection (2022) (0)
- New Amortized Cell-Probe Lower Bounds for Dynamic Problems (2019) (0)
- Electrical Flows for Polylogarithmic Competitive Oblivious Routing (2023) (0)
- The Presburger Award 2013: Call for Nominations (2013) (0)
- To Provide or To Bound: Sampling in Fully Dynamic Graph Algorithms (1996) (0)
- On fully dynamic constant-factor approximation algorithms for clustering problems (2021) (0)
- 2 A Graph Representation for the Web (2000) (0)
- Faster Vertex Connectivity Algorithms (2007) (0)
- The augmentation-speed tradeoff for consistent network updates (2022) (0)
- Modern Dynamic Data Structures (Invited Talk) (2022) (0)
- Time Complexity of Broadcast and Consensus for Randomized Oblivious Message Adversaries (2023) (0)
- Dynamic Demand-Aware Link Scheduling for Reconfigurable Datacenters (2023) (0)
- [12] G. N. Frederickson. Data Structures for On-line Updating of Minimum Spanning Trees, with Applications. Siam (2007) (0)
- Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2010. Proceedings, Part II (Lecture ... Computer Science and General Issues) (2011) (0)
- A Combinatorial Cut-Based Algorithm for Solving Laplacian Linear Systems (2020) (0)
- 46 : 2 Incremental Exact Min-Cut in Poly-logarithmic Amortized (2018) (0)
- Universal points in the asymptotic spectrum of tensors (2018) (0)
- Differentially Private Data Structures under Continual Observation for Histograms and Related Queries (2023) (0)
- Constant-Time Dynamic (\Delta + 1)-Coloring (2020) (0)
- Faster Submodular Maximization for Several Classes of Matroids (2023) (0)
- Dynamic Maintenance of Monotone Dynamic Programs and Applications (2023) (0)
- Efficient Algorithms for Graph-Related Problems in Computer-Aided Verification (Invited Talk) (2017) (0)
- Symbolic Time and Space Tradeoffs for Probabilistic Verification (2021) (0)
- Data Structures in Web Information Retrieval (2018) (0)
- Finding free registers (1998) (0)
- Maximizing a Submodular Function with Viability Constraints (2013) (0)
- Incremental exact min-cut in poly-logarithmic amortized update (2016) (0)
- Fully Dynamic Exact Edge Connectivity in Sublinear Time (2023) (0)
- Advice coins for classical and quantum computation (2011) (0)
- D S ] 1 2 N ov 2 01 7 Dynamic Algorithms for Graph Coloring (2018) (0)
- EATCS Fellows' Advice to the Young Theoretical Computer Scientist (2016) (0)
- Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I (2011) (0)
- Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Update Time (2017) (0)
- Fine-Grained Complexity Lower Bounds for Problems in Computer Aided Verification (2022) (0)
- 3 : 2 Near-Linear Time Algorithms for Streett Objectives in Graphs and MDPs Models : (2019) (0)
This paper list is powered by the following services:
Other Resources About Monika Henzinger
What Schools Are Affiliated With Monika Henzinger?
Monika Henzinger is affiliated with the following schools:
