Torben Hagerup

124 papers A* 21A 10B 26C 2Journal 52Unranked 11

Year	Rank	Type	Title / Venue / Authors
2020	J	`jnl`	Space-Efficient DFS and Applications to Connectivity Problems: Simpler, Leaner, Faster. Algorithmica Torben Hagerup
2020	J	`jnl`	Still Simpler Static Level Ancestors. CoRR Torben Hagerup
2019	B	`conf`	A Constant-Time Colored Choice Dictionary with Almost Robust Iteration. MFCS Torben Hagerup
2019	B	`conf`	Fast Breadth-First Search in Still Less Space. WG Torben Hagerup
2019	B	`conf`	Highly Succinct Dynamic Data Structures. FCT Torben Hagerup
2019	B	`conf`	Rank-Select Indices Without Tears. WADS Tim Baumann, Torben Hagerup
2019	J	`jnl`	Space-efficient Euler partition and bipartite edge coloring. Theor. Comput. Sci. Torben Hagerup, Frank Kammer, Moritz Laudahn
2018	J	`jnl`	Fast Breadth-First Search in Still Less Space. CoRR Torben Hagerup
2018	J	`jnl`	Guidesort: Simpler Optimal Deterministic Sorting for the Parallel Disk Model. CoRR Torben Hagerup
2018	J	`jnl`	Small Uncolored and Colored Choice Dictionaries. CoRR Torben Hagerup
2018	J	`jnl`	Space-Efficient DFS and Applications: Simpler, Leaner, Faster. CoRR Torben Hagerup
2017	J	`jnl`	An Optimal Choice Dictionary. CoRR Torben Hagerup
2017	B	`conf`	On-the-Fly Array Initialization in Less Space. ISAAC Torben Hagerup, Frank Kammer
2017	J	`jnl`	On-the-Fly Array Initialization in Less Space. CoRR Torben Hagerup, Frank Kammer
2017	J	`jnl`	Rank-Select Indices Without Tears. CoRR Tim Baumann, Torben Hagerup
2017	C	`conf`	Space-Efficient Euler Partition and Bipartite Edge Coloring. CIAC Torben Hagerup, Frank Kammer, Moritz Laudahn
2016	J	`jnl`	Succinct Choice Dictionaries. CoRR Torben Hagerup, Frank Kammer
2015	—	`conf`	Easy Multiple-Precision Divisors and Word-RAM Constants. MFCS (2) Torben Hagerup
2015	A	`conf`	Space-efficient Basic Graph Algorithms. STACS Amr Elmasry, Torben Hagerup, Frank Kammer
2012	J	`jnl`	A strengthened analysis of an algorithm for Dominating Set in planar graphs. Discret. Appl. Math. Torben Hagerup
2012	B	`conf`	Kernels for Edge Dominating Set: Simpler or Smaller. MFCS Torben Hagerup
2011	J	`jnl`	Finding the maximum suffix with fewer comparisons. J. Discrete Algorithms Gianni Franceschini, Torben Hagerup
2011	B	`conf`	Simpler Linear-Time Kernelization for Planar Dominating Set. IPEC Torben Hagerup
2010	C	`conf`	Finding the Maximum Suffix with Fewer Comparisons. CIAC Gianni Franceschini, Torben Hagerup
2010	J	`jnl`	Trimming of Graphs, with Application to Point Labeling. Theory Comput. Syst. Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, Alexander Wolff
2009	—	`conf`	A Pictorial Description of Cole's Parallel Merge Sort. Efficient Algorithms Torben Hagerup
2009	B	`conf`	An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees. WG Torben Hagerup
2008	J	`jnl`	Trimming of Graphs, with Application to Point Labeling CoRR Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, Alexander Wolff
2008	A	`conf`	Trimming of Graphs, with Application to Point Labeling. STACS Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, Alexander Wolff
2007	B	`conf`	A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs. WG Torben Hagerup
2007	B	`conf`	Online and Offline Access to Short Lists. MFCS Torben Hagerup
2006	J	`jnl`	Simpler Computation of Single-Source Shortest Paths in Linear Average Time. Theory Comput. Syst. Torben Hagerup
2004	—	`ed.`	Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004, Proceedings SWAT Torben Hagerup, Jyrki Katajainen
2004	A	`conf`	Simpler Computation of Single-Source Shortest Paths in Linear Average Time. STACS Torben Hagerup
2003	—	`conf`	On the parameterized complexity of the generalized rush hour puzzle. CCCG Henning Fernau, Torben Hagerup, Naomi Nishimura, Prabhakar Ragde, Klaus Reinhardt
2002	—	`conf`	An Efficient Quasidictionary. SWAT Torben Hagerup, Rajeev Raman
2002	J	`jnl`	Routing Flow Through a Strongly Connected Graph. Algorithmica Thomas Erlebach, Torben Hagerup
2002	A	`conf`	Translating a Planar Object to Maximize Point Containment. ESA Pankaj K. Agarwal, Torben Hagerup, Rahul Ray, Micha Sharir, Michiel H. M. Smid, Emo Welzl
2001	J	`jnl`	Deterministic Dictionaries. J. Algorithms Torben Hagerup, Peter Bro Miltersen, Rasmus Pagh
2001	A	`conf`	Efficient Minimal Perfect Hashing in Nearly Minimal Space. STACS Torben Hagerup, Torsten Tholey
2001	A	`conf`	Simple Minimal Perfect Hashing in Less Space. ESA Martin Dietzfelbinger, Torben Hagerup
2000	J	`jnl`	Dynamic Algorithms for Graphs of Bounded Treewidth. Algorithmica Torben Hagerup
2000	A*	`conf`	Improved Shortest Paths on the Word RAM. ICALP Torben Hagerup
2000	J	`jnl`	Parallel Preprocessing for Path Queries without Concurrent Reading. Inf. Comput. Torben Hagerup
2000	J	`jnl`	Self-Simulation for the Passive Optical Star. J. Algorithms Pascal Berthomé, Torben Hagerup, Ilan Newman, Assaf Schuster
2000	J	`jnl`	Tight Bounds for Searching a Sorted Array of Strings. SIAM J. Comput. Arne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson
1999	A*	`conf`	Fast Deterministic Construction of Static Dictionaries. SODA Torben Hagerup
1998	—	`conf`	An Implementation of the Binary Blocking Flow Algorithm. WAE Torben Hagerup, Peter Sanders, Jesper Larsson Träff
1998	J	`jnl`	Characterizing Multiterminal Flow Networks and Computing Flows in Networks of Small Treewidth. J. Comput. Syst. Sci. Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, Prabhakar Ragde
1998	J	`jnl`	More General Parallel Tree Contraction: Register Allocation and Broadcasting in a Tree. Theor. Comput. Sci. Krzysztof Diks, Torben Hagerup
1998	J	`jnl`	Parallel Algorithms with Optimal Speedup for Bounded Treewidth. SIAM J. Comput. Hans L. Bodlaender, Torben Hagerup
1998	A*	`conf`	Simpler and Faster Dictionaries on the AC ICALP Torben Hagerup
1998	A	`conf`	Sorting and Searching on the Word RAM. STACS Torben Hagerup
1998	J	`jnl`	Sorting in Linear Time? J. Comput. Syst. Sci. Arne Andersson, Torben Hagerup, Stefan Nilsson, Rajeev Raman
1998	B	`conf`	Tree Decompositions of Small Diameter. MFCS Hans L. Bodlaender, Torben Hagerup
1997	J	`jnl`	A Reliable Randomized Algorithm for the Closest-Pair Problem. J. Algorithms Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, Martti Penttonen
1997	J	`jnl`	Allocating Independent Tasks to Parallel Processors: An Experimental Study. J. Parallel Distributed Comput. Torben Hagerup
1997	A*	`conf`	Dynamic Algorithms for Graphs of Bounded Treewidth. ICALP Torben Hagerup
1997	J	`jnl`	Fast Integer Merging on the EREW PRAM. Algorithmica Torben Hagerup, Miroslaw Kutylowski
1997	J	`jnl`	Improved Parallel Integer Sorting without Concurrent Writing. Inf. Comput. Susanne Albers, Torben Hagerup
1996	—	`conf`	Allocating Independent Tasks to Parallel Processors: An Experimental Study. IRREGULAR Torben Hagerup
1996	J	`jnl`	An o(n³)-Time Algorithm Maximum-Flow Algorithm. SIAM J. Comput. Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn
1996	B	`conf`	More General Parallel Tree Contraction: Register Allocation and Broadcasting in a Tree. WG Krzysztof Diks, Torben Hagerup
1995	J	`jnl`	A Lower Bound for the Emulation of PRAM Memories on Processor Networks Inf. Comput. Torben Hagerup
1995	J	`jnl`	A Randomized Maximum-Flow Algorithm. SIAM J. Comput. Joseph Cheriyan, Torben Hagerup
1995	A*	`conf`	Characterizations of k-Terminal Flow Networks and Computing Network Flows in Partial k-Trees. SODA Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, Prabhakar Ragde
1995	J	`jnl`	Fast Deterministic Processor Allocation. J. Algorithms Torben Hagerup
1995	J	`jnl`	Fast Parallel Permutation Algorithms. Parallel Process. Lett. Torben Hagerup, Jörg Keller
1995	J	`jnl`	Fast Parallel Space Allocation, Estimation and Integer Sorting. Inf. Comput. Hannah Bast, Torben Hagerup
1995	B	`conf`	More Efficient Parallel Flow Algorithms. ISAAC Jürgen Dedorath, Jordan Gergov, Torben Hagerup
1995	A*	`conf`	Parallel Algorithms with Optimal Speedup for Bounded Treewidth. ICALP Hans L. Bodlaender, Torben Hagerup
1995	A	`conf`	Self-Simulation for the Passive Optical Star Model. ESA Pascal Berthomé, Th. Duboux, Torben Hagerup, Ilan Newman, Assaf Schuster
1995	A*	`conf`	Sorting in linear time? STOC Arne Andersson, Torben Hagerup, Stefan Nilsson, Rajeev Raman
1995	J	`jnl`	The Parallel Complexity of Integer Prefix Summation. Inf. Process. Lett. Torben Hagerup
1994	J	`jnl`	Generalized Topological Sorting in Linear Time. Nord. J. Comput. Torben Hagerup, Martin Maas
1994	A*	`conf`	Optimal parallel string algorithms: sorting, merging and computing the minimum. STOC Torben Hagerup
1994	B	`conf`	Prefix Graphs and Their Applications. WG Shiva Chaudhuri, Torben Hagerup
1994	A*	`conf`	The complexity of searching a sorted array of strings. STOC Arne Andersson, Torben Hagerup, Johan Håstad, Ola Petersson
1993	B	`conf`	Approximate and Exact Deterministic Parallel Selection. MFCS Shiva Chaudhuri, Torben Hagerup, Rajeev Raman
1993	J	`jnl`	Drawing Graphs in the Plane with High Resolution. SIAM J. Comput. Michael Formann, Torben Hagerup, James Haralambides, Michael Kaufmann, Frank Thomson Leighton, Antonios Symvonis, Emo Welzl, Gerhard J. Woeginger
1993	B	`conf`	Fast Deterministic Approximate and Exact Parallel Sorting. SPAA Torben Hagerup, Rajeev Raman
1993	A*	`conf`	Fast Deterministic Processor Allocation. SODA Torben Hagerup
1993	B	`conf`	Generalized Topological Sorting in Linear Time. FCT Torben Hagerup, Martin Maas
1993	A*	`conf`	Maintaining Discrete Probability Distributions Optimally. ICALP Torben Hagerup, Kurt Mehlhorn, J. Ian Munro
1992	B	`conf`	A Perfect Parallel Dictionary. MFCS Hannah Bast, Martin Dietzfelbinger, Torben Hagerup
1992	J	`jnl`	FORK: A high-level language for PRAMs. Future Gener. Comput. Syst. Torben Hagerup, Arno Schmitt, Helmut Seidl
1992	A*	`conf`	Fast Integer Merging on the EREW PRAM. ICALP Torben Hagerup
1992	A	`conf`	Fast and Optimal Simulations between CRCW PRAMs. STACS Torben Hagerup
1992	A*	`conf`	Improved Parallel Integer Sorting Without Concurrent Writing. SODA Susanne Albers, Torben Hagerup
1992	B	`conf`	Merging and Sorting Strings in Parallel. MFCS Torben Hagerup, Ola Petersson
1992	J	`jnl`	On a Compaction Theorem of Ragde. Inf. Process. Lett. Torben Hagerup
1992	A	`conf`	The Log-Star Revolution. STACS Torben Hagerup
1992	A*	`conf`	Waste Makes Haste: Tight Bounds for Loose Parallel Sorting FOCS Torben Hagerup, Rajeev Raman
1991	A*	`conf`	Constant-Time Parallel Integer Sorting (Extended Abstract) STOC Torben Hagerup
1991	—	`conf`	FORK: A High-Level Language for PRAMs. PARLE (1) Torben Hagerup, Arno Schmitt, Helmut Seidl
1991	A*	`conf`	Fast Parallel Generation of Random Permutations. ICALP Torben Hagerup
1991	B	`conf`	Fast and Reliable Parallel Hashing. SPAA Hannah Bast, Torben Hagerup
1991	J	`jnl`	Improved Deterministic Parallel Integer Sorting Inf. Comput. P. C. P. Bhatt, Krzysztof Diks, Torben Hagerup, V. C. Prasad, Tomasz Radzik, Sanjeev Saxena
1990	J	`jnl`	A Guided Tour of Chernoff Bounds. Inf. Process. Lett. Torben Hagerup, Christine Rüb
1990	A*	`conf`	Can A Maximum Flow be Computed on o(nm) Time? ICALP Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn
1990	A*	`conf`	Drawing Graphs in the Plane with High Resolution FOCS Michael Formann, Torben Hagerup, James Haralambides, Michael Kaufmann, Frank Thomson Leighton, Antonios Symvonis, Emo Welzl, Gerhard J. Woeginger
1990	B	`conf`	Efficient Parallel Computation of Arrangements of Hyperplanes in d Dimensions. SPAA Torben Hagerup, H. Jung, Emo Welzl
1990	B	`conf`	Every Robust CRCW PRAM Can Efficiently Simulate a PRIORITY PRAM. SPAA Torben Hagerup, Tomasz Radzik
1990	J	`jnl`	Improved Nonconservative Sequential and Parallel Integer Sorting. Inf. Process. Lett. Torben Hagerup, Hong Shen
1990	—	`conf`	Neue Algorithmen für das Maximum-Flow-Problem. GI Jahrestagung (2) Torben Hagerup
1990	J	`jnl`	Optimal Parallel Algorithms on Planar Graphs Inf. Comput. Torben Hagerup
1990	J	`jnl`	Planar Depth-First Search in O(log n) Parallel Time. SIAM J. Comput. Torben Hagerup
1989	A*	`conf`	A Randomized Maximum-Flow Algorithm FOCS Joseph Cheriyan, Torben Hagerup
1989	J	`jnl`	Hybridsort Revisited and Parallelized. Inf. Process. Lett. Torben Hagerup
1989	B	`conf`	New Simulations between CRCW PRAMs. FCT Bogdan S. Chlebus, Krzysztof Diks, Torben Hagerup, Tomasz Radzik
1989	J	`jnl`	Optimal Merging and Sorting on the Erew Pram. Inf. Process. Lett. Torben Hagerup, Christine Rüb
1989	J	`jnl`	Optimal Parallel 5-Colouring of Planar Graphs. SIAM J. Comput. Torben Hagerup, Marek Chrobak, Krzysztof Diks
1989	B	`conf`	Optimal Parallel Algorithms For The Recognition And Colouring Outerplanar Graphs (Extended Abstract). MFCS Krzysztof Diks, Torben Hagerup, Wojciech Rytter
1989	A*	`conf`	Parallel Retrieval of Scattered Information. ICALP Torben Hagerup, Manfred Nowak
1988	B	`conf`	Efficient Simulations Between Concurrent-Read Concurrent-Write PRAM Models. MFCS Bogdan S. Chlebus, Krzysztof Diks, Torben Hagerup, Tomasz Radzik
1988	J	`jnl`	On Saving Space in Parallel Computation (Note). Inf. Process. Lett. Torben Hagerup
1988	—	`conf`	Optimal Parallel Algorithms on Planar Graphs. AWOC Torben Hagerup
1988	—	`—`	Parallel algorithms on planar graphs. Torben Hagerup
1987	J	`jnl`	Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones. SIAM J. Comput. Helmut Alt, Torben Hagerup, Kurt Mehlhorn, Franco P. Preparata
1987	—	`conf`	Deterministic Simulation of Idealized Parallel Computers on more Realistic Ones. Parallel Algorithms and Architectures Helmut Alt, Torben Hagerup, Kurt Mehlhorn, Franco P. Preparata
1987	A*	`conf`	Parallel 5-Colouring of Planar Graphs. ICALP Torben Hagerup, Marek Chrobak, Krzysztof Diks
1987	J	`jnl`	Towards Optimal Parallel Bucket Sorting Inf. Comput. Torben Hagerup
1986	—	`conf`	A Generalized Topological Sorting Problem. Aegean Workshop on Computing Torben Hagerup, Wolfgang Rülling
1986	B	`conf`	Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones. MFCS Helmut Alt, Torben Hagerup, Kurt Mehlhorn, Franco P. Preparata