Erik D. Demaine, Dion Harmon, John Iacono, Scu Dynamic Optimality, Jacob Holm, Kristian De Lichtenberg, ...
Advanced topics in data structures: bibliography list #3
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...