# Mikkel Thorup

According to our database1, Mikkel Thorup authored at least 254 papers between 1990 and 2019.

Collaborative distances:
• Dijkstra number2 of three.
• Erdős number3 of two.

## ACM Fellow

ACM Fellow 2005, "For contributions to algorithms and data structures.".

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2019
Adjacency Labeling Schemes and Induced-Universal Graphs.
SIAM J. Discrete Math., 2019

Deterministic Edge Connectivity in Near-Linear Time.
J. ACM, 2019

Random k-out subgraph leaves only O(n/k) inter-component edges.
CoRR, 2019

Three-in-a-Tree in Near Linear Time.
CoRR, 2019

Disks in Curves of Bounded Convex Curvature.
CoRR, 2019

Faster Algorithms for Edge Connectivity via Random 2-Out Contractions.
CoRR, 2019

Hardness of Bichromatic Closest Pair with Jaccard Similarity.
CoRR, 2019

Fast hashing with Strong Concentration Bounds.
CoRR, 2019

Heavy hitters via cluster-preserving clustering.
Commun. ACM, 2019

Non-empty Bins with Simple Tabulation Hashing.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Hardness of Bichromatic Closest Pair with Jaccard Similarity.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

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

Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8.
SIAM J. Comput., 2018

Confirmation Sampling for Exact Nearest Neighbor Search.
CoRR, 2018

Non-Empty Bins with Simple Tabulation Hashing.
CoRR, 2018

Contraction-Based Sparsification in Near-Linear Time.
CoRR, 2018

Wireless coverage prediction via parametric shortest paths.
CoRR, 2018

Power of d Choices with Simple Tabulation.
CoRR, 2018

Fast Fencing.
CoRR, 2018

Fast fencing.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

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

The Entropy of Backwards Analysis.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Dynamic Bridge-Finding in Õ(log2 n) Amortized Time.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Wireless coverage prediction via parametric shortest paths.
Proceedings of the Nineteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2018

Power of d Choices with Simple Tabulation.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017
Coloring 3-Colorable Graphs with Less than n1/5 Colors.
J. ACM, 2017

Practical Hash Functions for Similarity Estimation and Dimensionality Reduction.
CoRR, 2017

The Entropy of Backwards Analysis.
CoRR, 2017

Dynamic Bridge-Finding in $\tilde{O}(\log ^2 n)$ Amortized Time.
CoRR, 2017

Fast Similarity Sketching.
CoRR, 2017

Fast and powerful hashing using tabulation.
Commun. ACM, 2017

Practical Hash Functions for Similarity Estimation and Dimensionality Reduction.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Fast and Powerful Hashing using Tabulation.
Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, 2017

Fast Similarity Sketching.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
On the k-Independence Required by Linear Probing and Minwise Independence.
ACM Trans. Algorithms, 2016

CoRR, 2016

Heavy hitters via cluster-preserving clustering.
CoRR, 2016

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

Finding the Maximum Subset with Bounded Convex Curvature.
CoRR, 2016

Bottleneck Paths and Trees and Deterministic Graphical Games.
Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

The Power of Two Choices with Simple Tabulation.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Fast and Powerful Hashing Using Tabulation (Invited Talk).
Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

Heavy Hitters via Cluster-Preserving Clustering.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Faster Worst Case Deterministic Dynamic Connectivity.
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

Finding the Maximum Subset with Bounded Convex Curvature.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015
Linear Probing with 5-Independent Hashing.
CoRR, 2015

Fast and Powerful Hashing using Tabulation.
CoRR, 2015

High Speed Hashing for Integers and Strings.
CoRR, 2015

Construction and impromptu repair of an MST in a distributed network with o(m) communication.
CoRR, 2015

Deterministic Worst Case Dynamic Connectivity: Simpler and Faster.
CoRR, 2015

From Independence to Expansion and Back Again.
CoRR, 2015

RAM-Efficient External Memory Sorting.
Algorithmica, 2015

Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

From Independence to Expansion and Back Again.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Adjacency Labeling Schemes and Induced-Universal Graphs.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

Sample (x) = (a*x<=t) is a Distinguisher with Probability 1/8.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Planar Reachability in Linear Space and Constant Time.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Hashing for Statistics over K-Partitions.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
Union-Find with Constant Time Deletions.
ACM Trans. Algorithms, 2014

Algorithms and estimators for summarization of unaggregated data streams.
J. Comput. Syst. Sci., 2014

Sample(x)=(a*x<=t) is a distinguisher with probability 1/8.
CoRR, 2014

Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search.
CoRR, 2014

Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time.
CoRR, 2014

Planar Reachability in Linear Space and Constant Time.
CoRR, 2014

Approximately Minwise Independence with Twisted Tabulation.
CoRR, 2014

Hashing for statistics over k-partitions.
CoRR, 2014

The Power of Two Choices with Simple Tabulation.
CoRR, 2014

Adjacency labeling schemes and induced-universal graphs.
CoRR, 2014

Approximately Minwise Independence with Twisted Tabulation.
Proceedings of the Algorithm Theory - SWAT 2014, 2014

Coloring 3-colorable graphs with o(n^{1/5}) colors.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
Mihai Pǎtraşcu: obituary and open problems.
SIGACT News, 2013

Mihai Patrascu: Obituary and Open Problems.
Bulletin of the EATCS, 2013

Bottom-k and Priority Sampling, Set Similarity and Subset Sums with Minimal Independence
CoRR, 2013

On the k-Independence Required by Linear Probing and Minwise Independence
CoRR, 2013

Simple Tabulation, Fast Expanders, Double Tabulation, and High Independence.
CoRR, 2013

RAM-Efficient External Memory Sorting.
CoRR, 2013

Funding successful research.
Commun. ACM, 2013

Intra-domain traffic engineering with shortest path routing protocols.
Annals OR, 2013

Bottom-k and priority sampling, set similarity and subset sums with minimal independence.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Twisted Tabulation Hashing.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

More Compact Oracles for Approximate Distances in Undirected Planar Graphs.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

RAM-Efficient External Memory Sorting.
Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

Simple Tabulation, Fast Expanders, Double Tabulation, and High Independence.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Nearest neighbor classification using bottom-k sketches.
Proceedings of the 2013 IEEE International Conference on Big Data, 2013

2012
Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation.
SIAM J. Comput., 2012

The Power of Simple Tabulation Hashing.
J. ACM, 2012

Combinatorial coloring of 3-colorable graphs
CoRR, 2012

A New Infinity of Distance Oracles for Sparse Graphs.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Combinatorial Coloring of 3-Colorable Graphs.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
Efficient Stream Sampling for Variance-Optimal Estimation of Subset Sums.
SIAM J. Comput., 2011

Don't Rush into a Union: Take Time to Find Your Roots
CoRR, 2011

Minimum k-way cut of bounded size is fixed-parameter tractable
CoRR, 2011

Don't rush into a union: take time to find your roots.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

The power of simple tabulation hashing.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Timeouts with time-reversed linear probing.
Proceedings of the INFOCOM 2011. 30th IEEE International Conference on Computer Communications, 2011

The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths.
ACM Trans. Algorithms, 2010

The Power of Simple Tabulation Hashing
CoRR, 2010

Changing base without losing space.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Regular Expression Matching with Multi-Strings and Intervals.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

On the k-Independence Required by Linear Probing and Minwise Independence.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Tabulation Based 5-Universal Hashing and Linear Probing.
Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments, 2010

2009
Maximum Overhang.
The American Mathematical Monthly, 2009

Higher Lower Bounds for Near-Neighbor and Further Rich Problems.
SIAM J. Comput., 2009

Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets.
PVLDB, 2009

Intra-domain traffic engineering with shortest path routing protocols.
4OR, 2009

String hashing for linear probing.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Discounted deterministic Markov decision processes and discounted all-pairs shortest paths.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Stream sampling for variance-optimal estimation of subset sums.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Faster Regular Expression Matching.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008
Roundtrip spanners and roundtrip routing in directed graphs.
ACM Trans. Algorithms, 2008

Compact name-independent routing with minimum stretch.
ACM Trans. Algorithms, 2008

Oracles for Distances Avoiding a Failed Node or Link.
SIAM J. Comput., 2008

Speeding Up Dynamic Shortest-Path Algorithms.
INFORMS Journal on Computing, 2008

Variance optimal sampling based estimation of subset sums
CoRR, 2008

Minimum k-way cuts via deterministic greedy tree packing.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Maximum overhang.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Confident estimation for multistage measurement sampling and aggregation.
Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2008

2007
Survivable IP network design with OSPF routing.
Networks, 2007

Equivalence between priority queues and sorting.
J. ACM, 2007

Priority sampling for estimation of arbitrary subset sums.
J. ACM, 2007

Dynamic ordered sets with exponential search trees.
J. ACM, 2007

On the variance of subset sum estimation
CoRR, 2007

Fully-Dynamic Min-Cut.
Combinatorica, 2007

Randomization does not help searching predecessors.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Sketching unaggregated data streams for subpopulation-size queries.
Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007

Algorithms and estimators for accurate summarization of internet traffic.
Proceedings of the 7th ACM SIGCOMM Internet Measurement Conference, 2007

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Compact Oracles for Approximate Distances Around Obstacles in the Plane.
Proceedings of the Algorithms, 2007

On the Variance of Subset Sum Estimation.
Proceedings of the Algorithms, 2007

2006
Melding priority queues.
ACM Trans. Algorithms, 2006

CoRR, 2006

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Spanners and emulators with sublinear distance errors.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Confidence intervals for priority sampling.
Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems, 2006

Higher Lower Bounds for Near-Neighbor and Further Rich Problems.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths?
Proceedings of the Algorithms, 2006

2005
Estimating flow distributions from sampled flow statistics.
IEEE/ACM Trans. Netw., 2005

Learn more, sample less: control of volume and variance in network measurement.
IEEE Trans. Information Theory, 2005

Black box for constant-time insertion in priority queues (note).
ACM Trans. Algorithms, 2005

Maintaining information in fully dynamic trees with top trees.
ACM Trans. Algorithms, 2005

A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing.
Networks, 2005

Approximate distance oracles.
J. ACM, 2005

Sampling to estimate arbitrary subset sums
CoRR, 2005

Worst-case update times for fully-dynamic all-pairs shortest paths.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Estimating arbitrary subset sums with few probes.
Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005

Optimal Combination of Sampled Network Measurements.
Proceedings of the 5th Internet Measurement Conference, 2005

Deterministic Constructions of Approximate Distance Oracles and Spanners.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Union-Find with Constant Time Deletions.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004
Quick k-Median, k-Center, and Facility Location for Sparse Graphs.
SIAM J. Comput., 2004

OPT Versus LOAD in Dynamic Storage Allocation.
SIAM J. Comput., 2004

Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut.
Math. Oper. Res., 2004

Integer priority queues with decrease key in constant time and the single source shortest paths problem.
J. Comput. Syst. Sci., 2004

Compact oracles for reachability and approximate distances in planar digraphs.
J. ACM, 2004

Increasing Internet Capacity Using Local Search.
Comp. Opt. and Appl., 2004

Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing Negative Cycles.
Proceedings of the Algorithm Theory, 2004

Melding Priority Queues.
Proceedings of the Algorithm Theory, 2004

Compact name-independent routing with minimum stretch.
Proceedings of the SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2004

Tabulation based 4-universal hashing with applications to second moment estimation.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Meldable RAM priority queues and minimum directed spanning trees.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Flow sampling under hard resource constraints.
Proceedings of the International Conference on Measurements and Modeling of Computer Systems, 2004

Proceedings of the Algorithms, 2004

2003
Untangling the balancing and searching of balanced binary search trees.
Softw., Pract. Exper., 2003

Combinatorial power in multimedia processors.
SIGARCH Computer Architecture News, 2003

Maintaining Information in Fully-Dynamic Trees with Top Trees
CoRR, 2003

Space efficient dynamic stabbing with fast queries.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Integer priority queues with decrease key in constant time and the single source shortest paths problem.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

OPT versus LOAD in dynamic storage allocation.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Tree based MPLS routing.
Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

On AC0 implementations of fusion trees and atomic heaps.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Quick and good facility location.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Performance of estimated traffic matrices in traffic engineering.
Proceedings of the International Conference on Measurements and Modeling of Computer Systems, 2003

Estimating flow distributions from sampled flow statistics.
Proceedings of the ACM SIGCOMM 2003 Conference on Applications, 2003

Load optimal MPLS routing with N+M labels.
Proceedings of the Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30, 2003

Traffic engineering with estimated traffic matrices.
Proceedings of the 3rd ACM SIGCOMM Internet Measurement Conference, 2003

2002
Optimizing OSPF/IS-IS weights in a changing world.
IEEE Journal on Selected Areas in Communications, 2002

Randomized Sorting in O(n log log n) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations.
J. Algorithms, 2002

Efficient Tree Layout in a Multilevel Memory Hierarchy
CoRR, 2002

Dynamic Ordered Sets with Exponential Search Trees
CoRR, 2002

Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut
CoRR, 2002

Roundtrip spanners and roundtrip routing in directed graphs.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Oracles for distances avoiding a link-failure.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Properties and prediction of flow statistics from sampled packet streams.
Proceedings of the 2nd ACM SIGCOMM Internet Measurement Workshop, 2002

Equivalence between Priority Queues and Sorting.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

On Distance Oracles and Routing in Graphs.
Proceedings of the Algorithms, 2002

2001
An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms.
ACM Journal of Experimental Algorithmics, 2001

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.
J. ACM, 2001

Approximate distance oracles.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Fully-dynamic min-cut.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Compact routing schemes.
Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2001

Dynamic string searching.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Charging from sampled network usage.
Proceedings of the 1st ACM SIGCOMM Internet Measurement Workshop, 2001

Quick k-Median, k-Center, and Facility Location for Sparse Graphs.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Compact Oracles for Reachability and Approximate Distances in Planar Digraphs.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms.
Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

2000
On RAM Priority Queues.
SIAM J. Comput., 2000

An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees.
SIAM J. Comput., 2000

Floats, Integers, and Single Source Shortest Paths.
J. Algorithms, 2000

Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees.
J. Algorithms, 2000

Generalized Dominators for Structured Programs.
Algorithmica, 2000

Dynamic Graph Algorithms with Applications.
Proceedings of the Algorithm Theory, 2000

Maintaining Center and Median in Dynamic Trees.
Proceedings of the Algorithm Theory, 2000

Near-optimal fully-dynamic graph connectivity.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Tight(er) worst-case bounds on dynamic searching and priority queues.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Even strongly universal hashing is pretty fast.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Word encoding tree connectivity works.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Internet Traffic Engineering by Optimizing OSPF Weights.
Proceedings of the Proceedings IEEE INFOCOM 2000, 2000

1999
Fusion Trees can be Implemented with AC0 Instructions Only.
Theor. Comput. Sci., 1999

Dominators in Linear Time.
SIAM J. Comput., 1999

On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics).
SIAM J. Comput., 1999

Decremental Dynamic Connectivity.
J. Algorithms, 1999

Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time.
J. ACM, 1999

Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998
All Structured Programs have Small Tree-Width and Good Register Allocation.
Inf. Comput., 1998

String Matching in Lempel-Ziv Compressed Strings.
Algorithmica, 1998

Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Floats, Integers, and Single Source Shortest Paths.
Proceedings of the STACS 98, 1998

Faster Deterministic Sorting and Priority Queues in Linear Space.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Direct Routing on Trees (Extended Abstract).
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Map Graphs in Polynomial Time.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Sparse Dynamic Programming for Evolutionary-Tree Comparison.
SIAM J. Comput., 1997

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

Parallel Shortcutting of Rooted Trees.
J. Algorithms, 1997

Structured Programs have Small Tree-Width and Good Register Allocation (Extended Abstract).
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1997

Finding Cores of Limited Length.
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

Randomized sorting in O(n log log n) Time and Linear Space Using Addition, Shift, and Bit-Wise Boolean Operations.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Decremental Dynamic Connectivity.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Minimizing Diameters of Dynamic Trees.
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

Undirected Single Source Shortest Path in Linear Time.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
Efficient Preprocessing of Simple Binay Pattern Forests.
J. Algorithms, 1996

Disambiguating Grammars by Exclusion of Sub-Parse Trees.
Acta Inf., 1996

Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees.
Proceedings of the Algorithm Theory, 1996

On RAM Priority Queues.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics).
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Generalized Dominators for Structured Programs.
Proceedings of the Static Analysis, Third International Symposium, 1996

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

Static Dictionaries on AC0 RAMs: Query Time Theta(sqrt(log n/log log n)) is Necessary and Sufficient.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
On the Agreement of Many Trees.
Inf. Process. Lett., 1995

Fast Comparison of Evolutionary Trees.
Inf. Comput., 1995

Shortcutting Planar Digraphs.
Combinatorics, Probability & Computing, 1995

String matching in Lempel-Ziv compressed strings.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Computing the Agreement of Trees with Bounded Degrees.
Proceedings of the Algorithms, 1995

1994
Controlled Grammatic Ambiguity.
ACM Trans. Program. Lang. Syst., 1994

Efficient Preprocessing of Simple Binary Pattern Forests.
Proceedings of the Algorithm Theory, 1994

Fast Comparison of Evolutionary Trees.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Optimal Evolutionary Tree Comparison by Sparse Dynamic Programming (Extended Abstract)
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1992
On Shortcutting Digraphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1992

1991
On Conservative Extensions of Syntax in System Development.
Theor. Comput. Sci., 1991

1990
On Conservative Extensions of Syntax in the Process of System Development.
Proceedings of the VDM '90, 1990