Erik D. Demaine, Dion Harmon, John Iacono, Scu Dynamic Optimality, Jacob Holm, Kristian De Lichtenberg, ...
Advanced topics in data structures: bibliography list #3
[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...
Stephen Alstrup, Jacob Holm, Mikkel Thorup
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...
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...
Improved algorithms for finding level ancestors in dynamic trees (2000)
Abstract. 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...
Top-trees and dynamic graph algorithms /--Jacob Holm, Kristian de Lichtenberg. (1998)
Holm, Jacob., Lichtenberg, Kristian De.
"Department of Computer Science, University of Copenhagen."
Top-Trees and Dynamic Graph Algorithms (1998)
Jacob Holm, Jacob Holm, Kristian De Lichtenberg, Kristian De Lichtenberg
Contents 1 Introduction 3 1.1 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Organisation of this thesis . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Readers...
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...
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...
Jacob Holm, Kristian De Lichtenberg, Jacob Holm, Kristian De Lichtenberg
Department of Computer Science,
Minimizing diameters of dynamic trees (1997)
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...
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...
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...