16 Search Results for "Sedgewick, Robert"


Document
Track A: Algorithms, Complexity and Games
Analysis of Smooth Heaps and Slim Heaps

Authors: Maria Hartmann, László Kozma, Corwin Sinnamon, and Robert E. Tarjan

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)


Abstract
The smooth heap is a recently introduced self-adjusting heap [Kozma, Saranurak, 2018] similar to the pairing heap [Fredman, Sedgewick, Sleator, Tarjan, 1986]. The smooth heap was obtained as a heap-counterpart of Greedy BST, a binary search tree updating strategy conjectured to be instance-optimal [Lucas, 1988], [Munro, 2000]. Several adaptive properties of smooth heaps follow from this connection; moreover, the smooth heap itself has been conjectured to be instance-optimal within a certain class of heaps. Nevertheless, no general analysis of smooth heaps has existed until now, the only previous analysis showing that, when used in sorting mode (n insertions followed by n delete-min operations), smooth heaps sort n numbers in O(nlg n) time. In this paper we describe a simpler variant of the smooth heap we call the slim heap. We give a new, self-contained analysis of smooth heaps and slim heaps in unrestricted operation, obtaining amortized bounds that match the best bounds known for self-adjusting heaps. Previous experimental work has found the pairing heap to dominate other data structures in this class in various settings. Our tests show that smooth heaps and slim heaps are competitive with pairing heaps, outperforming them in some cases, while being comparably easy to implement.

Cite as

Maria Hartmann, László Kozma, Corwin Sinnamon, and Robert E. Tarjan. Analysis of Smooth Heaps and Slim Heaps. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 79:1-79:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{hartmann_et_al:LIPIcs.ICALP.2021.79,
  author =	{Hartmann, Maria and Kozma, L\'{a}szl\'{o} and Sinnamon, Corwin and Tarjan, Robert E.},
  title =	{{Analysis of Smooth Heaps and Slim Heaps}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{79:1--79:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.79},
  URN =		{urn:nbn:de:0030-drops-141482},
  doi =		{10.4230/LIPIcs.ICALP.2021.79},
  annote =	{Keywords: data structure, heap, priority queue, amortized analysis, self-adjusting}
}
Document
Data Structures for the Cloud and External Memory Data (Dagstuhl Seminar 19051)

Authors: Gerth Stølting Brodal, Ulrich Carsten Meyer, Bernhard E. Nebel, and Robert Sedgewick

Published in: Dagstuhl Reports, Volume 9, Issue 1 (2019)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16101 "Data Structures for the Cloud and External Memory Data". In today's computing environment vast amounts of data are processed, exchanged and analyzed. The manner in which information is stored profoundly influences the efficiency of these operations over the data. In spite of the maturity of the field many data structuring problems are still open, while new ones arise due to technological advances. The seminar covered both recent advances in the "classical" data structuring topics as well as new models of computation adapted to modern architectures, scientific studies that reveal the need for such models, applications where large data sets play a central role, modern computing platforms for very large data, and new data structures for large data in modern architectures. The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.

Cite as

Gerth Stølting Brodal, Ulrich Carsten Meyer, Bernhard E. Nebel, and Robert Sedgewick. Data Structures for the Cloud and External Memory Data (Dagstuhl Seminar 19051). In Dagstuhl Reports, Volume 9, Issue 1, pp. 104-124, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@Article{brodal_et_al:DagRep.9.1.104,
  author =	{Brodal, Gerth St{\o}lting and Meyer, Ulrich Carsten and Nebel, Bernhard E. and Sedgewick, Robert},
  title =	{{Data Structures for the Cloud and External Memory Data (Dagstuhl Seminar 19051)}},
  pages =	{104--124},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{1},
  editor =	{Brodal, Gerth St{\o}lting and Meyer, Ulrich Carsten and Nebel, Bernhard E. and Sedgewick, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.1.104},
  URN =		{urn:nbn:de:0030-drops-105722},
  doi =		{10.4230/DagRep.9.1.104},
  annote =	{Keywords: algorithms, big data, cloud computing, data structures, external memory methods, large data sets, web-scale}
}
Document
Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 16101)

Authors: Alejandro Lopez-Ortiz, Ulrich Carsten Meyer, Markus E. Nebel, and Robert Sedgewick

Published in: Dagstuhl Reports, Volume 6, Issue 3 (2016)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16101 "Data Structures and Advanced Models of Computation on Big Data". In today's computing environment vast amounts of data are processed, exchanged and analyzed. The manner in which information is stored profoundly influences the efficiency of these operations over the data. In spite of the maturity of the field many data structuring problems are still open, while new ones arise due to technological advances. The seminar covered both recent advances in the "classical" data structuring topics as well as new models of computation adapted to modern architectures, scientific studies that reveal the need for such models, applications where large data sets play a central role, modern computing platforms for very large data, and new data structures for large data in modern architectures. The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.

Cite as

Alejandro Lopez-Ortiz, Ulrich Carsten Meyer, Markus E. Nebel, and Robert Sedgewick. Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 16101). In Dagstuhl Reports, Volume 6, Issue 3, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@Article{lopezortiz_et_al:DagRep.6.3.1,
  author =	{Lopez-Ortiz, Alejandro and Meyer, Ulrich Carsten and Nebel, Markus E. and Sedgewick, Robert},
  title =	{{Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 16101)}},
  pages =	{1--23},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{3},
  editor =	{Lopez-Ortiz, Alejandro and Meyer, Ulrich Carsten and Nebel, Markus E. and Sedgewick, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.3.1},
  URN =		{urn:nbn:de:0030-drops-61457},
  doi =		{10.4230/DagRep.6.3.1},
  annote =	{Keywords: algorithms, big data, cloud services, data structures, external memory methods, information theory, large data sets, streaming, web-scale}
}
Document
Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 14091)

Authors: Alejandro López-Ortiz, Ulrich Carsten Meyer, and Robert Sedgewick

Published in: Dagstuhl Reports, Volume 4, Issue 2 (2014)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14091 "Data Structures and Advanced Models of Computation on Big Data". In today's computing environment vast amounts of data are processed, exchanged and analyzed. The manner in which information is stored profoundly influences the efficiency of these operations over the data. In spite of the maturity of the field many data structuring problems are still open, while new ones arise due to technological advances. The seminar covered both recent advances in the "classical" data structuring topics as well as new models of computation adapted to modern architectures, scientific studies that reveal the need for such models, applications where large data sets play a central role, modern computing platforms for very large data, and new data structures for large data in modern architectures. The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.

Cite as

Alejandro López-Ortiz, Ulrich Carsten Meyer, and Robert Sedgewick. Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 14091). In Dagstuhl Reports, Volume 4, Issue 2, pp. 129-149, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@Article{lopezortiz_et_al:DagRep.4.2.129,
  author =	{L\'{o}pez-Ortiz, Alejandro and Meyer, Ulrich Carsten and Sedgewick, Robert},
  title =	{{Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 14091)}},
  pages =	{129--149},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{2},
  editor =	{L\'{o}pez-Ortiz, Alejandro and Meyer, Ulrich Carsten and Sedgewick, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.2.129},
  URN =		{urn:nbn:de:0030-drops-45489},
  doi =		{10.4230/DagRep.4.2.129},
  annote =	{Keywords: data structures, big data, models of computation, I/O Model, sorting, quicksort, graph algorithms, hashing, compression, succinct data structures, trajectories, text search, GPU algorithms, MapReduce}
}
Document
08081 Abstracts Collection – Data Structures

Authors: Lars Arge, Robert Sedgewick, and Raimund Seidel

Published in: Dagstuhl Seminar Proceedings, Volume 8081, Data Structures (2008)


Abstract
From February 17th to 22nd 2008, the Dagstuhl Seminar 08081 ``Data Structures'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. It brought together 49 researchers from four continents to discuss recent developments concerning data structures in terms of research but also in terms of new technologies that impact how data can be stored, updated, and retrieved. During the seminar a fair number of participants presented their current research. There was discussion of ongoing work, and in addition an open problem session was held. This paper first describes the seminar topics and goals in general, then gives the minutes of the open problem session, and concludes with abstracts of the presentations given during the seminar. Where appropriate and available, links to extended abstracts or full papers are provided.

Cite as

Lars Arge, Robert Sedgewick, and Raimund Seidel. 08081 Abstracts Collection – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 8081, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.08081.1,
  author =	{Arge, Lars and Sedgewick, Robert and Seidel, Raimund},
  title =	{{08081 Abstracts Collection – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8081},
  editor =	{Lars Arge and Robert Sedgewick and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08081.1},
  URN =		{urn:nbn:de:0030-drops-15325},
  doi =		{10.4230/DagSemProc.08081.1},
  annote =	{Keywords: Data structures, information retrieval, complexity, algorithms, flash memory}
}
Document
Kinetic kd-Trees and Longest-Side kd-Trees

Authors: Mohammad Abam, Mark de Berg, and Bettina Speckmann

Published in: Dagstuhl Seminar Proceedings, Volume 8081, Data Structures (2008)


Abstract
We propose a simple variant of kd-trees, called rank-based kd-trees, for sets of points in~$Reals^d$. We show that a rank-based kd-tree, like an ordinary kd-tree, supports range search que-ries in~$O(n^{1-1/d}+k)$ time, where~$k$ is the output size. The main advantage of rank-based kd-trees is that they can be efficiently kinetized: the KDS processes~$O(n^2)$ events in the worst case, assuming that the points follow constant-degree algebraic trajectories, each event can be handled in~$O(log n)$ time, and each point is involved in~$O(1)$ certificates. We also propose a variant of longest-side kd-trees, called rank-based longest-side kd-trees (RBLS kd-trees, for short), for sets of points in~$Reals^2$. RBLS kd-trees can be kinetized efficiently as well and like longest-side kd-trees, RBLS kd-trees support nearest-neighbor, farthest-neighbor, and approximate range search queries in~$O((1/epsilon)log^2 n)$ time. The KDS processes~$O(n^3log n)$ events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in~$O(log^2 n)$ time, and each point is involved in~$O(log n)$ certificates.

Cite as

Mohammad Abam, Mark de Berg, and Bettina Speckmann. Kinetic kd-Trees and Longest-Side kd-Trees. In Data Structures. Dagstuhl Seminar Proceedings, Volume 8081, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{abam_et_al:DagSemProc.08081.2,
  author =	{Abam, Mohammad and de Berg, Mark and Speckmann, Bettina},
  title =	{{Kinetic kd-Trees and Longest-Side kd-Trees}},
  booktitle =	{Data Structures},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8081},
  editor =	{Lars Arge and Robert Sedgewick and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08081.2},
  URN =		{urn:nbn:de:0030-drops-15307},
  doi =		{10.4230/DagSemProc.08081.2},
  annote =	{Keywords: Kinetic data structures, kd-tree, longest-side kd-tree}
}
Document
Optimal Speedup on a Low-Degree Multi-Core Parallel Architecture (LoPRAM)

Authors: Alejandro Lopez-Ortiz, Reza Dorrigiv, and Alejandro Salinger

Published in: Dagstuhl Seminar Proceedings, Volume 8081, Data Structures (2008)


Abstract
We propose a new model with small degreee of parallelism that reflects current and future multicore architectures in practice. The model is based on the PRAM architecture and hence it inherits many of its interesting theoretical properties. The key observations and differences are that the degree of parallelism (i.e. number of processors or cores) is bounded by O(log n), the synchronization model is looser and the use of parallelism is at a higher level unless explicitly specified otherwise. Surprisingly, these three rather minor variants result in a model in which obtaining work optimal algorithms is significantly easier than for the PRAM. The new model is called Low-degree PRAM or LoPRAM for short. Lastly we observe that there are thresholds in complexity of programming at p=O(log n) and p=O(sqrt(n)) and provide references for specific problems for which this threshold has been formally proven.

Cite as

Alejandro Lopez-Ortiz, Reza Dorrigiv, and Alejandro Salinger. Optimal Speedup on a Low-Degree Multi-Core Parallel Architecture (LoPRAM). In Data Structures. Dagstuhl Seminar Proceedings, Volume 8081, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{lopezortiz_et_al:DagSemProc.08081.3,
  author =	{Lopez-Ortiz, Alejandro and Dorrigiv, Reza and Salinger, Alejandro},
  title =	{{Optimal Speedup on a Low-Degree Multi-Core Parallel Architecture (LoPRAM)}},
  booktitle =	{Data Structures},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8081},
  editor =	{Lars Arge and Robert Sedgewick and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08081.3},
  URN =		{urn:nbn:de:0030-drops-15315},
  doi =		{10.4230/DagSemProc.08081.3},
  annote =	{Keywords: PRAM, multicore architectures, parallelism, algorithms, dynamic programming, divide and conquer}
}
Document
Sources of Superlinearity in Davenport-Schinzel Sequences

Authors: Seth Pettie

Published in: Dagstuhl Seminar Proceedings, Volume 8081, Data Structures (2008)


Abstract
A {em generalized} Davenport-Schinzel sequence is one over a finite alphabet that contains no subsequences isomorphic to a fixed {em forbidden subsequence}. One of the fundamental problems in this area is bounding (asymptotically) the maximum length of such sequences. Following Klazar, let $Ex(sigma,n)$ be the maximum length of a sequence over an alphabet of size $n$ avoiding subsequences isomorphic to $sigma$. It has been proved that for every $sigma$, $Ex(sigma,n)$ is either linear or very close to linear; in particular it is $O(n2^{alpha(n)^{O(1)}})$, where $alpha$ is the inverse-Ackermann function and $O(1)$ depends on $sigma$. However, very little is known about the properties of $sigma$ that induce superlinearity of $Ex(sigma,n)$. In this paper we exhibit an infinite family of independent superlinear forbidden subsequences. To be specific, we show that there are 17 {em prototypical} superlinear forbidden subsequences, some of which can be made arbitrarily long through a simple padding operation. Perhaps the most novel part of our constructions is a new succinct code for representing superlinear forbidden subsequences.

Cite as

Seth Pettie. Sources of Superlinearity in Davenport-Schinzel Sequences. In Data Structures. Dagstuhl Seminar Proceedings, Volume 8081, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{pettie:DagSemProc.08081.4,
  author =	{Pettie, Seth},
  title =	{{Sources of Superlinearity in Davenport-Schinzel Sequences}},
  booktitle =	{Data Structures},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8081},
  editor =	{Lars Arge and Robert Sedgewick and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08081.4},
  URN =		{urn:nbn:de:0030-drops-15291},
  doi =		{10.4230/DagSemProc.08081.4},
  annote =	{Keywords: Davenport-Schinzel Sequences, lower envelopes, splay trees}
}
Document
06091 Abstracts Collection – Data Structures

Authors: Lars Arge, Robert Sedgewick, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)


Abstract
From 26.02.06 to 03.03.06, the Dagstuhl Seminar 06091 ``Data Structures'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Lars Arge, Robert Sedgewick, and Dorothea Wagner. 06091 Abstracts Collection – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.06091.1,
  author =	{Arge, Lars and Sedgewick, Robert and Wagner, Dorothea},
  title =	{{06091 Abstracts Collection – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.1},
  URN =		{urn:nbn:de:0030-drops-8428},
  doi =		{10.4230/DagSemProc.06091.1},
  annote =	{Keywords: Algorithms, data structures}
}
Document
06091 Executive Summary – Data Structures

Authors: Lars Arge, Robert Sedgewick, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)


Abstract
The Dagstuhl Seminar on Data Structures in 2006 reported on ongoing research on data structures, including randomized, cache-oblivious and succinct data structures. There was some shift of interest away from purely theoretical issues towards scientific studies that are directly relevant to practical applications. The participants were asked to think about the direction that research on data structure should take. Several presentations were provocative responses to this question. Interest in the topic remains high: another attendance record was set.

Cite as

Lars Arge, Robert Sedgewick, and Dorothea Wagner. 06091 Executive Summary – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.06091.2,
  author =	{Arge, Lars and Sedgewick, Robert and Wagner, Dorothea},
  title =	{{06091 Executive Summary – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.2},
  URN =		{urn:nbn:de:0030-drops-8411},
  doi =		{10.4230/DagSemProc.06091.2},
  annote =	{Keywords: algorithms, data structures}
}
Document
Die Another Day

Authors: Rudolf Fleischer

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)


Abstract
The hydra was a many-headed monster from Greek mythology that could grow one or two new heads when one of its heads got cut off. It was the second task of Hercules to kill this monster. In an abstract sense a hydra can be modeled by a tree where the leaves are the heads, and when a head is cut off some subtrees get duplicated. Different hydra species differ by the location of subtrees to be duplicated and by the number of new subtrees grown in each step. Using some deep mathematics, it had been shown that two classes of rather restricted hydra species must always die, independent of the order in which heads are cut off. In this paper we provide an elementary proof which actually gives a complete classification of all hydra species as immortal or doomed. Now, if Hercules had known this...

Cite as

Rudolf Fleischer. Die Another Day. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{fleischer:DagSemProc.06091.3,
  author =	{Fleischer, Rudolf},
  title =	{{Die Another Day}},
  booktitle =	{Data Structures},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.3},
  URN =		{urn:nbn:de:0030-drops-7652},
  doi =		{10.4230/DagSemProc.06091.3},
  annote =	{Keywords: Hydra, Koenig's Lemma, Peano Arithmetic}
}
Document
In-Place Randomized Slope-Selection

Authors: Henrik Blunck and Jan Vahrenhold

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)


Abstract
Slope selection is a well-known algorithmic tool used in the context of computing robust estimators for fitting a line to a collection $mathcal{P}$ of $n$ points in the plane. We demonstrate that it is possible to perform slope selection in expected $mathcal{O}(n log n)$ time using only constant extra space in addition to the space needed for representing the input. Our solution is based upon a space-efficient variant of Matouv{s}ek's randomized interpolation search, and we believe that the techniques developed in this paper will prove helpful in the design of space-efficient randomized algorithms using samples. To underline this, we also sketch how to compute the repeated median line estimator in an in-place setting.

Cite as

Henrik Blunck and Jan Vahrenhold. In-Place Randomized Slope-Selection. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{blunck_et_al:DagSemProc.06091.4,
  author =	{Blunck, Henrik and Vahrenhold, Jan},
  title =	{{In-Place Randomized Slope-Selection}},
  booktitle =	{Data Structures},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.4},
  URN =		{urn:nbn:de:0030-drops-8390},
  doi =		{10.4230/DagSemProc.06091.4},
  annote =	{Keywords: In-Place Algorithms, Slope Selection}
}
Document
Towards a Final Analysis of Pairing Heaps

Authors: Seth Pettie

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)


Abstract
Fredman, Sedgewick, Sleator, and Tarjan proposed the {em pairing heap} as a self-adjusting, streamlined version of the Fibonacci heap. It provably supports all priority queue operations in logarithmic time and is known to be extremely efficient in practice. However, despite its simplicity and empirical superiority, the pairing heap is one of the few popular data structures whose basic complexity remains open. In this paper we prove that pairing heaps support the deletemin operation in optimal logarithmic time and all other operations (insert, meld, and decreasekey) in time $O(2^{2sqrt{loglog n}})$. This result gives the {em first} sub-logarithmic time bound for decreasekey and comes close to the lower bound of $Omega(loglog n)$ established by Fredman. Pairing heaps have a well known but poorly understood relationship to splay trees and, to date, the transfer of ideas has flowed in one direction: from splaying to pairing. One contribution of this paper is a new analysis that reasons explicitly with information-theoretic measures. Whether these ideas could contribute to the analysis of splay trees is an open question.

Cite as

Seth Pettie. Towards a Final Analysis of Pairing Heaps. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{pettie:DagSemProc.06091.5,
  author =	{Pettie, Seth},
  title =	{{Towards a Final Analysis of Pairing Heaps}},
  booktitle =	{Data Structures},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.5},
  URN =		{urn:nbn:de:0030-drops-7642},
  doi =		{10.4230/DagSemProc.06091.5},
  annote =	{Keywords: Data structure, heap, self-adjusting, amortized analysis}
}
Document
04091 Abstracts Collection – Data Structures

Authors: Susanne Albers, Robert Sedgewick, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 4091, Data Structures (2005)


Abstract
From 22.02. to 27.02.2004, Dagstuhl Seminar "Data Structures" was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar are put together in this paper. The first section describes the seminar topics and goals in general.

Cite as

Susanne Albers, Robert Sedgewick, and Dorothea Wagner. 04091 Abstracts Collection – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 4091, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{albers_et_al:DagSemProc.04091.1,
  author =	{Albers, Susanne and Sedgewick, Robert and Wagner, Dorothea},
  title =	{{04091 Abstracts Collection – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4091},
  editor =	{Susanne Albers and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04091.1},
  URN =		{urn:nbn:de:0030-drops-1758},
  doi =		{10.4230/DagSemProc.04091.1},
  annote =	{Keywords: Cache oblivious algorithms , cell probe model , computational geometry , data compression , dictionaries , finger search , hashing , heaps I/O efficiency , lower bounds}
}
Document
Data Structures (Dagstuhl Seminar 02091)

Authors: Susanne Albers, Robert Sedgewick, and Peter Widmayer

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Susanne Albers, Robert Sedgewick, and Peter Widmayer. Data Structures (Dagstuhl Seminar 02091). Dagstuhl Seminar Report 335, pp. 1-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)


Copy BibTex To Clipboard

@TechReport{albers_et_al:DagSemRep.335,
  author =	{Albers, Susanne and Sedgewick, Robert and Widmayer, Peter},
  title =	{{Data Structures (Dagstuhl Seminar 02091)}},
  pages =	{1--36},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{335},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.335},
  URN =		{urn:nbn:de:0030-drops-152176},
  doi =		{10.4230/DagSemRep.335},
}
  • Refine by Author
  • 9 Sedgewick, Robert
  • 3 Arge, Lars
  • 3 Meyer, Ulrich Carsten
  • 3 Wagner, Dorothea
  • 2 Albers, Susanne
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 5 algorithms
  • 5 data structures
  • 3 big data
  • 2 amortized analysis
  • 2 external memory methods
  • Show More...

  • Refine by Type
  • 16 document

  • Refine by Publication Year
  • 5 2006
  • 4 2008
  • 1 1996
  • 1 2002
  • 1 2005
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail