Torben Hagerup

MFCS Conference 2019 Conference Paper

A Constant-Time Colored Choice Dictionary with Almost Robust Iteration

• Torben Hagerup

A (colored) choice dictionary is a data structure that is initialized with positive integers n and c and subsequently maintains a sequence of n elements of {0, .. ., c-1}, called colors, under operations to inspect and to update the color in a given position and to return the position of an occurrence of a given color. Choice dictionaries are fundamental in space-efficient computing. Some applications call for the additional operation of dynamic iteration, i. e. , enumeration of the positions containing a given color while the sequence of colors may change. An iteration is robust if it enumerates every position that contains the relevant color throughout the iteration but never enumerates a position more than once or when it does not contain the color in question. We describe the first choice dictionary that executes every operation in constant amortized time and almost robust iteration in constant amortized time per element enumerated. The iteration is robust, except that it may enumerate some elements a second time. The data structure occupies n log_2 c+O((log n)^2) bits. The time and space bounds assume that c=O((log n)^{1/2}(log log n)^{-{3/2}}).

TCS Journal 2019 Journal Article

Space-efficient Euler partition and bipartite edge coloring

• Torben Hagerup
• Frank Kammer
• Moritz Laudahn

We describe space-efficient algorithms for two problems on undirected multigraphs: Euler partition (partitioning the edges into a minimum number of trails); and bipartite edge coloring (coloring the edges of a bipartite multigraph with the minimum number of colors). Let n, m and Δ ≥ 1 be the numbers of vertices and of edges and the maximum degree, respectively, of the input multigraph. For Euler partition we reduce the amount of working memory needed by a logarithmic factor, from Θ ( ( n + m ) log ⁡ ( n + m ) ) bits to O ( n + m ) bits, while preserving a running time of O ( n + m ). For bipartite edge coloring, still using O ( n + m ) bits of working memory, we achieve a running time of O ( n + m min ⁡ { Δ, log ⁡ Δ ( log ⁎ ⁡ Δ + ( log ⁡ m log ⁡ Δ ) / Δ ) } ). This is O ( m log ⁡ Δ log ⁎ ⁡ Δ ) if m = Ω ( n log ⁡ n log ⁡ log ⁡ n / log ⁎ ⁡ n ), to be compared with O ( m log ⁡ Δ ) for the fastest known algorithm. Instrumental in obtaining the latter result is a new data structure presented here, the subgraph stack, that allows graph algorithms centered around recursive calls on substantially smaller subgraphs to be implemented in a space-efficient manner.

MFCS Conference 2012 Conference Paper

Kernels for Edge Dominating Set: Simpler or Smaller

• Torben Hagerup

Abstract A kernelization for a parameterized computational problem is a polynomial-time procedure that transforms every instance of the problem into an equivalent instance (the so-called kernel ) whose size is bounded by a function of the value of the chosen parameter. We present new kernelizations for the NP-complete Edge Dominating Set problem which asks, given an undirected graph G = ( V, E ) and an integer k, whether there exists a subset D ⊆ E with | D | ≤ k such that every edge in E shares at least one endpoint with some edge in D. The best previous kernelization for Edge Dominating Set, due to Xiao, Kloks and Poon, yields a kernel with at most 2 k 2 + 2 k vertices in linear time. We first describe a very simple linear-time kernelization whose output has at most 4 k 2 + 4 k vertices and is either a trivial “no” instance or a vertex-induced subgraph of the input graph in which every edge dominating set of size ≤ k is also an edge dominating set of the input graph. We then show that a refinement of the algorithm of Xiao, Kloks and Poon and a different analysis can lower the bound on the number of vertices in the kernel by a factor of about 4, namely to \(\max\{\frac{1}{2}k^2+\frac{7}{2}k, 6 k\}\).

MFCS Conference 2007 Conference Paper

Online and Offline Access to Short Lists

• Torben Hagerup

Abstract We consider the list-update problem introduced by Sleator and Tarjan, specializing it to the case of accesses only and focusing on short lists. We describe a new optimal offline algorithm, faster than the best previous algorithm when the number of accesses is sufficiently large relative to the number ℓ of items. We also give a simple optimal offline algorithm for ℓ= 3. Taking c ℓ to denote the best competitive ratio of a randomized online algorithm for the list-access problem with ℓ items, we demonstrate that c 3 = 6/5 and give new upper and lower bounds on c 4. Finally we prove a strengthened lower bound for general ℓ.

SODA Conference 1999 Conference Paper

Fast Deterministic Construction of Static Dictionaries

• Torben Hagerup

TCS Journal 1998 Journal Article

More general parallel tree contraction: Register allocation and broadcasting in a tree

• Krzysztof Diks
• Torben Hagerup

We extend the classic parallel tree-contraction technique of Miller and Reif to handle the evaluation of a class of expression trees that does not fit their original framework. We discuss applications to the following problems: (1) Register allocation, i. e. , computing the number of registers needed to evaluate a given expression if all intermediate results are kept in registers; and (2) broadcasting in a tree, i. e. , computing the number of steps needed to transmit a message from the root to all other nodes in a given rooted tree if each node is a processor that can communicate with a single neighbor in each step. We show that on inputs of size n, both problems can be solved with optimal speedup in O((log n)2) time on an EREW PRAM, in O(log n log log n) time on a CREW PRAM, and in O(log n) time on a CRCW PRAM.

MFCS Conference 1998 Conference Paper

Tree Decompositions of Small Diameter

• Hans L. Bodlaender
• Torben Hagerup

Abstract Motivated by applications in parallel and dynamic graph algorithms, we investigate the tradeoff between width and diameter of tree decompositions. For all integers n, k and K with 1 ≤ k ≤ K ≤ n − 1, denote by D(n, k, K) the maximum, over all n -vertex graphs G of treewidth k, of the smallest diameter of a tree decomposition of G of width K. We determine D(n, k, K), up to a constant factor, for all values of n, k and K. When K is bounded by a constant (the case of greatest practical relevance), D(n, k, K) is θ(n) for K ≤ 2 k -1, θ(√n) for 2 k ≤ K ≤ 3 k −2, and θ(log n ) for K ≥ 3 k −1. We provide much more accurate bounds for the case K ≤ 2 k −1.

SODA Conference 1995 Conference Paper

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

• Torben Hagerup
• Jyrki Katajainen
• Naomi Nishimura
• Prabhakar Ragde

STOC Conference 1995 Conference Paper

Sorting in linear time?

• Arne Andersson
• Torben Hagerup
• Stefan Nilsson
• Rajeev Raman

STOC Conference 1994 Conference Paper

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

• Torben Hagerup

STOC Conference 1994 Conference Paper

The complexity of searching a sorted array of strings

• Arne Andersson
• Torben Hagerup
• Johan Håstad
• Ola Petersson

MFCS Conference 1993 Conference Paper

Approximate and Exact Deterministic Parallel Selection

• Shiva Chaudhuri
• Torben Hagerup
• Rajeev Raman

Abstract The selection problem of size n is, given a set of n elements drawn from an ordered universe and an integer r with 1< r ≤ n, to identify the r th smallest element in the set. We study approximate and exact selection on deterministic concurrent-read concurrent-write parallel RAMs, where approximate selection with relative accuracy λ>0 asks for any element whose true rank differs from r by at most An. Our main results are: (1) For all t ≥(log log n ) 4, approximate selection problems of size n can be solved in O(t) time with optimal speedup with relative accuracy \(2^{{{ - t} \mathord{\left/{\vphantom {{ - t} {\left( {\log \log n} \right)}}} \right. \kern-\nulldelimiterspace} {\left( {\log \log n} \right)}}^4 }\); no deterministic PRAM algorithm for approximate selection with a running time below Ο (log n /log log n ) was previously known. (2) Exact selection problems of size n can be solved in O (log n /log log n ) time with O(n log log n /log n ) processors. This running time is the best possible (using only a polynomial number of processors), and the number of processors is optimal for the given running time (optimal speedup); the best previous algorithm achieves optimal speedup with a running time of O (log n log * n /log log n ).

SODA Conference 1993 Conference Paper

Fast Deterministic Processor Allocation

• Torben Hagerup

MFCS Conference 1992 Conference Paper

A Perfect Parallel Dictionary

• Hannah Bast
• Martin Dietzfelbinger
• Torben Hagerup

Abstract We describe new randomized parallel algorithms for the problems of interval allocation, construction of static dictionaries, and maintenance of dynamic dictionaries. All of our algorithms run optimally in constant time with high probability. Our main result is the construction of what we call a perfect dictionary, a scheme that allows p processors implementing a set M in space proportional to ¦M¦ to process batches of p insert, delete, and lookup instructions on M in constant time pet batch. Our best results are obtained for a new variant of the CRCW PRAM model of computation called the OR PRAM. For other variants of the CRCW PRAM we show slightly weaker results, with some resource bounds increased by a factor of ⊖(log k n ), where k ∈ ℕ is fixed but arbitrarily large.

SODA Conference 1992 Conference Paper

Improved Parallel Integer Sorting Without Concurrent Writing

• Susanne Albers
• Torben Hagerup

MFCS Conference 1992 Conference Paper

Merging and Sorting Strings in Parallel

• Torben Hagerup
• Ola Petersson

Abstract We show that strings of characters, equipped with the usual lexicographical ordering, can be merged and sorted in parallel as efficiently as integers, although with some loss in speed. Specifically, our main results are: Two sorted lists of strings, containing altogether n characters, can be merged with an optimal time-processor product of O(n) in O (log n ) time on a CRCW PRAM, and in O ((log n ) 2 ) time on an EREW PRAM. Suppose that n integers of size polynomial in n can be sorted in time O(t(n) ) with a time-processor product of O(nf(n)) on a CRCW PRAM, a CREW PRAM or an EREW PRAM, for nondecreasing functions t, f: ℕ → ℕ. Then a list of strings, containing altogether n characters drawn from an alphabet of size polynomial in n, can be sorted in time O(t(n) log n) with a time-processor product of O(n f(n) + n log log n ) on a PRAM of the same type. In particular, such a list can be sorted in O((log n) 2 /log log n ) time with a time-processor product of O ( n log log n ) on a CRCW PRAM.

FOCS Conference 1992 Conference Paper

Waste Makes Haste: Tight Bounds for Loose Parallel Sorting

• Torben Hagerup
• Rajeev Raman

Conventional parallel sorting requires the n input keys to be output in an array of size n, and is known to take Omega (log n/log log n) time using any polynomial number of processors. The lower bound does not apply to the more 'wasteful' convention of padded sorting, which requires the keys to be output in sorted order in an array of size (1+o(1))n. The authors give very fast randomised CRCW PRAM algorithms for several padded-sorting problems. Applying only pairwise comparisons to the input and using kn processors, where 2 >

STOC Conference 1991 Conference Paper

Constant-Time Parallel Integer Sorting (Extended Abstract)

• Torben Hagerup

FOCS Conference 1990 Conference Paper

Drawing Graphs in the Plane with High Resolution

• Michael Formann
• Torben Hagerup
• James Haralambides
• Michael Kaufmann 0001
• Frank Thomson Leighton
• Antonios Symvonis
• Emo Welzl
• Gerhard J. Woeginger

The problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized is studied. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph is defined to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that Omega (1/d/sup 2/) >

FOCS Conference 1989 Conference Paper

A Randomized Maximum-Flow Algorithm

• Joseph Cheriyan
• Torben Hagerup

The authors present a randomized maximum-flow algorithm, called the PLED (prudent linking excess diminishing) algorithm, whose expected running time is O(nm+n/sup 2/(log n)/sup 3/); this is O(nm) for all except relatively sparse networks. The algorithm is always correct, and in the worst case, which occurs with negligible probability, it take O(nm log n) time. The approach taken is to maintain a parameter Delta, which is a measure of the maximum flow excess of a vertex and of the maximum amount of flow sent by a single operation. Initially, Delta is less than or equal to the maximum edge capacity, and Delta =0 at termination. The execution of the PLED algorithm is partitioned into phases so that Delta stays fixed during each phase and decreases between consecutive phases. In order to achieve a bound on the number of phases that is independent of the maximum edge capacity, the algorithm decreases Delta by as large a factor (>or=2) as possible, rather than by a constant factor. The algorithm uses the dynamic trees data structure. >

MFCS Conference 1989 Conference Paper

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

• Krzysztof Diks
• Torben Hagerup
• Wojciech Rytter

Abstract We show how to test outerplanarity in time T( n )=O(log n log n ) using n /T( n ) processors of CREW PRAM. It is the first optimal parallel algorithm recognizing a nontrivial class of graphs and it is the main result of the paper. If the graph is outerplanar and biconnected then a Hamiltonian cycle is produced. Using this cycle and optimal parsing algorithm for bracket expressions the construction of the tree of faces as well as vertex colourings (with the smallest number of colours) are also done by optimal parallel algorithms.

MFCS Conference 1988 Conference Paper

Efficient Simulations Between Concurrent-Read Concurrent-Write PRAM Models

• Bogdan S. Chlebus
• Krzysztof Diks
• Torben Hagerup
• Tomasz Radzik

Abstract We give several simple and efficient algorithms for simulations of stronger CRCW PRAMs on weaker ones. The models that we consider are the well-known PRIORITY, ARBITRARY and COMMON PRAMs, and COLLISION and COLLISION +, defined by the property that a special collision symbol is stored in each memory cell into which more than one processor attempts to write, or more than one value is attempted to be written, respectively, in a given step. Our results are the following, where n denotes the number of processors of the simulated PRAM: 1) A O (1)-time simulation between any pair of models, provided that the simulating machine has O( n log n ) processors; 2) Two n -processor simulations: of PRIORITY on ARBITRARY with O(loglog n ) slowdown, and of PRIORITY on COLLISION + with O((loglog n ) 2 ) slowdown.

MFCS Conference 1986 Conference Paper

Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones

• Helmut Alt
• Torben Hagerup
• Kurt Mehlhorn
• Franco P. Preparata

Abstract We describe a deterministic simulation of PRAMs on module parallel computers (MPCs) and on processor networks of bounded degree. The simulating machines have the same number n of processors as the simulated PRAM, and if the size of the PRAM's shared memory is polynomial in n, each PRAM step is simulated by O (log n ) MPC steps or by O ((log n ) 2 ) steps of the bounded degree network. This improves upon a previous result by Upfal and Wigderson. We also prove an Ω((log n ) 2 /log log n ) lower bound on the number of steps needed to simulate one PRAM step on a bounded degree network under the assumption that the communication in the network is point-to-point.