Stephen Alstrup

Time and Space Efficient Multi-Method Dispatching (2001)

We consider the problem of maintaining a string of n brackets ( or ) under the operation reverse(i) that changes the ith bracket from ( to ) or vice versa, and returns yes if and only if the...

Copyright C, Stephen Alstrup, Gerth Stlting Brodal, Inge Li Grtz, Theis Rauhe

The dispatching problem for object oriented languages is the problem of determining the most specialized method to invoke for calls at run-time. This can be a critical component of execution...

Identifying Nearest Common Ancestors in a Distributed Environment (2001)

Stephen Alstrup, Cyril Gavoille, Haim Kaplan, Theis Rauhe

We give a simple algorithm that labels the nodes of a rooted tree such that from the labels of two nodes alone one can compute in constant time the label of their nearest common ancestor. The labels...

Improved Labeling Scheme for Ancestor Queries (2001)

Stephen Alstrup, Theis Rauhe

We present a labeling scheme for rooted trees that supports ancestor queries. Given a tree, the scheme assigns to each node a label which is a binary string. Given the labels of any two nodes u and...

Finding Cores of Limited Length (2001)

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

In this paper we consider several well-studied variants of the problem of finding a core of a prescribed length in a tree. Here a core is a path minimizing the sum of the distances to all nodes in...

A Cell Probe Lower Bound for Dynamic Nearest-Neighbour Searching (2001)

Optimal Static Range Reporting in One Dimension (2001)

This paper proves lower bounds for the dynamic NNS problem in two dimensions with respect to the Euclidean norm in nite precision models. The lower bound holds in the cell probe model, so it can be...

New Data Structures for Orthogonal Range Searching (2001)

We consider static one dimensional range searching problems. These problems are to build static data structures for an integer set S

Optimal Static Range Reporting in One Dimension (2000)

We present new general techniques for static orthogonal range searching problems in two and higher dimensions. For the general range reporting problem in R 3 , we achieve query time O(log n+ k) using...

Optimal Static Range Reporting in One Dimension (2000)

We consider static one dimensional range searching problems. These problems are to build static data structures for an integer set S U , where U = f0; 1; : : : ; 2 w 1g, which support various queries...

Gerth S. Brodal, Stephen Alstrup, Gerth Stlting Brodal, Theis Rauhe

We consider static one dimensional range searching problems. These problems are to build static data structures for an integer set S U , where U = f0; 1; : : : ; 2 w 1g, which support various queries...

A Cell Probe Lower Bound for Dynamic Nearest-Neighbour Searching (2000)

Word Encoding Tree Connectivity Works (2000)

This paper proves lower bounds for the dynamic NNS problem in two dimensions with respect to the Euclidean norm in nite precision models. The lower bound holds in the cell probe model, so it can be...

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...

Dominators in Linear Time (2000)

Stephen Alstrup, Dov Harel, Peter W. Lauridsen Mikkel

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

Dominators in Linear Time (2000)

Stephen Alstrup, Peter W. Lauridsen, Mikkel Thorup

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

Optimal On-line Decremental Connectivity in Trees (2000)

Stephen Alstrup, Jens Peter Secher, Maz Spork

Let T be a tree with n nodes from which edges are deleted interspersed with m on-line connectivity queries. Even and Shiloach gave an O(n log n + m) algorithm to process edge deletion and m queries...

Minimizing Diameters of Dynamic Trees (2000)

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 added, and our task is to delete the edge e of the induced cycle so as to...

Improved Algorithms for Finding Level Ancestors in Dynamic Trees (2000)

Stephen Alstrup, Jacob Holm

Given a node x at depth d in a rooted tree LevelAncestor(x; i) returns the ancestor to x in depth d i. We show how to maintain a tree under addition of new leaves so that updates and level ancestor...

Direct Routing on Trees (2000)

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...

Maintaining Center and Median in Dynamic Trees (2000)

New Data Structures for Orthogonal Range Searching (2000)

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 O(log n)...

Pattern Matching in Dynamic Texts (2000)

We present new general techniques for static orthogonal range searching problems in two and higher dimensions. For the general range reporting problem in R^3, we achieve query time O(log n + k) using...

Optimal On-line Decremental Connectivity in Trees (2000)

Pattern matching is the problem of finding all occurrences of a pattern in a text. In a dynamic setting the problem is to support pattern matching in a text which can be manipulated on-line, i.e.,...

Stephen Alstrup, Jens Peter Secher, Maz Spork

Let T be a tree with n nodes from which edges are deleted interspersed with m on-line connectivity queries. Even and Shiloach gave an O(n log n + m) algorithm to process edge deletion and m queries...

Pattern Matching in Dynamic Texts (1999)

Worst-case and Amortised Optimality in Union-Find (Extended abstract ) (1999)

Pattern matching is the problem of nding all occurrences of a pattern in a text. In a dynamic setting the problem is to support pattern matching in a text which can be manipulated on-line, i.e., the...

Stephen Alstrup, Amir M. Ben-amram, Theis Rauhe

We study the interplay between worst-case and amortised time bounds for the classic Disjoint Set Union problem (Union-Find). We ask whether it is possible to achieve optimal worst-case and amortised...

Marked Ancestor Problems (1998)

Optimal On-line Decremental Connectivity in Trees (1998)

Consider a rooted tree whose nodes can be marked or unmarked. Given a node, we want to find its nearest marked ancestor. This generalises the well-known predecessor problem, where the tree is a path.

Stephen Alstrup, Jens Peter Secher, Maz Spork

Let T be a tree with n nodes from which edges are deleted interspersed with m on-line connectivity queries. Even and Shiloach gave an O(n log n + m) algorithm to process edge deletion and m queries...

Dominators in Linear Time (1998)

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 (Extended Abstract) (1997)

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...

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...

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...

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...

Minimizing Diameters of Dynamic Trees (1997)

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 added, and our task is to delete the edge e of the induced cycle so as to...

Generalized Dominators for Structured Programs (1997)

Dominators in Linear Time (1997)

. 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...

Stephen Alstrup, Peter W. Lauridsen, Mikkel Thorup

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...

Minimizing Diameters of Dynamic Trees (1997)

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...

Dominators in Linear Time (1996)

Stephen Alstrup, Peter W. Lauridsen, Mikkel Thorup

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...

Generalized Dominators for Structured Programs (1996)

An O(|V|*|E|) Algorithm for Finding Immediate Multiple-Vertex Dominators. (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...

Stephen Alstrup, Jens Clausen

We present an O(jV j jEj) algorithm for finding immediate multiple-vertex dominators in a graph with vertices V and edges E. 1 Introduction. Finding dominators in a graph has been investigated in...

Algorithm for Finding Immediate Multiple-Vertex Dominators. (1996)

Stephen Alstrup, Jens Clausen

We present an O(jV j jEj) algorithm for finding immediate multiple-vertex dominators in a graph with vertices V and edges E. 1 Introduction. Finding dominators in a graph has been investigated in...

A Simple Dynamic Algorithm for Maintaining a Dominator Tree (1996)

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

We present a simple algorithm which maintains the dominator tree for an arbitrary flow graph during a sequence of i edge insertions interspersed with q queries as "does x dominate y?". The complexity...

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...

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

A Simple and Optimal Algorithm for Finding Immediate Dominators in Reducible Graphs (1996)

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

A Simple Dynamic Algorithm for Maintaining a Dominator Tree (1996)

We present two simple algorithm for finding immediate dominator in reducible graphs with n nodes and m edges: A O(n + m) RAM algorithm and a O(n +m log log n) pointer machine algorithm. 1...

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

We present a simple algorithm which maintains the dominator tree for an arbitrary flow graph during a sequence of i edge insertions interspersed with q queries as "does x dominate y?". The complexity...

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

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

Algorithm for Finding Immediate Multiple-Vertex Dominators. (1970)

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

Stephen Alstrup, Jens Clausen

We present an O(jV j jEj) algorithm for finding immediate multiple-vertex dominators in a graph with vertices V and edges E. 1 Introduction. Finding dominators in a graph has been investigated in...

A Simple Dynamic Algorithm for Maintaining a Dominator Tree (1970)