Mikkel Thorup

Abstract Maximum Overhang (extended abstract) ∗ (2008)

Traffic engineering involves adapting the routing of traffic to network conditions, with the joint goals of good user performance and efficient use of network resources. In this article we describe...

Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick

How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...

Measurement, Performance (2008)

Storage and Retrieval (2008)

We consider the performance of estimated traffic matrices in traffic engineering. More precisely, we first optimize the routing in an IP backbone to minimize congestion with the estimated traffic...

Noga Alon, Nick Duffield, Carsten Lund, Mikkel Thorup

Suppose we have a large table T of items i, each with a weight wi, e.g., people and their salary. In a general preprocessing step for estimating arbitrary subset sums, we assign each item a random...

Abstract Optimal Combination of Sampled Network Measurements (2008)

Union-Find with Constant Time Deletions (2008)

IP network traffic is commonly measured at multiple points in order that all traffic passes at least one observation point. The resulting measurements are subsequently joined for network analysis....

Stephen Alstrup, Inge Li Gørtz, Theis Rauhe, Mikkel Thorup, Uri Zwick

Abstract. A union-find data structure maintains a collection of disjoint sets under makeset, union and find operations. Kaplan, Shafrir and Tarjan [SODA 2002] designed data structures for an...

[Mathematics of Computing]: Discrete Mathematics—graph algorithms General Terms: Algorithms (2008)

Jacob Holm, De Lichtenberg, Mikkel Thorup

Abstract. Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph...

Variance optimal sampling based estimation of subset sums (2008)

Cohen, Edith, Duffield, Nick, Kaplan, Haim, Lund, Carsten, Thorup, Mikkel

From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size $k$ that we can later use to estimate the total weight of arbitrary subsets. This is the...

David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young

Given an undirected graph with edge costs and a subset of k ≥ 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others....

k (2007)

David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young

Given an undirected graph with edge costs and a subset of

y (2007)

Liam Roditty, Mikkel Thorup, Uri Zwick

We introduce the notion of roundtrip-spanners of weighted directed graphs and describe ecient algorithms for their construction. For every integer k 1 and any > 0, we show that any directed graph...

General Terms (2007)

log n = log log n) is Necessary and Sufficient (2007)

We consider the performance of estimated tra#c matrices in tra#c engineering. More precisely, we first optimize the routing in an IP backbone to minimize congestion with the estimated tra#c matrix....

Arne Andersson, Peter Bro Miltersen, Sren Riis, Mikkel Thorup

et al.:

and Other Rewriting Systems (2007)

RAMs: Query time \Theta( (2007)

A new approach to ambiguity of context-free grammars is presented, and within this approach the LL and LR techniques are generalized to solve the following problems for large classes of ambiguous...

Arne Andersson, Arne Andersson, Peter Bro Miltersen, Peter Bro Miltersen, Sren Riis, Sren Riis, ...

log n = log log n) is necessary and sufficient

x (2007)

David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young

Given an undirected graph with edge costs and a subset of k 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The...

E-mail: (2007)

Web www.it-c.dk Finding Cores of Limited Length (2007)

Abstract---IP flows have heavy-tailed packet and byte size distributions. This make them poor candidates for uniform sampling---i.e. selecting

Peter Sommerlund, Copyright C, Peer Sommerlun, Mikkel Thorup, Mikkel Thorup, Stephen Alstrup, ...

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. ISSN

Rutgers University (2007)

Stephen Alstrup, Jacob Holm, Mikkel Thorup

We consider the problem of computing the Maximum Agreement Subtree (MAST) of a set of leaf labeled trees. We give an algorithm which computes the MAST of k trees on n species where some tree has...

1 (2007)

Abstract. We show how to maintain centers and medians for a collection of dynamic trees where edges may be inserted and deleted and node and edge weights may be changed. All updates are supported in...

Learn More, Sample Less: Control of Volume and Variance in Network Measurement (2007)

Network design for OSPF routing (2007)

objects 289-43596 . We wish to estimate the sums !#" %$ &('*)+& , of the sizes of objects of a given color , from a sampled subset of objects. How should the sampling distribution...

Luciana Buriol Paulo, Paulo M. França, Mikkel Thorup

Internet protocol (IP) traffic follows rules established by routing protocols, such as Open Shortest Path First (OSPF). Each router computes shortest paths using weights assigned by the network...

ABSTRACT Traffic Engineering with Estimated Traffic Matrices (2007)

On the variance of subset sum estimation (2007)

Traffic engineering and traffic matrix estimation are often treated as separate fields, even though one of the major applications for a traffic matrix is traffic engineering. In cases where a traffic...

Maximum overhang (2007)

Paterson, Mike, Peres, Yuval, Thorup, Mikkel, Winkler, Peter, Zwick, Uri

How far can a stack of $n$ identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...

Szegedy, Mario, Thorup, Mikkel

For high volume data streams and large data warehouses, sampling is used for efficient approximate answers to aggregate queries over selected subsets. Mathematically, we are dealing with a set of...

Maximum Overhang (2007)

Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick

How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...

Maximum Overhang (2007)

Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick

How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...

Time-Space Trade-Offs for Predecessor Search (2006)

Patrascu, Mihai, Thorup, Mikkel

We develop a new technique for proving cell-probe lower bounds for static data structures. Previous lower bounds used a reduction to communication games, which was known not to be tight by counting...

In defence of enmity - critiques of liberal globalism (2006)

Thorup, Mikkel

In defence of enmity - critiques of liberal globalism (2006)

Thorup, Mikkel

Survivable composite-link IP network design with OSPF routing (2006)

Diogo V. Andrade, Luciana S. Buriol, Mikkel Thorup

ABSTRACT. OSPF, or Open Shortest Path First, is a commonly used interior gateway protocol. Given a network topology, a set of link types to be deployed, each having a different capacity, and...

Higher lower bounds for near-neighbor and further rich problems (2006)

Sampling to estimate arbitrary subset sums (2005)

We convert cell-probe lower bounds for polynomial space into stronger lower bound for near-linear space. Our technique applies to any lower bound proved through the richness method. For example, it...

Duffield, Nick, Lund, Carsten, Thorup, Mikkel

Starting with a set of weighted items, we want to create a generic sample of a certain size that we can later use to estimate the total weight of arbitrary subsets. For this purpose, we propose...

Estimating arbitrary subset sums with few probes (2005)

Noga Alon, Nick Duffield, Carsten Lund, Mikkel Thorup

Suppose we have a large table T of items i, each with a weight wi, e.g., people and their salary. In a general preprocessing step for estimating arbitrary subset sums, we assign each item a random...

Optimal Combination of Sampled Network Measurements (2005)

Learn more, sample less: Control of volume and variance in network measurement (2005)

IP network traffic is commonly measured at multiple points in order that all traffic passes at least one observation point. The resulting measurements are subsequently joined for network analysis....

Compact name-independent routing with minimum stretch (2004)

Abstract — This paper deals with sampling objects from a large stream. Each object possesses a size, and the aim is to be able to estimate the total size of an arbitrary subset of objects whose...

Ittai Abraham, Noam Nisan, Cyril Gavoille, Dahlia Malkhi, Mikkel Thorup

Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a �O ( √ n) space routing table at each node, and routing along paths of stretch 3, that...

Melding Priority Queues (2004)

Ran Mendelson, Robert E. Tarjan, Mikkel Thorup, Uri Zwick

We show that any priority queue data structure that supports insert, delete, and find-min operations in pq(n) time, when n is an upper bound on the number of elements in the priority queue, can be...

Melding Priority Queues (2004)

Ran Mendelson, Robert E. Tarjan, Mikkel Thorup, Uri Zwick

We show that any priority queue data structure that supports insert, delete, and find-min operations in pq(n) time, when there are up to n elements in the priority queue, can be converted into a...

Compact name-independent routing with minimum stretch (2004)

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, Mikkel Thorup

Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a � O ( √ n) space routing table at each node, and routing along paths of stretch 3, that...

On adaptive integer sorting (2004)

Anna Pagh, Rasmus Pagh, Mikkel Thorup

Abstract. This paper considers integer sorting on a RAM. We show that adaptive sorting of a sequence with qn inversions is asymptotically equivalent to multisorting groups of at most q keys, and a...

Maintaining Information in Fully-Dynamic Trees with Top Trees (2003)

Alstrup, Stephen, Holm, Jacob, De Lichtenberg, Kristian, Thorup, Mikkel

We introduce top trees as a design of a new simpler interface for data structures maintaining information in a fully-dynamic forest. We demonstrate how easy and versatile they are to use on a host of...

Robust optimization of OSPF/IS-IS weights (2003)

Appendix for Tabulation Based 4-Universal Hashing with Applications to Second Moment Estimation A Second (2003)

In this paper, we adapt the heuristic of Fortz and Thorup for optimizing the weights of Shortest Path First protocols such as Open Shortest Path First (OSPF) or Intermediate System-Intermediate...

Moment Estimation, Mikkel Thorup, Yin Zhang

Let ¢¡¤£¦¥¨§�©��§��©�£¦¥��©��©��©�£¦¥��©��be a data stream, where each key¥��is a...

Traffic Engineering with Estimated Traffic Matrices (2003)

Performance of Estimated Traffic Matrices in Traffic Engineering (2003)

Traffic engineering and traffic matrix estimation are often treated as separate fields, even though one of the major applications for a traffic matrix is traffic engineering. In cases where a traffic...

OPT versus LOAD in Dynamic Storage Allocation (2003)

We consider the performance of estimated traffic matrices in traffic engineering. More precisely, we first optimize the routing in an IP backbone to minimize congestion with the estimated traffic...

Adam L. Buchsbaum, Howard Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup

Dynamic Storage Allocation is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L = LOAD...

Efficient Tree Layout in a Multilevel Memory Hierarchy (2002)

Alstrup, Stephen, Bender, Michael A., Demaine, Erik D., Farach-Colton, Martin, Rauhe, Theis, Thorup, Mikkel

We consider the problem of laying out a tree with fixed parent/child structure in hierarchical memory. The goal is to minimize the expected number of block transfers performed during a search along a...

Dynamic Ordered Sets with Exponential Search Trees (2002)

Andersson, Arne, Thorup, Mikkel

We introduce exponential search trees as a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures. This leads to an...

Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut (2002)

Karger, David, Klein, Phil, Stein, Cliff, Thorup, Mikkel, Young, Neal E.

The multiway-cut problem is, given a weighted graph and k >= 2 terminal nodes, to find a minimum-weight set of edges whose removal separates all the terminals. The problem is NP-hard, and even...

Traffic engineering with traditional IP routing protocols (2002)

Ramachandran V. “Oracles for Distances Avoiding a Node-Link Failure (2002)

Traffic engineering involves adapting the routing of traffic to the network conditions, with the joint goals of good user performance and efficient use of network resources. In this paper, we...

Camil Demetrescu, Mikkel Thorup, R. A. Chowdhury, Vijaya Ramach

We consider the problem of preprocessing an edge-weighted directed graph G to answer queries that ask for the shortest distance from any given node x to any other node y avoiding an arbitrary failed...

Optimizing OSPF/IS-IS weights in a changing world (2002)

Bernard Fortz, Associate Member, Mikkel Thorup

Abstract—A system of techniques is presented for optimizing open shortest path first (OSPF) or intermediate system–intermediate system (IS–IS) weights for intradomain routing in a changing...

Traffic engineering with traditional IP routing protocols (2002)

Properties and prediction of flow statistics from sampled packet streams (2002)

Traffic engineering involves adapting the routing of traffic to the network conditions, with the joint goals of good user performance and efficient use of network resources. In this paper, we...

Efficient Tree Layout in a Multilevel Memory Hierarchy (2002)

Abstract--- Many routers can generate and export statistics on flows of packets that traverse them. Increasingly, high end routers form flow statistics from only a sampled packet stream in order to...

Stephen Alstrup, Michael A. Bender, Erik D. Demaine, Martin Farach-colton, J. Ian Munro, Theis Rauhe, ...

We consider the problem of laying out a tree with fixed parent/child structure in hierarchical memory. The goal is to minimize the expected number of block transfers performed during a search along a...

Traffic Engineering with Traditional IP Routing Protocols (2002)

Traffic engineering with traditional IP routing protocols (2002)

Traffic engineering involves adapting the routing of traffic to the network conditions, with the joint goals of good user performance and efficient use of network resources. In this paper, we...

Properties and Prediction of Flow Statistics from Sampled Packet Streams (2002)

Traffic engineering involves adapting the routing of traffic to the network conditions, with the joint goals of good user performance and efficient use of network resources. In this paper, we...

Microsoft Research (2002)

Many routers can generate and export statistics on flows of packets that traverse them. Increasingly, high end routers form flow statistics from only a sampled packet stream in order to manage...

Ministère Recherche, Science Et Technologie, Ministère Recherche, Science Et Technologie, ...

34th ACM Symposium

Dynamic ordered sets with exponential search trees (2002)

Arne Andersson, Mikkel Thorup

We introduce exponential search trees as a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures. This leads to an...

Approximate distance oracles (2001)

Compact Routing Schemes (2001)

Let G = (V; E) be an undirected weighted graph with jV j = n and jEj = m. Let k 1 be an integer. We show that G = (V; E) can be preprocessed in O(kmn

Approximate Distance Oracles (2001)

We describe several compact routing schemes for general weighted undirected networks. Our schemes are simple and easy to implement. The routing tables stored at the nodes of the network are all very...

Approximate distance oracles (2001)

Let G = (V, E) be an undirected weighted graph with |V| = n and |E| = m. Let k ≥ 1 be an integer. We show that G = (V, E) can be preprocessed in O(kmn ) expected time, constructing a data...

An O (n log n) algorithm for the maximum agreement subtree problem for binary trees (2000)

Let G = (V,E) be an undirected weighted graph with |V | = n and |E | = m. Let k ≥ 1 be an integer. We show that G = (V,E) can be preprocessed in O(kmn 1/k) expected time, constructing a data...

Cole, Richard, Farach-Colton, Martin, Hariharan, Ramesh, Przytycka, Teresa, Thorup, Mikkel

The maximum agreement subtree problem is the following. Given two rooted trees whose leaves are drawn from the same set of items (e.g., species), and the largest subset of these items so that the...

An O(n log n) algorithm for the maximum agreement subtree problem for binary trees (2000)

Cole,Richard, Farach-Colton,Martin, Hariharan,Ramesh, Przytycka,Teresa, Thorup,Mikkel

An O(n log n) algorithm for the maximum agreement subtree problem for binary trees (2000)

Cole, Richard, Farach-Colton, Martin, Hariharan, Ramesh, Przytycka, Teresa, Thorup, Mikkel

An O (n log n) algorithm for the maximum agreement subtree problem for binary trees (2000)

Cole, Richard, Farach-Colton, Martin, Hariharan, Ramesh, Przytycka, Teresa, Thorup, Mikkel

The maximum agreement subtree problem is the following. Given two rooted trees whose leaves are drawn from the same set of items (e.g., species), and the largest subset of these items so that the...

Internet traffic engineering by optimizing OSPF weights (2000)

An Experimental Study of Poly-Logarithmic Fully-Dynamic Connectivity Algorithms (2000)

Abstract--- Open Shortest Path First (OSPF) is the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, splitting flow at nodes where several...

Raj D. Iyer, David Karger, Hariharan S. Rahul, Mikkel Thorup, Name David, ...

ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission...

Increasing Internet Capacity Using Local Search (2000)

An Experimental Study of Poly-Logarithmic Fully-Dynamic Connectivity Algorithms (2000)

Open Shortest Path First (OSPF) is the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, splitting flow evenly at nodes where several outgoing...

Raj D. Iyer, David Karger, Hariharan S. Rahul, Mikkel Thorup

this paper we study some algorithms in which t(n) is polylogarithmic.

Word Encoding Tree Connectivity Works (2000)

Stephen Alstrup, Jens Peter Secher, Mikkel Thorup

|Experimentally, we demonstrate the practical relevance of the theoretical trick of encoding trees in words. 1 Introduction In 1983, Gabow and Tarjan [3] showed that union- nd can be supported in...

Internet Traffic Engineering by Optimizing OSPF Weights (2000)

An Experimental Study of Poly-Logarithmic Fully-Dynamic Connectivity Algorithms (2000)

Open Shortest Path First (OSPF) is the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, splitting flow at nodes where several outgoing links are...

Raj Iyer Jr, David Karger, Hariharan S. Rahul, Mikkel Thorup

ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission...

Floats, Integers, and Single Source Shortest Paths (2000)

Floats, Integers, and Single Source Shortest Paths (2000)

Floats are ugly, but to everyone but theoretical computer scientists, they are the real thing. A linear time algorithm is presented for the undirected single source shortest paths problem with...

Mikkel Thorup, Mikkel Thorup

Floats are ugly, but to everyone but theoretical computer scientists, they are the real thing. A linear time algorithm is presented for the undirected single source shortest paths problem with...

Internet traffic engineering by optimizing OSPF weights (2000)

Dominators in linear time (1999)

Abstract—Open Shortest Path First (OSPF) is the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, sptitting flow at nodes where several...

Rounding algorithms for a geometric embedding of minimum multiway cut (1999)

A linear time algorithm is presented for nding dominators in control ow graphs. 1

David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young

Given an undirected graph with edge costs and a subset of k 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The...

Fusion trees can be implemented with AC 0 instructions only. Theoretical Computer Science (1999)

Peter Bro Miltersen, Mikkel Thorup, Arne Andersson, Arne Andersson

is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...

Dominators in Linear Time (1999)

Stephen Alstrup, Dov Harel, Peter W. Lauridsen, Mikkel Thorup

A linear time algorithm is presented for finding dominators in control flow graphs.

Direct routing on trees (1998)

Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, Mikkel Thorup

Poly-logarithmic deterministic fully-dynamic graph algorithms II: 2-edge and biconnectivity (1998)

Kristian De Lichtenberg, Jacob Holm, Jacob Holm, Kristian De Lichtenberg, Mikkel Thorup, Mikkel Thorup

Deterministic fully dynamic algorithms are presented for 2-edge connectivity and biconnectivity. For 2-edge connectivity the amortized cost per operation is O(log 4 n) improving over the previous...

All Structured Programs have Small Tree-Width and Good Register Allocation (1998)

Good Register Allocation, Mikkel Thorup

The register allocation problem for an imperative program is often modelled as the coloring problem of the interference graph of the control-flow graph of the program. The interference graph of a...

Direct routing on trees (Extended Abstract) (1998)

Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, Mikkel Thorup

We consider off-line permutation routing on trees. We are particularly interested in direct tree routing schedules where packets once started move directly towards their destination. The scheduling...

Undirected single source shortest paths in linear time (1997)

Decremental dynamic connectivity (1997)

The single source shortest paths problem (SSSP) is one of the classic problems in algorithmic graph theory: given a weighted graph G with a source vertex s, find the shortest path from s to all other...

Minimizing diameters of dynamic trees (1997)

We consider Las Vegas randomized dynamic algorithms for on-line connectivity problems with deletions only. In particular, we show that starting from a graph with m edges and n nodes, we can maintain...

Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, Mikkel Thorup

Abstract. In this paper we consider an on--line problem related to minimizing the diameter of a dynamic tree T. A new edge f is added, and our task is to delete the edge e of the induced cycle so as...

Undirected single source shortest paths in linear time (1997)

Minimizing diameters of dynamic trees (1997)

The single source shortest paths problem (SSSP) is one of the classic problems in algorithmic graph theory: given a positively weighted graph G with a source vertex s, find the shortest path from s...

Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, Mikkel Thorup

In this paper we consider an on--line problem related to minimizing the diameter of a dynamic tree T. A new edge f is presented, and our task is to delete the edge e of the induced cycle so as to...

Poly-logarithmic deterministic fully-dynamic graph algorithms I: connectivity and minimum spanning tree (1997)

Kristian De Lichtenberg, Jacob Holm, Jacob Holm, Kristian De Lichtenberg, Mikkel Thorup, Mikkel Thorup

Deterministic fully dynamic graph algorithms are presented for connectivity and minimum spanning forest. For connectivity, starting with no edges, the amortized cost for maintaining a spanning forest...

Finding Cores of Limited Length (1997)

Stephen Alstrup, Peter W. Lauridsen, Peer Sommerlund, Mikkel Thorup

In this paper we consider the problem of finding a core of limited length in a tree. A core is a path, which minimizes the sum of the distances to all nodes in the tree. This problem has been...

Sparse Dynamic Programming For Evolutionary-Tree Comparison (1997)

Martin Farach, Mikkel Thorup

. Constructing evolutionary trees for species sets is a fundamental problem in biology. Unfortunately, there is no single agreed upon method for this task, and many methods are in use. Current...

On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics) (1997)

Richa Agarwala, Vineet Bafna, Martin Farach, Babu Narayanan, Mike Paterson, Mikkel Thorup

We consider the problem of fitting an n \Theta n distance matrix D by a tree metric T . Let " be the distance to the closest tree metric under the L1 norm, that is, " = min T fk T \Gamma D...

Dominators in Linear Time (1997)

Sampling to Provide or to Bound: With Applications to Fully Dynamic Graph Algorithms (1997)

A linear time algorithm is presented for finding dominators in control flow graphs. 1 Introduction Finding the dominator tree for a control flow graph is one of the most fundamental problems in the...

Monika Henzinger, Mikkel Thorup

In dynamic graph algorithms the following provide-or-bound problem has to be solved quickly: Given a set S containing a subset R and a way of generating random elements from S testing for membership...

Undirected Single Source Shortest Path in Linear Time (1997)

Mikkel Thorup, Mikkel Thorup

A deterministic linear time and linear space algorithm is presented for the undirected single source shortest path problem. 1 Introduction Let G = (V; E), jV j = n, jEj = m, be an undirected...

Dominators in Linear Time (1997)

An O(n log n) algorithm for the maximum agreement subtree problem for binary trees (1996)

A linear time algorithm is presented for finding dominators in control flow graphs. 1 Introduction Finding the dominator tree for a control flow graph is one of the most fundamental problems in the...

Richard Cole, Martin Farach-colton, Ramesh Hariharan, Teresa Przytycka, Mikkel Thorup

Abstract. The maximum agreement subtree problem is the following. Given two rooted trees whose leaves are drawn from the same set of items (e.g., species), find the largest subset of these items so...

Improved sampling with applications to dynamic graph algorithms (1996)

Monika Rauch Henzinger, Mikkel Thorup

Abstract. We state a new sampling lemma and use it to improve the running time of dynamic graph algorithms. For the dynamic connectivity problem the previously best randomized algorithm takes...

An O(n log n) algorithm for the maximum agreement subtree problem for binary trees (1996)

Richard Cole, Martin Farach-colton, Ramesh Hariharan, Mikkel Thorup

Abstract. The Maximum Agreement Subtree problem is the following: given two rooted trees whose leaves are drawn from the same set of items (e.g., species), find the largest subset of these items so...

An O(n log n) algorithm for the maximum agreement subtree problem for binary trees (1996)

Richard Cole, Martin Farach, Ramesh Hariharan, Teresa Przytycka, Mikkel Thorup

The Maximum Agreement Subtree problem is the following: given two trees whose leaves are drawn from the same set of items (e.g., species), find the largest subset of these items so that the portions...

Static Dictionaries on (1996)

Rams Query, Arne Andersson, Peter Bro Miltersen, Mikkel Thorup

In this paper we consider solutions to the static dictionary problem on AC 0 RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computational...

On RAM priority queues (1996)

Generalized Dominators for Structured Programs (1996)

Priority queues are some of the most fundamental data structures. They are used directly for, say, task scheduling in operating systems. Moreover, they are essential to greedy algorithms. We study...

A Pragmatic Implemention of Monotone Priority Queues (1996)

. Recently it has been discovered that control flow graphs of structured programs have bounded treewidth. In this paper we show that this knowledge can be used to design fast algorithms for control...

Arne Andersson, Mikkel Thorup

Introduction Recently there have been several theoretical improvements in the area of sorting, priority queues, and searching [1, 2, 8, 9]. All these improvements use indirect addressing to surpass...

On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics) (1996)

Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, Mikkel Thorup

. We consider the problem of fitting an n \Theta n distance matrix D by a tree metric T . Let " be the distance to the closest tree metric under the L1 norm, that is, " = minT fk T \Gamma D...

Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations (1996)

Generalized Dominators for Structured Programs (1996)

A randomized sorting algorithm is presented, doing as described in the title. 1 Introduction In this paper we consider sorting on a very simple RAM where the only word-operations are addition, shift,...

Dynamic Graph Algorithms (1996)

. Recently it has been discovered that control flow graphs of structured programs have bounded treewidth. In this paper we show that this knowledge can be used to design fast algorithms for control...

Monika R. Henzinger, Mikkel Thorup, Monika R. Henzinger, Mikkel Thorup

The charter of SRC is to advance both the state of knowledge and the state of the art in computer systems. From our establishment in 1984, we have performed basic and applied research to support...

Dynamic Graph Algorithms (1996)

Monika R. Henzinger, Mikkel Thorup, Monika R. Henzinger, Mikkel Thorup

The charter of SRC is to advance both the state of knowledge and the state of the art in computer systems. From our establishment in 1984, we have performed basic and applied research to support...

Improved Sampling with Applications to Dynamic Graph Algorithms (1995)

Henzinger, Monika, Thorup, Mikkel

We state a new sampling lemma and use it to improve the running time of dynamic graph algorithms. For the dynamic connectivity problem the previously best randomized algorithm takes expected time...

Improved Sampling with Applications to Dynamic Graph Algorithms (1995)

Henzinger, Monika, Thorup, Mikkel

We state a new sampling lemma and use it to improve the running time of dynamic graph algorithms. For the dynamic connectivity problem the previously best randomized algorithm takes expected time...

Equivalence between sorting and priority queues, DIMACS (1995)

On the Agreement of Many Trees (1995)

by

On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics) (1995)

We consider the problem of computing the Maximum Agreement Subtree (MAST) of a set of rooted leaf labeled trees. We give an algorithm which computes the MAST of k trees on n leaves where some tree...

Richa Agarwala, Vineet Bafna, Martin Farach, Babu Narayanan, Mike Paterson, Mikkel Thorup

We consider the problem of fitting an n \Theta n distance matrix D by a tree metric T . Let " be the distance to the closest tree metric, that is, " = min T fk T; D k1 g. First we present...

Structured Programs have Small Tree-Width and Good Register Allocation (1995)

Optimal Algorithms for Finding Nearest Common Ancestors in Dynamic Trees (1995)

The register allocation problem for an imperative program is often modelled as the coloring problem of the interference graph of the control-flow graph of the program. The interference graph of a...

Stephen Alstrup, Mikkel Thorup

We consider the problem of finding the nearest common ancestor of two given nodes x and y (denoted by nca(x; y)) in a dynamic forest of rooted trees. Interspersed with nca-queries are on-line...

On the Agreement of Many Trees (1995)

The Maximum Agreement Subtree Problem for Binary Trees (1995)

We consider the problem of computing the Maximum Agreement Subtree (MAST) of a set of leaf labeled trees. We give an algorithm which computes the MAST of k trees on n species where some tree has...

On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics) (1995)

We consider the problem of computing the Maximum Agreement Subtree (a maximum common topological restriction) of two binary labeled trees. We show that the problem can be solved in O(n log 3 n) using...

Richa Agarwala, Vineet Bafna, Martin Farach, Babu Narayanan, Mike Paterson, Mikkel Thorup

We consider the problem of fitting an n \Theta n distance matrix D by a tree metric T . Let " be the distance to the closest tree metric, that is, " = min T fk T; D k1 g. First we present...

Firing games (1994)