Torben Hagerup

CoRR, 2020

Space-Efficient DFS and Applications to Connectivity Problems: Simpler, Leaner, Faster.

[BibT_eX]

[DOI]

Algorithmica, 2020

2019

Fast Breadth-First Search in Still Less Space.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2019

Rank-Select Indices Without Tears.

[BibT_eX]

[DOI]

Tim Baumann

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

A Constant-Time Colored Choice Dictionary with Almost Robust Iteration.

[BibT_eX]

[DOI]

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

Highly Succinct Dynamic Data Structures.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 22nd International Symposium, 2019

2018

Small Uncolored and Colored Choice Dictionaries.

[BibT_eX]

[DOI]

CoRR, 2018

Guidesort: Simpler Optimal Deterministic Sorting for the Parallel Disk Model.

[BibT_eX]

[DOI]

CoRR, 2018

Space-Efficient DFS and Applications: Simpler, Leaner, Faster.

[BibT_eX]

[DOI]

CoRR, 2018

2017

An Optimal Choice Dictionary.

[BibT_eX]

[DOI]

CoRR, 2017

On-the-Fly Array Initialization in Less Space.

[BibT_eX]

[DOI]

Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

Space-Efficient Euler Partition and Bipartite Edge Coloring.

[BibT_eX]

[DOI]

Moritz Laudahn

Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

2016

Succinct Choice Dictionaries.

[BibT_eX]

[DOI]

CoRR, 2016

2015

Space-efficient Basic Graph Algorithms.

[BibT_eX]

[DOI]

Amr Elmasry

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Easy Multiple-Precision Divisors and Word-RAM Constants.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

2012

A strengthened analysis of an algorithm for Dominating Set in planar graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2012

Kernels for Edge Dominating Set: Simpler or Smaller.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

2011

Simpler Linear-Time Kernelization for Planar Dominating Set.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 6th International Symposium, 2011

2010

Finding the Maximum Suffix with Fewer Comparisons.

[BibT_eX]

[DOI]

Gianni Franceschini

Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

2009

An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2009

A Pictorial Description of Cole's Parallel Merge Sort.

[BibT_eX]

[DOI]

Proceedings of the Efficient Algorithms, 2009

2008

Trimming of Graphs, with Application to Point Labeling.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, 2008

2007

A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2007

Online and Offline Access to Short Lists.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

2004

Simpler Computation of Single-Source Shortest Paths in Linear Average Time.

[BibT_eX]

[DOI]

Proceedings of the STACS 2004, 2004

2003

On the parameterized complexity of the generalized rush hour puzzle.

[BibT_eX]

[DOI]

Proceedings of the 15th Canadian Conference on Computational Geometry, 2003

2002

Routing Flow Through a Strongly Connected Graph.

[BibT_eX]

[DOI]

Thomas Erlebach

Algorithmica, 2002

An Efficient Quasidictionary.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2002

Translating a Planar Object to Maximize Point Containment.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2002

2001

Deterministic Dictionaries.

[BibT_eX]

[DOI]

Peter Bro Miltersen

Rasmus Pagh

J. Algorithms, 2001

Efficient Minimal Perfect Hashing in Nearly Minimal Space.

[BibT_eX]

[DOI]

Torsten Tholey

Proceedings of the STACS 2001, 2001

Simple Minimal Perfect Hashing in Less Space.

[BibT_eX]

[DOI]

Martin Dietzfelbinger

Proceedings of the Algorithms, 2001

2000

Tight Bounds for Searching a Sorted Array of Strings.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

Self-Simulation for the Passive Optical Star.

[BibT_eX]

[DOI]

J. Algorithms, 2000

Parallel Preprocessing for Path Queries without Concurrent Reading.

[BibT_eX]

[DOI]

Inf. Comput., 2000

Improved Shortest Paths on the Word RAM.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

Fast Deterministic Construction of Static Dictionaries.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998

Characterizing Multiterminal Flow Networks and Computing Flows in Networks of Small Treewidth.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1998

An Implementation of the Binary Blocking Flow Algorithm.

[BibT_eX]

Peter Sanders

Jesper Larsson Träff

Proceedings of the Algorithm Engineering, 2nd International Workshop, 1998

Sorting and Searching on the Word RAM.

[BibT_eX]

[DOI]

Proceedings of the STACS 98, 1998

Tree Decompositions of Small Diameter.

[BibT_eX]

[DOI]

Hans L. Bodlaender

Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

Simpler and Faster Dictionaries on the AC<sup>0</sup> RAM.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

1997

A Reliable Randomized Algorithm for the Closest-Pair Problem.

[BibT_eX]

[DOI]

Martin Dietzfelbinger

Jyrki Katajainen

Martti Penttonen

J. Algorithms, 1997

Fast Integer Merging on the EREW PRAM.

[BibT_eX]

[DOI]

Miroslaw Kutylowski

Algorithmica, 1997

Dynamic Algorithms for Graphs of Bounded Treewidth.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

1996

An o(n³)-Time Algorithm Maximum-Flow Algorithm.

[BibT_eX]

[DOI]

Joseph Cheriyan

Kurt Mehlhorn

SIAM J. Comput., 1996

More General Parallel Tree Contraction: Register Allocation and Broadcasting in a Tree.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1996

Allocating Independent Tasks to Parallel Processors: An Experimental Study.

[BibT_eX]

[DOI]

Proceedings of the Parallel Algorithms for Irregularly Structured Problems, 1996

1995

A Lower Bound for the Emulation of PRAM Memories on Processor Networks

[BibT_eX]

[DOI]

Inf. Comput., May, 1995

Fast Parallel Permutation Algorithms.

[BibT_eX]

[DOI]

Jörg Keller

Parallel Process. Lett., 1995

The Parallel Complexity of Integer Prefix Summation.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1995

Fast Parallel Space Allocation, Estimation and Integer Sorting.

[BibT_eX]

[DOI]

Hannah Bast

Inf. Comput., 1995

Sorting in linear time?

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Characterizations of k-Terminal Flow Networks and Computing Network Flows in Partial k-Trees.

[BibT_eX]

[DOI]

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

More Efficient Parallel Flow Algorithms.

[BibT_eX]

[DOI]

Jürgen Dedorath

Jordan Gergov

Proceedings of the Algorithms and Computation, 6th International Symposium, 1995

Parallel Algorithms with Optimal Speedup for Bounded Treewidth.

[BibT_eX]

[DOI]

Hans L. Bodlaender

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Self-Simulation for the Passive Optical Star Model.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1995

1994

Prefix Graphs and Their Applications.

[BibT_eX]

[DOI]

Shiva Chaudhuri

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1994

Optimal parallel string algorithms: sorting, merging and computing the minimum.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

The complexity of searching a sorted array of strings.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

1993

Fast Deterministic Approximate and Exact Parallel Sorting.

[BibT_eX]

[DOI]

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

Fast Deterministic Processor Allocation.

[BibT_eX]

[DOI]

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Approximate and Exact Deterministic Parallel Selection.

[BibT_eX]

[DOI]

Shiva Chaudhuri

Proceedings of the Mathematical Foundations of Computer Science 1993, 1993

Maintaining Discrete Probability Distributions Optimally.

[BibT_eX]

[DOI]

Kurt Mehlhorn

J. Ian Munro

Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

Generalized Topological Sorting in Linear Time.

[BibT_eX]

[DOI]

Martin Maas

Proceedings of the Fundamentals of Computation Theory, 9th International Symposium, 1993

1992

On a Compaction Theorem of Ragde.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1992

The Log-Star Revolution.

[BibT_eX]

[DOI]

Proceedings of the STACS 92, 1992

Fast and Optimal Simulations between CRCW PRAMs.

[BibT_eX]

[DOI]

Proceedings of the STACS 92, 1992

Improved Parallel Integer Sorting Without Concurrent Writing.

[BibT_eX]

[DOI]

Susanne Albers

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Merging and Sorting Strings in Parallel.

[BibT_eX]

[DOI]

Ola Petersson

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

A Perfect Parallel Dictionary.

[BibT_eX]

[DOI]

Hannah Bast

Martin Dietzfelbinger

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Fast Integer Merging on the EREW PRAM.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

Waste Makes Haste: Tight Bounds for Loose Parallel Sorting

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

Improved Deterministic Parallel Integer Sorting

[BibT_eX]

[DOI]

Inf. Comput., September, 1991

Constant-Time Parallel Integer Sorting (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Fast and Reliable Parallel Hashing.

[BibT_eX]

[DOI]

Hannah Bast

Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, 1991

FORK: A High-Level Language for PRAMs.

[BibT_eX]

[DOI]

Arno Schmitt

Helmut Seidl

Proceedings of the PARLE '91: Parallel Architectures and Languages Europe, 1991

Fast Parallel Generation of Random Permutations.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

1990

Planar Depth-First Search in O(log n) Parallel Time.

[BibT_eX]

[DOI]

SIAM J. Comput., 1990

Improved Nonconservative Sequential and Parallel Integer Sorting.

[BibT_eX]

[DOI]

Hong Shen

Inf. Process. Lett., 1990

A Guided Tour of Chernoff Bounds.

[BibT_eX]

[DOI]

Christine Rüb

Inf. Process. Lett., 1990

Every Robust CRCW PRAM Can Efficiently Simulate a PRIORITY PRAM.

[BibT_eX]

[DOI]

Tomasz Radzik

Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990

Efficient Parallel Computation of Arrangements of Hyperplanes in d Dimensions.

[BibT_eX]

[DOI]

H. Jung

Emo Welzl

Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990

Can A Maximum Flow be Computed on o(nm) Time?

[BibT_eX]

[DOI]

Joseph Cheriyan

Kurt Mehlhorn

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

Neue Algorithmen für das Maximum-Flow-Problem.

[BibT_eX]

[DOI]

Proceedings of the GI, 1990

Drawing Graphs in the Plane with High Resolution

[BibT_eX]

[DOI]

Frank Thomson Leighton

Antonios Symvonis

Emo Welzl

Gerhard J. Woeginger

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

Optimal Parallel 5-Colouring of Planar Graphs.

[BibT_eX]

[DOI]

Marek Chrobak

SIAM J. Comput., 1989

Optimal Merging and Sorting on the Erew Pram.

[BibT_eX]

[DOI]

Christine Rüb

Inf. Process. Lett., 1989

Hybridsort Revisited and Parallelized.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1989

Optimal Parallel Algorithms For The Recognition And Colouring Outerplanar Graphs (Extended Abstract).

[BibT_eX]

[DOI]

Wojciech Rytter

Proceedings of the Mathematical Foundations of Computer Science 1989, 1989

Parallel Retrieval of Scattered Information.

[BibT_eX]

[DOI]

Manfred Nowak

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

A Randomized Maximum-Flow Algorithm

[BibT_eX]

[DOI]

Joseph Cheriyan

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

New Simulations between CRCW PRAMs.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 1989

1988

Parallel algorithms on planar graphs.

[BibT_eX]

[DOI]

PhD thesis, 1988

On Saving Space in Parallel Computation (Note).

[BibT_eX]

[DOI]

Inf. Process. Lett., 1988

Efficient Simulations Between Concurrent-Read Concurrent-Write PRAM Models.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

Optimal Parallel Algorithms on Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987

Towards Optimal Parallel Bucket Sorting

[BibT_eX]

[DOI]

Inf. Comput., October, 1987

Deterministic Simulation of Idealized Parallel Computers on more Realistic Ones.

[BibT_eX]

[DOI]

Proceedings of the Parallel Algorithms and Architectures, 1987

Parallel 5-Colouring of Planar Graphs.

[BibT_eX]

[DOI]

Marek Chrobak

Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

1986

A Generalized Topological Sorting Problem.

[BibT_eX]

[DOI]