Monika Henzinger

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Dynamic Algorithms for Graph Coloring.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Quasipolynomial Set-Based Symbolic Algorithms for Parity Games.

[BibT_eX]

[DOI]

Alexander Svozil

Proceedings of the LPAR-22. 22nd International Conference on Logic for Programming, 2018

Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.

[BibT_eX]

[DOI]

Pan Peng

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

A Tree Structure For Dynamic Facility Location.

[BibT_eX]

[DOI]

Dariusz Leniowski

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Symbolic Algorithms for Graphs and Markov Decision Processes with Fairness Objectives.

[BibT_eX]

[DOI]

Simin Oraee

Viktor Toman

Proceedings of the Computer Aided Verification - 30th International Conference, 2018

2017

Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2017

Improved Algorithms for Topic Distillation in a Hyperlinked Environment.

[BibT_eX]

[DOI]

Krishna Bharat

SIGIR Forum, 2017

Welfare Maximization with Friends-of-Friends Network Externalities.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

Improved Algorithms for Parity and Streett objectives.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2017

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3n) Worst Case Update Time.

[BibT_eX]

[DOI]

CoRR, 2017

Maximizing a Submodular Function with Viability Constraints.

[BibT_eX]

[DOI]

David P. Williamson

Algorithmica, 2017

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Faster Algorithms for Mean-Payoff Parity Games.

[BibT_eX]

[DOI]

Alexander Svozil

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.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Conditional Hardness for Sensitivity Problems.

[BibT_eX]

[DOI]

Virginia Vassilevska Williams

Andrea Lincoln

Stefan Neumann

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Capacity Releasing Diffusion for Speed and Locality.

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Machine Learning, 2017

Efficient Algorithms for Graph-Related Problems in Computer-Aided Verification (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.

[BibT_eX]

[DOI]

Pan Peng

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Improved Set-Based Symbolic Algorithms for Parity Games.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

PageRank Algorithm.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization.

[BibT_eX]

[DOI]

Mariangiola Dezani-Ciancaglini

SIAM J. Comput., 2016

EATCS Fellows' Advice to the Young Theoretical Computer Scientist.

[BibT_eX]

[DOI]

Luca Aceto

Bull. EATCS, 2016

New deterministic approximation algorithms for fully dynamic matching.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Conditionally Optimal Algorithms for Generalized Büchi Games.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Yun Kuen Cheung

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning.

[BibT_eX]

[DOI]

Stefan Neumann

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time.

[BibT_eX]

[DOI]

Mikkel Thorup

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

An Expressive Mechanism for Auctions on the Web.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2015

Auctions for Heterogeneous Items and Budget Limits.

[BibT_eX]

[DOI]

Riccardo Colini-Baldeschi

Martin Starnberger

ACM Trans. Economics and Comput., 2015

On Multiple Keyword Sponsored Search Auctions with Budgets.

[BibT_eX]

[DOI]

Stefano Leonardi

Martin Starnberger

ACM Trans. Economics and Comput., 2015

Truthful unit-demand auctions with budgets revisited.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

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

[BibT_eX]

[DOI]

CoRR, 2015

Combinatorial Auctions with Conflict-Based Externalities.

[BibT_eX]

[DOI]

Proceedings of the Web and Internet Economics - 11th International Conference, 2015

Ad Exchange: Envy-Free Auctions with Mediators.

[BibT_eX]

[DOI]

Oren Ben-Zwi

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.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

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.

[BibT_eX]

[DOI]

Charalampos E. Tsourakakis

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Improved Algorithms for One-Pair and k-Pair Streett Objectives.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Design of Dynamic Algorithms via Primal-Dual Method.

[BibT_eX]

[DOI]

Giuseppe F. Italiano

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Approximating the minimum cycle mean.

[BibT_eX]

[DOI]

Michael A. Raskin

Theor. Comput. Sci., 2014

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

[BibT_eX]

[DOI]

J. ACM, 2014

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

[BibT_eX]

[DOI]

Algorithmica, 2014

Limiting Price Discrimination when Selling Products with Positive Network Externalities.

[BibT_eX]

[DOI]

Proceedings of the Web and Internet Economics - 10th International Conference, 2014

Online Ad Assignment with an Ad Exchange.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Online Bipartite Matching with Decomposable Weights.

[BibT_eX]

[DOI]

Moses Charikar

Huy L. Nguyen

Proceedings of the Algorithms - ESA 2014, 2014

2013

A Comprehensive Study of Techniques for URL-Based Web Page Language Classification.

[BibT_eX]

[DOI]

Eda Baykan

ACM Trans. Web, 2013

Bidder optimal assignments for general utilities.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Sponsored search, market equilibria, and the Hungarian Method.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2013

38th International Colloquium on Automata, Languages and Programming.

[BibT_eX]

[DOI]

Luca Aceto

Jirí Sgall

Inf. Comput., 2013

Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives.

[BibT_eX]

[DOI]

Manas Joglekar

Nisarg Shah

Formal Methods Syst. Des., 2013

Approximating the minimum cycle mean.

[BibT_eX]

[DOI]

Proceedings of the Proceedings Fourth International Symposium on Games, 2013

Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

The Presburger Award 2013: Call for Nominations.

[BibT_eX]

[DOI]

Bull. EATCS, 2012

An O(n2) time algorithm for alternating Büchi games.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Maximizing revenue from strategic recommendations under decaying trust.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

ACM Trans. Web, 2011

Offline file assignments for online load balancing.

[BibT_eX]

[DOI]

Riccardo Colini-Baldeschi

Inf. Process. Lett., 2011

On Multiple Round Sponsored Search Auctions with Budgets

[BibT_eX]

[DOI]

Stefano Leonardi

Martin Starnberger

CoRR, 2011

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

[BibT_eX]

[DOI]

CoRR, 2011

Faster and Dynamic Algorithms for Maximal End-Component Decomposition and Related Graph Problems in Probabilistic Verification.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Multi-parameter Mechanism Design under Budget and Matroid Constraints.

[BibT_eX]

[DOI]

Angelina Vidali

Proceedings of the Algorithms - ESA 2011, 2011

2010

The stability of the h-index.

[BibT_eX]

[DOI]

Jacob Suñol

Scientometrics, 2010

Online Stochastic Ad Allocation: Efficiency and Fairness

[BibT_eX]

[DOI]

CoRR, 2010

How much is your personal recommendation worth?

[BibT_eX]

[DOI]

Proceedings of the 19th International Conference on World Wide Web, 2010

Online Stochastic Packing Applied to Display Ad Allocation.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

Mechanisms for the Marriage and the Assignment Game.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

2009

On the Pricing of Recommendations and Recommending Strategically

[BibT_eX]

[DOI]

CoRR, 2009

Detecting the origin of text segments efficiently.

[BibT_eX]

[DOI]

Proceedings of the 18th International Conference on World Wide Web, 2009

Purely URL-based topic classification.

[BibT_eX]

[DOI]

Proceedings of the 18th International Conference on World Wide Web, 2009

A Comparison of Techniques for Sampling Web Pages.

[BibT_eX]

[DOI]

Eda Baykan

Stefan F. Keller

Sebastian De Castelberg

Markus Kinzler

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

2008

PageRank Algorithm.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Theory research at Google.

[BibT_eX]

[DOI]

Anastasios Sidiropoulos

SIGACT News, 2008

Web page language identification based on URLs.

[BibT_eX]

[DOI]

Eda Baykan

Proc. VLDB Endow., 2008

2007

Combinatorial algorithms for web search engines: three success stories.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

Finding near-duplicate web pages: a large-scale evaluation of algorithms.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

World Wide Web, 2005

An online throughput-competitive algorithm for multicast routing and admission control.

[BibT_eX]

[DOI]

Ashish Goel

Serge A. Plotkin

J. Algorithms, 2005

Hyperlink analysis on the world wide web.

[BibT_eX]

[DOI]

Proceedings of the HYPERTEXT 2005, 2005

2004

Data Structures in Web Information Retrieval.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Data Structures and Applications., 2004

The Past, Present and Future of Web Information Retrieval.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Algorithmic Aspects of Web Search Engines.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2004

2003

Scheduling multicasts on unit-capacity trees and meshes.

[BibT_eX]

[DOI]

Stefano Leonardi

J. Comput. Syst. Sci., 2003

Scheduling data transfers in a network and the set scheduling problem.

[BibT_eX]

[DOI]

Ashish Goel

Serge A. Plotkin

Éva Tardos

J. Algorithms, 2003

Algorithmic Challenges in Web Search Engines.

[BibT_eX]

[DOI]

Internet Math., 2003

2002

Challenges in web search engines.

[BibT_eX]

[DOI]

Rajeev Motwani

Craig Silverstein

SIGIR Forum, 2002

Indexing the Web - A Challenge for Supercomputers.

[BibT_eX]

[DOI]

Proceedings of the 2002 IEEE International Conference on Cluster Computing (CLUSTER 2002), 2002

2001

Maintaining Minimum Spanning Forests in Dynamic Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2001

Hyperlink Analysis for the Web.

[BibT_eX]

[DOI]

IEEE Internet Comput., 2001

Who Links to Whom: Mining Linkage between Web Sites.

[BibT_eX]

[DOI]

Proceedings of the 2001 IEEE International Conference on Data Mining, 29 November, 2001

2000

Improved Data Structures for Fully Dynamic Biconnectivity.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

Exploring Unknown Environments.

[BibT_eX]

[DOI]

Susanne Albers

SIAM J. Comput., 2000

A comparison of techniques to find mirrored hosts on the WWW.

[BibT_eX]

[DOI]

Krishna Bharat

Andrei Z. Broder

Jeffrey Dean

J. Am. Soc. Inf. Sci., 2000

Computing Vertex Connectivity: New Bounds from Old Techniques.

[BibT_eX]

[DOI]

Satish Rao

Harold N. Gabow

J. Algorithms, 2000

Link Analysis in Web Information Retrieval.

[BibT_eX]

[DOI]

IEEE Data Eng. Bull., 2000

On near-uniform URL sampling.

[BibT_eX]

[DOI]

Allan Heydon

Michael Mitzenmacher

Marc Najork

Comput. Networks, 2000

Web Information Retrieval.

[BibT_eX]

[DOI]

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

Web Information Retrieval - an Algorithmic Perspective.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2000

1999

Analysis of a Very Large Web Search Engine Query Log.

[BibT_eX]

[DOI]

SIGIR Forum, 1999

Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation.

[BibT_eX]

[DOI]

J. ACM, 1999

Measuring Index Quality Using Random Walks on the Web.

[BibT_eX]

[DOI]

Allan Heydon

Michael Mitzenmacher

Marc Najork

Comput. Networks, 1999

Finding Related Pages in the World Wide Web.

[BibT_eX]

[DOI]

Jeffrey Dean

Comput. Networks, 1999

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

[BibT_eX]

[DOI]

Suresh Venkatasubramanian

Tandy J. Warnow

Algorithmica, 1999

1998

The Connectivity Server: Fast Access to Linkage Information on the Web.

[BibT_eX]

[DOI]

Comput. Networks, 1998

Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.

[BibT_eX]

[DOI]

Michael L. Fredman

Algorithmica, 1998

Average-Case Analysis of Dynamic Graph Algorithms.

[BibT_eX]

[DOI]

David Alberts

Algorithmica, 1998

Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control.

[BibT_eX]

[DOI]

Ashish Goel

Serge A. Plotkin

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Information Retrieval on the Web.

[BibT_eX]

[DOI]

Andrei Z. Broder

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Parametric and Kinetic Minimum Spanning Trees.

[BibT_eX]

[DOI]

Pankaj K. Agarwal

David Eppstein

Leonidas J. Guibas

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Computing on data streams.

[BibT_eX]

[DOI]

Prabhakar Raghavan

Sridhar Rajagopalan

Proceedings of the External Memory Algorithms, 1998

1997

Continuous Profiling: Where Have All the Cycles Gone?

[BibT_eX]

[DOI]

Jennifer-Ann M. Anderson

Lance M. Berc

Jeffrey Dean

Sanjay Ghemawat

ACM Trans. Comput. Syst., 1997

Sampling to provide or to bound: With applications to fully dynamic graph algorithms.

[BibT_eX]

[DOI]

Mikkel Thorup

Random Struct. Algorithms, 1997

Faster Shortest-Path Algorithms for Planar Graphs.

[BibT_eX]

[DOI]

Philip N. Klein

Satish Rao

Sairam Subramanian

J. Comput. Syst. Sci., 1997

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

[BibT_eX]

[DOI]

J. Algorithms, 1997

Maintaining Minimum Spanning Trees in Dynamic Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

1996

On the Number of Small Cuts in a Graph.

[BibT_eX]

[DOI]

David P. Williamson

Inf. Process. Lett., 1996

Faster Algorithms for the Nonemptiness of Streett Automata and for Communication Protocol Pruning.

[BibT_eX]

[DOI]

Jan Arne Telle

Proceedings of the Algorithm Theory, 1996

Improved Sampling with Applications to Dynamic Graph Algorithms.

[BibT_eX]

[DOI]

Mikkel Thorup

Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995

Fully Dynamic Biconnectivity in Graphs.

[BibT_eX]

[DOI]

Algorithmica, 1995

Randomized dynamic graph algorithms with polylogarithmic time per operation.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Approximating Minimum Cuts under Insertions.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Fully Dynamic Biconnectivity and Transitive Closure.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Computing Simulations on Finite and Infinite Graphs.

[BibT_eX]

[DOI]

Thomas A. Henzinger

Peter W. Kopke

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs.

[BibT_eX]

[DOI]

Johannes A. La Poutré

Proceedings of the Algorithms, 1995

1994

Data Structures for Two-Edge Connectivity in Planar Graphs.

[BibT_eX]

[DOI]

John Hershberger

Subhash Suri

Theor. Comput. Sci., 1994

Fully Dynamic Cycle-Equivalence in Graphs

[BibT_eX]

[DOI]

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

An Algorithm for Finding Predecessors in Integer Sets.

[BibT_eX]

[DOI]

Bruce M. Maggs

Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Fully Dynamic Planarity Testing in Planar Embedded Graphs (Extended Abstract).

[BibT_eX]

[DOI]

Giuseppe F. Italiano

Johannes A. La Poutré

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.

[BibT_eX]

[DOI]

Brandon Dixon

Robert Endre Tarjan

SIAM J. Comput., 1992

Fully Dynamic 2-Edge-Connectivity in Planar Graphs.

[BibT_eX]

[DOI]

John Hershberger

Subhash Suri

Proceedings of the Algorithm Theory, 1992

1990

On the Complexity of a Game Related to the Dictionary Problem.

[BibT_eX]

[DOI]

Kurt Mehlhorn

Stefan Näher