2. Number - only D1

MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1 - MPI-INF/SWS Research Reports 1991-2021

Number	Title	Name(s)	Pages
2013-1-001	New results for non-preemptive speed scaling	Ott	32
2010-1-001	Maximum cardinality popular matchings in strict two-sided preference lists	Huang, Kavitha	17
2008-1-001	Characterizing the performance of Flash memory storage devices and its impact on algorithm design	Ajwani, Malinger, Meyer, Toledo	36
2007-1-003	LFthreads: a lock-free thread library	Gidenstam, Papatriantafilou	36
2007-1-002	A Lagrangian relaxation approach for the multiple sequence alignment problem	Althaus, Canzar	41
2007-1-001	A New Approximation Algorithm for thr Maximum Traveling Salesman Problem	Paluch	?
2007-1-001	Linear-time reordering in a sweep-line algorithm for algebraic curves intersecting in a common point	Berberich, Kettner	20
2006-1-007	Output-sensitive autocompletion search	Bast, Weber, Mortensen	17
2006-1-006	Division-free computation of subresultants using bezout matrices	Kerber	20
2006-1-005	Snap rounding of Bézier curves	Eigenwillig, Kettner, Wolpert	39
2006-1-004	Power assignment problems in wireless communication	Funke, Laue, Naujoks, Zvi	25
2005-1-008	Cycle bases of graphs and sampled manifolds	Gotsman, Kaligosi, Mehlhorn, Michail, Pyrga	30
2005-1-007	A faster algorithm for computing a longest common increasing subsequence	Katriel, Kutz	13
2005-1-003	Improved algorithms for all-pairs approximate shortest paths in weighted graphs	Baswana, Telikepalli	26
2005-1-002	Reachability substitutes for planar digraphs	Katriel, Kutz, Skutella	24
2005-1-001	Rank-maximal through maximum weight matchings	Michail	22
2004-1-006	On the Hadwiger's conjecture for graph products	Chandran, Sivadasan	12
2004-1-005	A comparison of polynomial evaluation schemes	Schmitt, Fousse	19
2004-1-004	Online scheduling with bounded migration	Sivadasan, Sanders, Skutella	21
2004-1-003	On algorithms for online topological ordering and sorting	Katriel	15
2004-1-002	A simpler linear time 2/3 - epsilon approximation for maximum weight matching	Sanders, Pettie	10
2004-1-001	Filtering algorithms for the Same and UsedBy constraints	Beldiceanu, Katriel, Thiel	36
2003-1-018	A note on the smoothed complexity of the single-source shortest path problem	Schaefer	8
2003-1-017	Cross-monotonic cost sharing methods for connected facility location games	Schäfer, Leonardi	10
2003-1-016	Topology matters: smoothed competitive analysis of metrical task systems	Schäfer, Sivadasan	28
2003-1-015	Sum-Multicoloring on paths	Kovács	20
2003-1-014	Average case and smoothed competitive analysis of the multi-level feedback algorithm	Schäfer, Becchetti, Leonardi, Marchetti-Spaccamela, Vredeveld	31
2003-1-013	Fast bound consistency for the global cardinality constraint	Katriel, Thiel	30
2003-1-011	Selfish traffic allocation for server farms	Krysta, Czumaj, Voecking	43
2003-1-010	A linear time heuristic for the branch-decomposition of planar graphs	Tamaki	18
2003-1-009	On the Bollob\'as -- Eldridge conjecture for bipartite graphs	Csaba	29
2003-1-008	Polynomial time algorithms for network information flow	Sanders	15
2003-1-007	Alternating cycles contribution: a strategy of tour-merging for the traveling salesman problem	Tamaki	22
2003-1-006	On the probability of rendezvous in graphs	Dietzfelbinger, Tamaki	30
2003-1-005	Almost random graphs with simple hash functions	Dietzfelbinger, Woelfel	23
2003-1-004	Improving linear programming approaches for the Steiner tree problem	Althaus, Polzin, Daneshmand	19
2003-1-003	Random knapsack in expected polynomial time	Beier, Vöcking	22
2003-1-002	Scheduling and traffic allocation for tasks with bounded splittability	Krysta, Sanders, Vöcking	15
2003-1-001	Asynchronous parallel disk sorting	Sanders, Dementiev	22
2002-1-005	Performance of heuristic and approximation algorithms for the uncapacitated facility location problem	Hoefer	27
2002-1-001	Using (sub)graphs of small width for solving the Steiner problem	Polzin, Vahdati	9
2001-1-007	Extending reduction techniques for the Steiner tree problem: a combination of alternative-and bound-based approaches	Polzin, Vahdati	24
2001-1-006	Partitioning techniques for the Steiner problem	Polzin, Vahdati	21
2001-1-005	On Steiner trees and minimum spanning trees in hypergraphs	Polzin, Vahdati	15
2001-1-004	An adaptable and extensible geometry kernel	Hert, Hoffmann, Kettner, Pion, Seel	27
2001-1-003	Implementation of planar Nef polyhedra	Seel	345
2001-1-002	Directed single-source shortest-paths in linear average-case time	Meyer	32
2001-1-001	Approximating minimum size 1,2-connected networks	Krysta	22
2000-1-005	Infimaximal frames: a technique for making lines look like segments	Seel, Mehlhorn	16
2000-1-004	Generalized and improved constructive separation bound for real algebraic expressions	Mehlhorn, Schirra	12
2000-1-003	Low-contention depth-first scheduling of parallel computations with synchronization variables	Fatourou	56
2000-1-002	A powerful heuristic for telephone gossiping	Beier, Sibeyn	23
2000-1-001	A branch and cut algorithm for the optimal solution of the side-chain placement problem	Althaus, Kohlbacher, Lenhof, Müller	26
1999-1-007	A simple way to recognize a correct Voronoi diagram of line segments	Burnikel, Mehlhorn, Seel	11
1999-1-006	Integration of graph iterators into LEDA	Nissen	39
1999-1-005	Ultimate parallel list ranking?	Sibeyn	20
1999-1-004	How generic language extensions enable ''open-world'' design in Java	Nissen, Weihe	40
1999-1-003	Fast concurrent access to parallel disks	Sanders, Egner, Korst	30
1999-1-002	BALL: Biochemical Algorithms Library	Boghossian, Kohlbacher, Lenhof	20
1999-1-001	A theoretical and experimental study on the construction of suffix arrays in external memory	Crauser, Ferragina	40
98-1-031	Optimal compaction of orthogonal grid drawings	Klau, Mutzel	20
98-1-030	Applications of the generic programming paradigm in the design of CGAL	Brönniman, Kettner, Schirra, Veltkamp	12
98-1-029	Optimizing over all combinatorial embeddings of a planar graph	Mutzel, Weiskircher	23
98-1-028	On the performance of LEDA-SM	Crauser, Mehlhorn, Althaus, Brengel, Buchheit, Keller, Krone, Lambert, Schulte, Thiel, Westphal, Wirth	26
98-1-027	Delaunay graphs by divide and conquer	Burnikel	24
98-1-026	Improved approximation schemes for scheduling unrelated parallel machines	Jansen, Porkolab	14
98-1-025	Linear-time approximation schemes for scheduling malleable parallel tasks	Jansen, Porkolab	15
98-1-024	$q$-gram based database searching using a suffix array (QUASAR)	Burkhardt, Crauser, Ferragina, Lenhof, Rivals, Vingron	11
98-1-023	Rational points on circles	Burnikel	14
98-1-022	Fast recursive division	Burnikel, Ziegler	29
98-1-021	Scheduling with unexpected machine breakdowns	Albers, Schmidt	15
98-1-020	On Wallace's method for the generation of normal variates	Rüb	17
98-1-019	2nd Workshop on Algorithm Engineering WAE '98 - Proceedings	Mehlhorn (ed.)	213
98-1-018	On positive influence and negative dependence	Dubhashi, Ranjan	12
98-1-017	Randomized external-memory algorithms for some geometric problems	Crauser, Ferragina, Mehlhorn, Meyer, Ramos	27
98-1-016	New approximation algorithms for the achromatic number	Krysta, Lory\'{s}	26
98-1-015	Scheduling multicasts on unit-capacity trees and meshes	Henzinger, Leonardi	38
98-1-014	Time-independent gossiping on full-port tori	Meyer, Sibeyn	20
98-1-013	Quasi-orthogonal drawing of planar graphs	Klau, Mutzel	15
98-1-012	Solving some discrepancy problems in NC*	Mahajan, Ramos, Subrahmanyam	21
98-1-011	Robustness analysis in combinatorial optimization	Frederickson, Solis-Oba	66
98-1-010	2-Approximation algorithm for finding a spanning tree with maximum number of leaves	Solis-Oba	16
98-1-009	Fully dynamic shortest paths and negative cycle detection on diagraphs with Arbitrary Arc Weights	Frigioni, Marchetti-Spaccamela, Nanni	18
98-1-008	A note on computing a maximal planar subgraph using PQ-trees	Jünger, Leipert, Mutzel	5
98-1-007	On the Design of CGAL, the Computational Geometry Algorithms Library	Fabri, Giezeman, Kettner, Schirra, Schönherr	31
98-1-006	A new characterization for parity graphs and a coloring problem with costs	Jansen	16
98-1-005	The mutual exclusion scheduling problem for permutation and comparability graphs	Jansen	12
98-1-004	Robustness and precision issues in geometric computation	Schirra	34
98-1-003	Parameterized implementations of classical planar convex hull algorithms and extreme point compuations	Schirra	93
98-1-002	Comparator networks for binary heap construction	Brodal, Pinotti	11
98-1-001	Simpler and faster static AC$^0$ dictionaries	Hagerup	13
97-1-028	The practical use of the $\calA^*$ algorithm for exact multiple sequence alignment	Lermen, Reinert	16
97-1-027	A polylogarithmic approximation algorithm for group Steiner tree problem	Garg, Konjevod, Ravi	7
97-1-026	On-line network routing - a survey	Fiat, Leonardi	19
97-1-025	Faster and simpler algorithms for multicommodity flow and other fractional packing problems	Garg, Könemann	13
97-1-024	Minimizing stall time in single and parallel disk systems	Albers, Garg, Leonardi	16
97-1-023	Randomized on-line call control revisited	Leonardi, Marchetti-Spaccamela	19
97-1-022	Maximum network flow with floating point arithmetic	Althaus, Mehlhorn	5
97-1-021	From parallel to external list ranking	Sibeyn	15
97-1-020	Finger search trees with constant insertion time	Brodal	17
97-1-019	AGD-Library: A Library of Algorithms for Graph Drawing	Alberts, Gutwenger, Mutzel, Näher	13
97-1-018	On the Bahncard problem	Fleischer	16
97-1-017	Exploring unknown environments	Albers, Henzinger	23
97-1-016	Faster deterministic sorting and priority queues in linear space	Thorup	9
97-1-015	Pitfalls of using PQ--Trees in automatic graph drawing	Jünger, Leipert, Mutzel	12
97-1-014	Designing a Computational Geometry Algorithms Library	Schirra	8
97-1-013	Datenstrukturen und Algorithmen	Hagerup	223
97-1-012	On Batcher's Merge Sorts as Parallel Sorting Algorithms	Rüb	23
97-1-011	A parallel priority queue with constant time operations	Brodal, Träff, Zaroliagis	19
97-1-010	Evaluating a 2-approximation algorithm for edge-separators in planar graphs	Garg, Manss	9
97-1-009	Better bounds for online scheduling	Albers	16
97-1-008	An alternative method to crossing minimization on hierarchical graphs	Mutzel	15
97-1-007	Algorithmen zum automatischen Zeichnen von Graphen	Brandenburg, Jünger, Mutzel	9
97-1-006	Restricted 2-factor polytopes	Cunningham, Wang	30
97-1-005	Bicriteria job sequencing with release dates	Wang	18
97-1-004	New contact measures for the protein docking problem	Lenhof	10
97-1-003	Parallel algorithms for MD-simulations of synthetic polymers	Jung, Lenhof, Müller, Rüb	32
97-1-002	Approximating sparsest cuts	Garg	9
97-1-001	BSP-like external-memory computation	Sibeyn, Kaufmann	14
96-1-033	A runtime test of integer arithmetic and linear algebra in LEDA	Seel	10
96-1-032	Runtime prediction of real programs on real machines	Finkler, Mehlhorn	10
96-1-031	On the complexity of computing evolutionary trees	Gasieniec, Jansson, Lingas, Östlin	14
96-1-030	External inverse pattern matching	Gasieniec, Indyk, Krysta	12
96-1-029	Lower bounds for row minima searching	Bradford, Reinert	12
96-1-028	A branch-and-cut algorithm for multiple sequence alignment	Reinert, Lenhof, Mutzel, Mehlhorn, Kececioglou	15
96-1-027	A branch-and-cut approach to physical mapping with end-probes	Christof, Jünger, Kececioglou, Mutzel, Reinelt	10
96-1-026	A survey of self-organizing data structures	Albers, Westbrook	39
96-1-025	2-Layer straigthline crossing minimization: performance of exact and heuristic algorithms	Jünger, Mutzel	14
96-1-024	More geneal parallel tree contraction: Register allocation and broadcasting in a tree	Diks, Hagerup	24
96-1-023	Discovering all most specific sentences by randomized algorithms	Gunopulos, Mannila, Saluja	23
96-1-022	Optimal algorithms for some proximity problems on the Gaussian sphere with applications	Saluja, Gupta	8
96-1-021	Generalized $k$-Center Problems	Garg, Chaudhuri, Ravi	9
96-1-020	Negative dependence through the FKG Inequality	Dubhashi, Priebe, Ranjan	10
96-1-019	Rotations of periodic strings and short superstrings	Breslauer, Jiang, Jiang	13
96-1-018	Gossiping on meshes and tori	Sibeyn, Rao, Juurlink	19
96-1-017	A technique for adding range restrictions to generalized searching problems	Gupta, Janardan, Smid	9
96-1-016	A computational basis for higher-dimensional computational geometry	Mehlhorn, Näher, Schirra, Seel, Uhrig	120
96-1-015	Computational Molecular Biology	Vingron, Lenhof, Mutzel	26
96-1-014	The randomized complexity of maintaining the minimum	Brodal, Chaudhuri, Radhakrishnan	12
96-1-013	Derandomizing semidefinite programming based approximation algorithms	Mahajan, Ramesh	22
96-1-012	A simple parallel algorithm for the single-source shortest path problem on planar diagraphs	Träff, Zaroliagis	17
96-1-011	The impact of timing on linearizability in counting networks	Mavronicolas, Papatriantafilou, Tsigas	19
96-1-010	Distributed list coloring: how to dynamically allocate frequencies to mobile base stations	Garg, Papatriantafilou, Tsigas	15
96-1-009	The thickness of graphs: a survey	Mutzel, Odenthal, Scharbrodt	18
96-1-008	Efficient algorithms for counting and reporting pairwise intersections between convex polygons	Gupta, Janardan, Smid	11
96-1-007	All-pairs min-cut in sparse networks	Arikati, Chaudhuri, Zaroliagis	27
96-1-006	On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees	Das, Kapoor, Smid	14
96-1-005	Vorlesungsskript Komplexitätstheorie	Hagerup	150
96-1-004	Exact ground states of two-dimensional $\pm J$ Ising Spin Glasses	De Simone, Diehl, Jünger, Mutzel, Reinelt, Rinaldi	10
96-1-003	Proximity in arrangements of algebraic sets	Rieger	25
96-1-002	High-precision floating point numbers in LEDA	Burnikel, Könemann	47
95-1-029	Weak epsilon-nets for points on a hypersphere	Bradford, Capoyleas	8
95-1-028	Exact and heuristic algorithms for 2-layer straightline crossing minimization	Jünger, Mutzel	12
95-1-027	The thickness of a minor-excluded class of graphs	Jünger, Mutzel, Odenthal, Scharbrodt	9
95-1-026	Closest point problems in computational geometry	Smid	62
95-1-025	Matching nuts and bolts optimally	Bradford	24
95-1-024	Sorting in linear time?	Andersson, Nilsson, Hagerup, Raman	32
95-1-023	An algorithm for the protein docking problem	Lenhof	11
95-1-022	New deterministic algorithms for counting pairs of intersecting segments and off-line triangle range searching	Pellegrini	12
95-1-021	Shortest paths in digraphs of small treewidth part II: optimal parallel algirithms	Chaudhuri, Zaroliagis	20
95-1-020	Shortest paths in digraphs of small treewidth sequential algorithms	Chaudhuri, Zaroliagis	17
95-1-019	The fourth moment in Luby`s distribution	Dubhashi, Pantziou, Spirakis, Zaroliagis	10
95-1-018	Overview of mesh results	Sibeyn	22
95-1-017	Parallel algorithms with optimal speedup for bounded treewidth	Bodlaender, Hagerup	27
95-1-016	Wait-free consensus in "in-phase" multiprocessor systems	Papatriantafilou, Tsigas	12
95-1-015	Dynamic maintenance of 2-d convex hulls and order decomposable problems	Kapoor	22
95-1-014	A polyhedral approach to planar augmentation and related problems	Mutzel	14
95-1-013	Efficient computation of implicit representations of sparse graphs (revised version)	Arikati, Maheshwari, Zaroliagis	16
95-1-012	Sample sort on meshes	Sibeyn	14
95-1-010	On the average running time of odd-even merge sort	Rüb	16
95-1-009	Radix heaps an efficient implementation for priority queues	Könemann, Schmitz, Schwarz	27
95-1-007	Interactive Proof Systems	Radhakrishnan, Saluja	121
95-1-006	A polylog-time and $O(n\sqrt\lg n)$-work parallel algorithm for finding the row minima in totally monotone matrices	Bradford, Fleischer, Smid	12
95-1-005	Towards self-stabilizing wait-free shared memory objects	Hoepmann, Papatriantafilou, Tsigas	15
95-1-004	Exact ground states of Ising spin classes: new experimental results with a branch and cut algorithm	Diehl, De Simone, Jünger, Mutzel, Reinelt, Rinaldi	17
95-1-002	LEDA user manual (version R 3.2)	Näher, Uhrig	184
95-1-001	Computing a largest empty anchored cylinder, and related problems	Smid, Thiel, Follert, Schömer, Sellen	17
94-162	On the parallel complexity of degree sequence problems	Arikati	12
94-160	Implementation of a sweep line algorithm for the Straight \& Line Segment Intersection Problem	Mehlhorn, Näher	41
94-158	Further improvements of Steiner tree approximations	Karpinksi, Zelikovsky	10
94-156	Dynamic algorithms for geometric spanners of small diameter: randomized solutions	Arya, Mount, Smid	?
94-155	Lecture notes selected topics in data structures	Smid	76
94-153	Towards practical permutation routing on meshes	Kaufmann, Meyer, Sibeyn	11
94-150	On characteristic points and approximate decision algorithms for the minimum Hausdorff distance	Chew, Kedem, Schirra	10
94-149	Revenge of the dog: queries on Voronoi diagrams of moving points	Devillers, Golin, Schirra, Kedem	14
94-148	Efficient computation of compact representations of sparse graphs	Arikati, Maheshwari, Zaroliagis	10
94-147	Efficient collision detection for moving polyhedra	Schömer, Thiel	24
94-145	Prefix graphs and their applications	Chaudhuri, Hagerup	13
94-144	Stochastic majorisation: exploding some myths	Dubhashi, Ranjan	5
94-143	Some correlation inequalities for probabilistic analysis of algorithms	Dubhashi, Ranjan	16
94-142	The rectangle enclosure and point-dominance problems revisited	Gupta, Janardan, Smid, Dasgupta	16
94-137	Improved parallel integer sorting without concurrent writing	Albers, Hagerup	?
94-136	Near-optimal distributed edge	Dubhashi, Panconesi	12
94-131	Hammock-on-ears decomposition: a technique for the efficient parallel solution of shortest paths and other problems	Kavvadias, Pantziou, Spirakis, Zaroliagis	38
94-122	Realizing degree sequences in parallel	Arikati, Maheshwari	27
94-121	Short random walks on graphs	Barnes, Feige	14
94-120	A method for implementing lock-free shared data structures	Barnes	15
94-119	Time-space lower bounds for directed s-t connectivity on JAG models	Barnes, Edmonds	?
94-117	On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm	Mehlhorn, Mutzel	8
94-115	Efficient construction of a bounded degree spanner with low weight	Arya, Smid	25
94-114	On-line and dynamic algorithms for shortest path problems	Djidjev, Pantziou, Zaroliagis	20
94-113	Fast algorithms for collision and proximity problems involving moving geometric objects	Gupta, Janardan, Smid	22
94-112	On-line and Dynamic Shortest Paths through Graph Decompositions (Preliminary Version)	Djidjev, Pantziou, Zaroliagis	14
94-111	On the width and roundness of a set of points in the plane	Smid, Janardan	14
94-110	Quickest paths: faster algorithms and dynamization	Kargaris, Pantziou, Tragoudas, Zaroliagis	15
94-106	New on-line algorithms for the page replication problem	Albers, Koga	18
94-105	An implementation of a Convex Hull Algorithm, Version 1.0	Müller, Ziegler	63
94-104	Komplexitätstheorie und effiziente Algorithmen	Fleischer	30
94-103	On the intellectual terrain around NP	Chari, Hartmanis	11
94-102	Desnakification of mesh sorting algorithms	Sibeyn	21
93-166	Effizient algorithms for generalized intersection searching on non-iso-oriented objects	Gupta, Janardan, Smid	32
93-163	Deterministic 1-k routing on meshes with applications to worm-hole routing	Sibeyn, Kaufmann	13
93-162	On multi-party communication complexity of random functions	Grolmusz	10
93-161	Harmonic analysis, real approximation, and the communication complexity of Boolean functions	Grolmusz	15
93-159	New techniques for exact and approximate dynamic closest-point problems	Kapoor, Smid	29
93-155	Quantifier elimination in p-adic fields	Dubhashi	21
93-154	Searching, sorting and randomised algorithms for central elements and ideal counting in posets	Dubhashi, Mehlhorn, Ranjan, Thiel	8
93-152	Optimal parallel string algorithms: sorting, merching and computing the minimum	Hagerup	25
93-151	An implementation of the Hopcroft and Tarjan planarity test and embedding algorithm	Mehlhorn	20
93-148	Lower bounds for merging on the hypercube	Rüb	10
93-147	The complexity of parallel prefix problems on small domains	Chaudhuri, Radhakrishnan	17
93-146	A lower bound for linear approximate compaction	Chaudhuri	12
93-145	Sensitive functions and approximate problems	Chaudhuri	8
93-144	A lower bound for area-universal graphs	Bilardi, Chaudhuri, Dubhashi, Mehlhorn	7
93-142	MOD m gates do not help on the ground floor	Grolmusz	13
93-140	A complete and efficient algorithm for the intersection of a general convex polyhedron	Dobrindt, Mehlhorn, Yvinec	14
93-138	Routing and sorting on circular arrays	Sibeyn	20
93-132	Multi-party protocols and spectral norms	Grolmusz	11
93-129	Tight bounds for some problems in computational geometry: the complete sub-logarithmic parallel time range	Sen	12
93-128	Maintaining dynamic sequences under equality-tests in polylogorithmic time	Mehlhorn, Uhrig	17
93-124	Algorithms for some intersection searching problems involving curved objects	Gupta, Janardan, Smid	43
[Replication or Save Conflict]
93-123	Fast parallel space allocation, estimation and integer sorting (revised)	Bast, Hagerup	85
93-121	The circuit subfunction relations are $sum^P_2$-complete	Borchert, Ranjan	14
93-119	Generalized topological sorting in linear time	Hagerup, Maas	10
93-118	Approximate and exact deterministic parallel selection	Chaudhuri, Hagerup, Raman	10
93-110	Coloring k-colorable graphs in expected parallel time	Kucera	14
93-109	LEDA-Manual Version 3.0	Näher, Mehlhorn	140
93-108	Static and dynamic algorithms for k-point clustering problems	Smid, Datta, Lenhof, Schwarz	20
93-107	Expected complexity of graph partitioning problems	Kucera	16
93-106	Broadcasting through a noisy one-dimensional network	Kucera	14
93-105	Randomized incremental construction of abstract Voronoi diagrams	Klein, Mehlhorn, Meiser	29
93-103	Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection	Mehlhorn, Sharir, Welzl	12
93-102	Randomized Data Structures for the Dynamic Closest-Pair Problem	Golin, Raman, Schwarz, Smid	32
92-155	Simple randomized algorithms for closest pair problems	Golin, Raman, Schwarz, Smid	14
92-154	Further results on generalized intersection searching problems: counting, reporting, and dynamization	Smid, Gupta, Janardan	41
92-153	Semi-dynamic maintenance of the width of a planar point set	Schwarz	14
92-152	Finding k points with a smallest enclosing square	Smid	8
92-149	Fast deterministic processor allocation	Hagerup	11
92-145	not published	Hagerup, Mehlhorn, Munro
92-143	The influence of lookahead in competitive on-line algorithms	Albers	56
92-141	Waste makes haste: tight bounds for loose parallel sorting	Hagerup, Raman	185
92-135	Furthest site abstract Voronoi diagrams	Mehlhorn, Meiser, Rasch	25
92-134	Sequential and parallel algorithms for the k closest pairs problem	Lenhof, Smid	18
92-127	A lower bound for set intersection queries	Mehlhorn, Uhrig, Raman	14
92-126	Dynamic point location in general subdivisions	Baumgarten, Jung, Mehlhorn	30
92-125	A new lower bound technique for decision trees	Fleischer	21
92-123	The largest hyper-rectangle in a three dimensional orthogonal polyhedron	Krithivasan, Vanisree, Datta	7
92-122	A faster 11/6-approximation algorithm for the Steiner tree problem in graphs	Zelikovsky	8
92-121	Minimum base of weighted k polymatroid and Steiner tree problem	Zelikovsky	9
92-120	Separating the communication complexities of MOD m and MOD p circuits	Grolmusz	16
92-118	Enumerating the k closest pairs mechanically	Smid, Lenhof	12
92-115	Fast integer merging on the EREW PRAM	Hagerup, Kutylowski	12
92-112	Four results on randomized incremental constructions	Clarkson, Mehlhorn, Seidel	21
92-110	A method for obtaining randomized algorithms with small tail probalities	Alt, Guibas, Mehlhorn, Karp, Widgerson	5
92-108	Computing intersections and arrangements for red-blue curve segments in parallel	Rüb	30
92-104	Circuits and multi-party protocols	Grolmusz	16
92-102	Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity	Lenhof, Smid	16
92-101	A simple balanced search tree with 0(1) worst-case update time	Fleischer	10
91-126	Optimal embedding of a toroidal mesh in a path	Paterson, Schröder, Sýkora, Vrto	6
91-125	Edge separators for graphs of bounded genus with applications	Sýkora, Vrto	10
91-124	On crossing numbers of hypercubes and cube connected cycles	Sýkora, Vrto	6
91-123	An optimal algorithm for the on-line closest-pair problem	Schwarz, Smid, Snoeyink	11
91-122	On embeddings in cycles	Hromkovic, Müller, Sýkora, Vrto	22
91-121	On a compaction theorem of ragde	Hagerup	6
91-120	An $O(n^3)$-time maximum-flow algorithm	Cheriyan, Hagerup, Mehlhorn	30
91-115	A lower bound for the nondeterministic space complexity of contextfree recognition	Alt, Geffert, Mehlhorn	4
91-114	Algorithms for dense graphs and networks	Cheriyan, Mehlhorn	29
91-113	Tail estimates for the space complexity of randomized incremantal algorithms	Mehlhorn, Sharir, Welzl	8
91-112	An optimal construction method for generalized convex layers	Lenhof, Smid	25
91-110	Approximate decision algorithms for point set congruence	Heffernan, Schirra	25
91-107	An O(n log n log log n) algorithm for the on-line closes pair problem	Schwarz, Smid	21
91-106	Fast parallel space allocation, estimation an integer sorting	Hagerup	28
91-105	Simultaneous inner and outer aproximation of shapes	Fleischer, Mehlhorn, Rote, Welzl	24
91-104	A tight lower bound for the worst case of bottom-up-heapsort	Fleischer	13
91-103	Maintaining the minimal distance of a point set in polylogarithmic time (revised version)	Smid	17
91-102	Range trees with slack parameter	Smid	11
91-101	Dynamic rectangular point location, with an application to the closest pair problem	Smid	28

Imprint / Impressum | Data Protection / Datenschutzhinweis