MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2021

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

NumberTitleName(s)Pages
2013-1-001Attachment IconNew results for non-preemptive speed scalingOtt32
2010-1-001Attachment IconMaximum cardinality popular matchings in strict two-sided preference listsHuang, Kavitha17
2008-1-001Attachment IconCharacterizing the performance of Flash memory storage devices and its impact on algorithm designAjwani, Malinger, Meyer, Toledo36
2007-1-003Attachment IconLFthreads: a lock-free thread libraryGidenstam, Papatriantafilou36
2007-1-002Attachment IconA Lagrangian relaxation approach for the multiple sequence alignment problemAlthaus, Canzar41
2007-1-001A New Approximation Algorithm for thr Maximum Traveling Salesman ProblemPaluch?
2007-1-001Attachment IconLinear-time reordering in a sweep-line algorithm for algebraic curves intersecting in a common pointBerberich, Kettner20
2006-1-007Attachment IconOutput-sensitive autocompletion searchBast, Weber, Mortensen17
2006-1-006Attachment IconDivision-free computation of subresultants using bezout matricesKerber20
2006-1-005Attachment IconSnap rounding of Bézier curvesEigenwillig, Kettner, Wolpert39
2006-1-004Attachment IconPower assignment problems in wireless communicationFunke, Laue, Naujoks, Zvi25
2005-1-008Attachment IconCycle bases of graphs and sampled manifoldsGotsman, Kaligosi, Mehlhorn, Michail, Pyrga30
2005-1-007Attachment IconA faster algorithm for computing a longest common increasing
subsequence
Katriel, Kutz13
2005-1-003Attachment IconImproved algorithms for all-pairs approximate shortest paths in weighted graphsBaswana, Telikepalli26
2005-1-002Attachment IconReachability substitutes for planar digraphsKatriel, Kutz, Skutella24
2005-1-001Attachment IconRank-maximal through maximum weight matchingsMichail22
2004-1-006Attachment IconOn the Hadwiger's conjecture for graph productsChandran, Sivadasan12
2004-1-005Attachment IconA comparison of polynomial evaluation schemesSchmitt, Fousse19
2004-1-004Attachment IconOnline scheduling with bounded migrationSivadasan, Sanders, Skutella21
2004-1-003Attachment IconOn algorithms for online topological ordering and sortingKatriel15
2004-1-002Attachment IconA simpler linear time 2/3 - epsilon approximation for maximum weight matchingSanders, Pettie10
2004-1-001Attachment IconFiltering algorithms for the Same and UsedBy constraintsBeldiceanu, Katriel, Thiel36
2003-1-018Attachment IconA note on the smoothed complexity of the single-source shortest path problemSchaefer8
2003-1-017Attachment IconCross-monotonic cost sharing methods for connected facility location gamesSchäfer, Leonardi10
2003-1-016Attachment IconTopology matters: smoothed competitive analysis of metrical task systemsSchäfer, Sivadasan28
2003-1-015Attachment IconSum-Multicoloring on pathsKovács20
2003-1-014Attachment IconAverage case and smoothed competitive analysis of the multi-level feedback algorithmSchäfer, Becchetti, Leonardi, Marchetti-Spaccamela, Vredeveld31
2003-1-013Attachment IconFast bound consistency for the global cardinality constraintKatriel, Thiel30
2003-1-011Attachment IconSelfish traffic allocation for server farmsKrysta, Czumaj, Voecking43
2003-1-010Attachment IconA linear time heuristic for the branch-decomposition of planar graphsTamaki18
2003-1-009Attachment IconOn the Bollob\'as -- Eldridge conjecture for bipartite graphsCsaba29
2003-1-008Attachment IconPolynomial time algorithms for network information flowSanders15
2003-1-007Attachment IconAlternating cycles contribution: a strategy of tour-merging for the traveling salesman problemTamaki22
2003-1-006Attachment IconOn the probability of rendezvous in graphsDietzfelbinger, Tamaki30
2003-1-005Attachment IconAlmost random graphs with simple hash functionsDietzfelbinger, Woelfel23
2003-1-004Attachment IconImproving linear programming approaches for the Steiner tree problemAlthaus, Polzin, Daneshmand19
2003-1-003Attachment IconRandom knapsack in expected polynomial timeBeier, Vöcking22
2003-1-002Attachment IconScheduling and traffic allocation for tasks with bounded splittabilityKrysta, Sanders, Vöcking15
2003-1-001Attachment IconAsynchronous parallel disk sortingSanders, Dementiev22
2002-1-005Attachment IconPerformance of heuristic and approximation algorithms for the uncapacitated facility location problemHoefer27
2002-1-001Attachment IconUsing (sub)graphs of small width for solving the Steiner problemPolzin, Vahdati9
2001-1-007Attachment IconExtending reduction techniques for the Steiner tree problem: a combination of alternative-and bound-based approachesPolzin, Vahdati24
2001-1-006Attachment IconPartitioning techniques for the Steiner problemPolzin, Vahdati21
2001-1-005Attachment IconOn Steiner trees and minimum spanning trees in hypergraphsPolzin, Vahdati15
2001-1-004Attachment IconAn adaptable and extensible geometry kernelHert, Hoffmann, Kettner, Pion, Seel27
2001-1-003Attachment IconImplementation of planar Nef polyhedraSeel345
2001-1-002Attachment IconDirected single-source shortest-paths in linear average-case timeMeyer32
2001-1-001Attachment IconApproximating minimum size 1,2-connected networksKrysta22
2000-1-005Attachment IconInfimaximal frames: a technique for making lines look like segmentsSeel, Mehlhorn16
2000-1-004Attachment IconGeneralized and improved constructive separation bound for real algebraic expressionsMehlhorn, Schirra12
2000-1-003Attachment IconLow-contention depth-first scheduling of parallel computations with synchronization variablesFatourou56
2000-1-002Attachment IconA powerful heuristic for telephone gossipingBeier, Sibeyn23
2000-1-001Attachment IconA branch and cut algorithm for the optimal solution of the side-chain placement problemAlthaus, Kohlbacher, Lenhof, Müller26
1999-1-007Attachment IconA simple way to recognize a correct Voronoi diagram of line segmentsBurnikel, Mehlhorn, Seel11
1999-1-006Attachment IconIntegration of graph iterators into LEDANissen39
1999-1-005Attachment IconUltimate parallel list ranking?Sibeyn20
1999-1-004Attachment IconHow generic language extensions enable ''open-world'' design in JavaNissen, Weihe40
1999-1-003Attachment IconFast concurrent access to parallel disksSanders, Egner, Korst30
1999-1-002Attachment IconBALL: Biochemical Algorithms LibraryBoghossian, Kohlbacher, Lenhof20
1999-1-001Attachment IconA theoretical and experimental study on the construction of suffix arrays in external memoryCrauser, Ferragina40
98-1-031Attachment IconOptimal compaction of orthogonal grid drawingsKlau, Mutzel20
98-1-030Attachment IconApplications of the generic programming paradigm in the design of CGALBrönniman, Kettner, Schirra, Veltkamp12
98-1-029Attachment IconOptimizing over all combinatorial embeddings of a planar graphMutzel, Weiskircher23
98-1-028Attachment IconOn the performance of LEDA-SMCrauser, Mehlhorn, Althaus, Brengel, Buchheit, Keller, Krone, Lambert, Schulte, Thiel, Westphal, Wirth26
98-1-027Attachment IconDelaunay graphs by divide and conquerBurnikel24
98-1-026Attachment IconImproved approximation schemes for scheduling unrelated parallel machinesJansen, Porkolab14
98-1-025Attachment IconLinear-time approximation schemes for scheduling malleable parallel tasksJansen, Porkolab15
98-1-024Attachment Icon$q$-gram based database searching using a suffix array (QUASAR)Burkhardt, Crauser, Ferragina, Lenhof, Rivals, Vingron11
98-1-023Attachment IconRational points on circlesBurnikel14
98-1-022Attachment IconFast recursive divisionBurnikel, Ziegler29
98-1-021Attachment IconScheduling with unexpected machine breakdownsAlbers, Schmidt15
98-1-020Attachment IconOn Wallace's method for the generation of normal variatesRüb17
98-1-019Attachment Icon2nd Workshop on Algorithm Engineering WAE '98 - ProceedingsMehlhorn (ed.)213
98-1-018Attachment IconOn positive influence and negative dependenceDubhashi, Ranjan12
98-1-017Attachment IconRandomized external-memory algorithms for some geometric problemsCrauser, Ferragina, Mehlhorn, Meyer, Ramos27
98-1-016Attachment IconNew approximation algorithms for the achromatic numberKrysta, Lory\'{s}26
98-1-015Attachment IconScheduling multicasts on unit-capacity trees and meshesHenzinger, Leonardi38
98-1-014Attachment IconTime-independent gossiping on full-port toriMeyer, Sibeyn20
98-1-013Attachment IconQuasi-orthogonal drawing of planar graphsKlau, Mutzel15
98-1-012Attachment IconSolving some discrepancy problems in NC*Mahajan, Ramos, Subrahmanyam21
98-1-011Attachment IconRobustness analysis in combinatorial optimizationFrederickson, Solis-Oba66
98-1-010Attachment Icon2-Approximation algorithm for finding a spanning tree with maximum number of leavesSolis-Oba16
98-1-009Attachment IconFully dynamic shortest paths and negative cycle detection on diagraphs with Arbitrary Arc WeightsFrigioni, Marchetti-Spaccamela, Nanni18
98-1-008Attachment IconA note on computing a maximal planar subgraph using PQ-treesJünger, Leipert, Mutzel5
98-1-007Attachment IconOn the Design of CGAL, the Computational Geometry Algorithms LibraryFabri, Giezeman, Kettner, Schirra, Schönherr31
98-1-006Attachment IconA new characterization for parity graphs and a coloring problem with costsJansen16
98-1-005Attachment IconThe mutual exclusion scheduling problem for permutation and comparability graphsJansen12
98-1-004Attachment IconRobustness and precision issues in geometric computationSchirra34
98-1-003Attachment IconParameterized implementations of classical planar convex hull algorithms and extreme point compuationsSchirra93
98-1-002Attachment IconComparator networks for binary heap constructionBrodal, Pinotti11
98-1-001Attachment IconSimpler and faster static AC$^0$ dictionariesHagerup13
97-1-028Attachment IconThe practical use of the $\calA^*$ algorithm for exact multiple sequence alignmentLermen, Reinert16
97-1-027Attachment IconA polylogarithmic approximation algorithm for group Steiner tree problemGarg, Konjevod, Ravi7
97-1-026Attachment IconOn-line network routing - a surveyFiat, Leonardi19
97-1-025Attachment IconFaster and simpler algorithms for multicommodity flow and other fractional packing problemsGarg, Könemann13
97-1-024Attachment IconMinimizing stall time in single and parallel disk systemsAlbers, Garg, Leonardi16
97-1-023Attachment IconRandomized on-line call control revisitedLeonardi, Marchetti-Spaccamela19
97-1-022Attachment IconMaximum network flow with floating point arithmeticAlthaus, Mehlhorn5
97-1-021Attachment IconFrom parallel to external list rankingSibeyn15
97-1-020Attachment IconFinger search trees with constant insertion timeBrodal17
97-1-019Attachment IconAGD-Library: A Library of Algorithms for Graph DrawingAlberts, Gutwenger, Mutzel, Näher13
97-1-018Attachment IconOn the Bahncard problemFleischer16
97-1-017Attachment IconExploring unknown environmentsAlbers, Henzinger23
97-1-016Attachment IconFaster deterministic sorting and priority queues in linear spaceThorup9
97-1-015Attachment IconPitfalls of using PQ--Trees in automatic graph drawingJünger, Leipert, Mutzel12
97-1-014Attachment IconDesigning a Computational Geometry Algorithms LibrarySchirra8
97-1-013Attachment IconDatenstrukturen und AlgorithmenHagerup223
97-1-012Attachment IconOn Batcher's Merge Sorts as Parallel Sorting AlgorithmsRüb23
97-1-011Attachment IconA parallel priority queue with constant time operationsBrodal, Träff, Zaroliagis19
97-1-010Attachment IconEvaluating a 2-approximation algorithm for edge-separators in planar graphsGarg, Manss9
97-1-009Attachment IconBetter bounds for online schedulingAlbers16
97-1-008Attachment IconAn alternative method to crossing minimization on hierarchical graphsMutzel15
97-1-007Attachment IconAlgorithmen zum automatischen Zeichnen von GraphenBrandenburg, Jünger, Mutzel9
97-1-006Attachment IconRestricted 2-factor polytopesCunningham, Wang30
97-1-005Attachment IconBicriteria job sequencing with release datesWang18
97-1-004Attachment IconNew contact measures for the protein docking problemLenhof10
97-1-003Attachment IconParallel algorithms for MD-simulations of synthetic polymersJung, Lenhof, Müller, Rüb32
97-1-002Attachment IconApproximating sparsest cutsGarg9
97-1-001Attachment IconBSP-like external-memory computationSibeyn, Kaufmann14
96-1-033Attachment IconA runtime test of integer arithmetic and linear algebra in LEDASeel10
96-1-032Attachment IconRuntime prediction of real programs on real machinesFinkler, Mehlhorn10
96-1-031Attachment IconOn the complexity of computing evolutionary treesGasieniec, Jansson, Lingas, Östlin14
96-1-030Attachment IconExternal inverse pattern matchingGasieniec, Indyk, Krysta12
96-1-029Attachment IconLower bounds for row minima searchingBradford, Reinert12
96-1-028Attachment IconA branch-and-cut algorithm for multiple sequence alignmentReinert, Lenhof, Mutzel, Mehlhorn, Kececioglou15
96-1-027Attachment IconA branch-and-cut approach to physical mapping with end-probesChristof, Jünger, Kececioglou, Mutzel, Reinelt10
96-1-026Attachment IconA survey of self-organizing data structuresAlbers, Westbrook39
96-1-025Attachment Icon2-Layer straigthline crossing minimization: performance of exact and heuristic algorithmsJünger, Mutzel14
96-1-024Attachment IconMore geneal parallel tree contraction: Register allocation and broadcasting in a treeDiks, Hagerup24
96-1-023Attachment IconDiscovering all most specific sentences by randomized algorithmsGunopulos, Mannila, Saluja23
96-1-022Attachment IconOptimal algorithms for some proximity problems on the Gaussian sphere with applicationsSaluja, Gupta8
96-1-021Attachment IconGeneralized $k$-Center ProblemsGarg, Chaudhuri, Ravi9
96-1-020Attachment IconNegative dependence through the FKG InequalityDubhashi, Priebe, Ranjan10
96-1-019Attachment IconRotations of periodic strings and short superstringsBreslauer, Jiang, Jiang13
96-1-018Attachment IconGossiping on meshes and toriSibeyn, Rao, Juurlink19
96-1-017Attachment IconA technique for adding range restrictions to generalized searching problemsGupta, Janardan, Smid9
96-1-016Attachment IconA computational basis for higher-dimensional computational geometryMehlhorn, Näher, Schirra, Seel, Uhrig120
96-1-015Attachment IconComputational Molecular BiologyVingron, Lenhof, Mutzel26
96-1-014Attachment IconThe randomized complexity of maintaining the minimumBrodal, Chaudhuri, Radhakrishnan12
96-1-013Attachment IconDerandomizing semidefinite programming based approximation algorithmsMahajan, Ramesh22
96-1-012Attachment IconA simple parallel algorithm for the single-source shortest path problem on planar diagraphsTräff, Zaroliagis17
96-1-011Attachment IconThe impact of timing on linearizability in counting networksMavronicolas, Papatriantafilou, Tsigas19
96-1-010Attachment IconDistributed list coloring: how to dynamically allocate frequencies to mobile base stationsGarg, Papatriantafilou, Tsigas15
96-1-009Attachment IconThe thickness of graphs: a surveyMutzel, Odenthal, Scharbrodt18
96-1-008Attachment IconEfficient algorithms for counting and reporting pairwise intersections between convex polygonsGupta, Janardan, Smid11
96-1-007Attachment IconAll-pairs min-cut in sparse networksArikati, Chaudhuri, Zaroliagis27
96-1-006Attachment IconOn the complexity of approximating Euclidean traveling salesman tours and minimum spanning treesDas, Kapoor, Smid14
96-1-005Attachment IconVorlesungsskript KomplexitätstheorieHagerup150
96-1-004Attachment IconExact ground states of two-dimensional $\pm J$ Ising Spin GlassesDe Simone, Diehl, Jünger, Mutzel, Reinelt, Rinaldi10
96-1-003Attachment IconProximity in arrangements of algebraic setsRieger25
96-1-002Attachment IconHigh-precision floating point numbers in LEDABurnikel, Könemann47
95-1-029Attachment IconWeak epsilon-nets for points on a hypersphereBradford, Capoyleas8
95-1-028Attachment IconExact and heuristic algorithms for 2-layer straightline crossing minimizationJünger, Mutzel12
95-1-027Attachment IconThe thickness of a minor-excluded class of graphsJünger, Mutzel, Odenthal, Scharbrodt9
95-1-026Attachment IconClosest point problems in computational geometrySmid62
95-1-025Attachment IconMatching nuts and bolts optimallyBradford24
95-1-024Attachment IconSorting in linear time?Andersson, Nilsson, Hagerup, Raman32
95-1-023Attachment IconAn algorithm for the protein docking problemLenhof11
95-1-022Attachment IconNew deterministic algorithms for counting pairs of intersecting segments and off-line triangle range searchingPellegrini12
95-1-021Attachment IconShortest paths in digraphs of small treewidth part II: optimal parallel algirithmsChaudhuri, Zaroliagis20
95-1-020Attachment IconShortest paths in digraphs of small treewidth sequential algorithmsChaudhuri, Zaroliagis17
95-1-019Attachment IconThe fourth moment in Luby`s distributionDubhashi, Pantziou, Spirakis, Zaroliagis10
95-1-018Attachment IconOverview of mesh resultsSibeyn22
95-1-017Attachment IconParallel algorithms with optimal speedup for bounded treewidthBodlaender, Hagerup27
95-1-016Attachment IconWait-free consensus in "in-phase" multiprocessor systemsPapatriantafilou, Tsigas12
95-1-015Attachment IconDynamic maintenance of 2-d convex hulls and order decomposable problemsKapoor22
95-1-014Attachment IconA polyhedral approach to planar augmentation and related problemsMutzel14
95-1-013Attachment IconEfficient computation of implicit representations of sparse graphs (revised version)Arikati, Maheshwari, Zaroliagis16
95-1-012Attachment IconSample sort on meshesSibeyn14
95-1-010Attachment IconOn the average running time of odd-even merge sortRüb16
95-1-009Attachment IconRadix heaps an efficient implementation for priority queuesKönemann, Schmitz, Schwarz27
95-1-007Attachment IconInteractive Proof SystemsRadhakrishnan, Saluja121
95-1-006Attachment IconA polylog-time and $O(n\sqrt\lg n)$-work parallel algorithm for finding the row minima in totally monotone matricesBradford, Fleischer, Smid12
95-1-005Attachment IconTowards self-stabilizing wait-free shared memory objectsHoepmann, Papatriantafilou, Tsigas15
95-1-004Attachment IconExact ground states of Ising spin classes: new experimental results with a branch and cut algorithmDiehl, De Simone, Jünger, Mutzel, Reinelt, Rinaldi17
95-1-002Attachment IconLEDA user manual (version R 3.2)Näher, Uhrig184
95-1-001Attachment IconComputing a largest empty anchored cylinder, and related problemsSmid, Thiel, Follert, Schömer, Sellen17
94-162Attachment IconOn the parallel complexity of degree sequence problemsArikati12
94-160Attachment IconImplementation of a sweep line algorithm for the Straight \& Line Segment Intersection ProblemMehlhorn, Näher41
94-158Attachment IconFurther improvements of Steiner tree approximationsKarpinksi, Zelikovsky10
94-156Attachment IconDynamic algorithms for geometric spanners of small diameter: randomized solutionsArya, Mount, Smid?
94-155Attachment IconLecture notes selected topics in data structuresSmid76
94-153Attachment IconTowards practical permutation routing on meshesKaufmann, Meyer, Sibeyn11
94-150Attachment IconOn characteristic points and approximate decision algorithms for the minimum Hausdorff distanceChew, Kedem, Schirra10
94-149Attachment IconRevenge of the dog: queries on Voronoi diagrams of moving pointsDevillers, Golin, Schirra, Kedem14
94-148Attachment IconEfficient computation of compact representations of sparse graphsArikati, Maheshwari, Zaroliagis10
94-147Attachment IconEfficient collision detection for moving polyhedraSchömer, Thiel24
94-145Attachment IconPrefix graphs and their applicationsChaudhuri, Hagerup13
94-144Attachment IconStochastic majorisation: exploding some mythsDubhashi, Ranjan5
94-143Attachment IconSome correlation inequalities for probabilistic analysis of algorithmsDubhashi, Ranjan16
94-142Attachment IconThe rectangle enclosure and point-dominance problems revisitedGupta, Janardan, Smid, Dasgupta16
94-137Attachment IconImproved parallel integer sorting without concurrent writingAlbers, Hagerup?
94-136Attachment IconNear-optimal distributed edgeDubhashi, Panconesi12
94-131Attachment IconHammock-on-ears decomposition: a technique for the efficient parallel solution of shortest paths and other problemsKavvadias, Pantziou, Spirakis, Zaroliagis38
94-122Attachment IconRealizing degree sequences in parallelArikati, Maheshwari27
94-121Attachment IconShort random walks on graphsBarnes, Feige14
94-120Attachment IconA method for implementing lock-free shared data structuresBarnes15
94-119Attachment IconTime-space lower bounds for directed s-t connectivity on JAG modelsBarnes, Edmonds?
94-117Attachment IconOn the embedding phase of the Hopcroft and Tarjan planarity testing algorithmMehlhorn, Mutzel8
94-115Attachment IconEfficient construction of a bounded degree spanner with low weightArya, Smid25
94-114Attachment IconOn-line and dynamic algorithms for shortest path problemsDjidjev, Pantziou, Zaroliagis20
94-113Attachment IconFast algorithms for collision and proximity problems involving moving geometric objectsGupta, Janardan, Smid22
94-112Attachment IconOn-line and Dynamic Shortest Paths through Graph Decompositions (Preliminary Version)Djidjev, Pantziou, Zaroliagis14
94-111Attachment IconOn the width and roundness of a set of points in the planeSmid, Janardan14
94-110Attachment IconQuickest paths: faster algorithms and dynamizationKargaris, Pantziou, Tragoudas, Zaroliagis15
94-106Attachment IconNew on-line algorithms for the page replication problemAlbers, Koga18
94-105Attachment IconAn implementation of a Convex Hull Algorithm, Version 1.0Müller, Ziegler63
94-104Attachment IconKomplexitätstheorie und effiziente AlgorithmenFleischer30
94-103Attachment IconOn the intellectual terrain around NPChari, Hartmanis11
94-102Attachment IconDesnakification of mesh sorting algorithmsSibeyn21
93-166Attachment IconEffizient algorithms for generalized intersection searching on non-iso-oriented objectsGupta, Janardan, Smid32
93-163Attachment IconDeterministic 1-k routing on meshes with applications to worm-hole routingSibeyn, Kaufmann13
93-162Attachment IconOn multi-party communication complexity of random functionsGrolmusz10
93-161Attachment IconHarmonic analysis, real approximation, and the communication complexity of Boolean functionsGrolmusz15
93-159Attachment IconNew techniques for exact and approximate dynamic closest-point problemsKapoor, Smid29
93-155Attachment IconQuantifier elimination in p-adic fieldsDubhashi21
93-154Attachment IconSearching, sorting and randomised algorithms for central elements and ideal counting in posetsDubhashi, Mehlhorn, Ranjan, Thiel8
93-152Attachment IconOptimal parallel string algorithms: sorting, merching and computing the minimumHagerup25
93-151Attachment IconAn implementation of the Hopcroft and Tarjan planarity test and embedding algorithmMehlhorn20
93-148Attachment IconLower bounds for merging on the hypercubeRüb10
93-147Attachment IconThe complexity of parallel prefix problems on small domainsChaudhuri, Radhakrishnan17
93-146Attachment IconA lower bound for linear approximate compactionChaudhuri12
93-145Attachment IconSensitive functions and approximate problemsChaudhuri8
93-144Attachment IconA lower bound for area-universal graphsBilardi, Chaudhuri, Dubhashi, Mehlhorn7
93-142Attachment IconMOD m gates do not help on the ground floorGrolmusz13
93-140Attachment IconA complete and efficient algorithm for the intersection of a general convex polyhedronDobrindt, Mehlhorn, Yvinec14
93-138Attachment IconRouting and sorting on circular arraysSibeyn20
93-132Attachment IconMulti-party protocols and spectral normsGrolmusz11
93-129Attachment IconTight bounds for some problems in computational geometry: the complete sub-logarithmic parallel time rangeSen12
93-128Attachment IconMaintaining dynamic sequences under equality-tests in polylogorithmic timeMehlhorn, Uhrig17
93-124Attachment IconAlgorithms for some intersection searching problems involving curved objectsGupta, Janardan, Smid43
[Replication or Save Conflict]
93-123Attachment IconFast parallel space allocation, estimation and integer sorting (revised)Bast, Hagerup85
93-121Attachment IconThe circuit subfunction relations are $sum^P_2$-completeBorchert, Ranjan14
93-119Attachment IconGeneralized topological sorting in linear timeHagerup, Maas10
93-118Attachment IconApproximate and exact deterministic parallel selectionChaudhuri, Hagerup, Raman10
93-110Attachment IconColoring k-colorable graphs in expected parallel timeKucera14
93-109Attachment IconLEDA-Manual Version 3.0Näher, Mehlhorn140
93-108Attachment IconStatic and dynamic algorithms for k-point clustering problemsSmid, Datta, Lenhof, Schwarz20
93-107Attachment IconExpected complexity of graph partitioning problemsKucera16
93-106Attachment IconBroadcasting through a noisy one-dimensional networkKucera14
93-105Attachment IconRandomized incremental construction of abstract Voronoi diagramsKlein, Mehlhorn, Meiser29
93-103Attachment IconTail estimates for the efficiency of randomized incremental algorithms for line segment intersectionMehlhorn, Sharir, Welzl12
93-102Attachment IconRandomized Data Structures for the Dynamic Closest-Pair ProblemGolin, Raman, Schwarz, Smid32
92-155Attachment IconSimple randomized algorithms for closest pair problemsGolin, Raman, Schwarz, Smid14
92-154Attachment IconFurther results on generalized intersection searching problems: counting, reporting, and dynamizationSmid, Gupta, Janardan41
92-153Attachment IconSemi-dynamic maintenance of the width of a planar point setSchwarz14
92-152Attachment IconFinding k points with a smallest enclosing squareSmid8
92-149Attachment IconFast deterministic processor allocationHagerup11
92-145not publishedHagerup, Mehlhorn, Munro
92-143Attachment IconThe influence of lookahead in competitive on-line algorithmsAlbers56
92-141Attachment IconWaste makes haste: tight bounds for loose parallel sortingHagerup, Raman185
92-135Attachment IconFurthest site abstract Voronoi diagramsMehlhorn, Meiser, Rasch25
92-134Attachment IconSequential and parallel algorithms for the k closest pairs problemLenhof, Smid18
92-127Attachment IconA lower bound for set intersection queriesMehlhorn, Uhrig, Raman14
92-126Attachment IconDynamic point location in general subdivisionsBaumgarten, Jung, Mehlhorn30
92-125Attachment IconA new lower bound technique for decision treesFleischer21
92-123Attachment IconThe largest hyper-rectangle in a three dimensional orthogonal polyhedronKrithivasan, Vanisree, Datta7
92-122Attachment IconA faster 11/6-approximation algorithm for the Steiner tree problem in graphsZelikovsky8
92-121Attachment IconMinimum base of weighted k polymatroid and Steiner tree problemZelikovsky9
92-120Attachment IconSeparating the communication complexities of MOD m and MOD p circuitsGrolmusz16
92-118Attachment IconEnumerating the k closest pairs mechanicallySmid, Lenhof12
92-115Attachment IconFast integer merging on the EREW PRAMHagerup, Kutylowski12
92-112Attachment IconFour results on randomized incremental constructionsClarkson, Mehlhorn, Seidel21
92-110Attachment IconA method for obtaining randomized algorithms with small tail probalitiesAlt, Guibas, Mehlhorn, Karp, Widgerson5
92-108Attachment IconComputing intersections and arrangements for red-blue curve segments in parallelRüb30
92-104Attachment IconCircuits and multi-party protocolsGrolmusz16
92-102Attachment IconMaintaining the visibility map of spheres while moving the viewpoint on a circle at infinityLenhof, Smid16
92-101Attachment IconA simple balanced search tree with 0(1) worst-case update timeFleischer10
91-126Attachment IconOptimal embedding of a toroidal mesh in a pathPaterson, Schröder, Sýkora, Vrto6
91-125Attachment IconEdge separators for graphs of bounded genus with applicationsSýkora, Vrto10
91-124Attachment IconOn crossing numbers of hypercubes and cube connected cyclesSýkora, Vrto6
91-123Attachment IconAn optimal algorithm for the on-line closest-pair problemSchwarz, Smid, Snoeyink11
91-122Attachment IconOn embeddings in cyclesHromkovic, Müller, Sýkora, Vrto22
91-121Attachment IconOn a compaction theorem of ragdeHagerup6
91-120Attachment IconAn $O(n^3)$-time maximum-flow algorithmCheriyan, Hagerup, Mehlhorn30
91-115Attachment IconA lower bound for the nondeterministic space complexity of contextfree recognitionAlt, Geffert, Mehlhorn4
91-114Attachment IconAlgorithms for dense graphs and networksCheriyan, Mehlhorn29
91-113Attachment IconTail estimates for the space complexity of randomized incremantal algorithmsMehlhorn, Sharir, Welzl8
91-112Attachment IconAn optimal construction method for generalized convex layersLenhof, Smid25
91-110Attachment IconApproximate decision algorithms for point set congruenceHeffernan, Schirra25
91-107Attachment IconAn O(n log n log log n) algorithm for the on-line closes pair problemSchwarz, Smid21
91-106Attachment IconFast parallel space allocation, estimation an integer sortingHagerup28
91-105Attachment IconSimultaneous inner and outer aproximation of shapesFleischer, Mehlhorn, Rote, Welzl24
91-104Attachment IconA tight lower bound for the worst case of bottom-up-heapsortFleischer13
91-103Attachment IconMaintaining the minimal distance of a point set in polylogarithmic time (revised version)Smid17
91-102Attachment IconRange trees with slack parameterSmid11
91-101Attachment IconDynamic rectangular point location, with an application to the closest pair problemSmid28