Browse

ftp://ftp.mpi-sb.mpg.de (82)

	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-92-224.ps.Z, 19920629 1 Completeness of Resolution and Superposition Calculi Rolf Socher-Ambrosius Max-Planck-Institut f r Informatik, Im Stadtwald, D-W-6600 Saarbr cken, Germany email: socher@mpi-sb.mpg.de
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-92-207.ps.Z, 19920629 1 Semi-Unification Rolf Socher-Ambrosius Max-Planck-Institut f r Informatik, Im Stadtwald, D-W-6600 Saarbr cken, Germany email: socher@mpi-sb.mpg.de
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-92-206.ps.Z, 19920629 1 A Goal Oriented Strategy Based on Completion Rolf Socher-Ambrosius* Max-Planck-Institut f r Informatik, Im Stadtwald, D-W-6600 Saarbr cken, Germany email: socher@mpi-sb.mpg.de
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-93-217.ps.Z, 19930505 1 Unification of Terms With Exponents Rolf Socher-Ambrosius MPI I 93 217 May 1993 2 Unification Of Terms With Exponents Rolf Socher-Ambrosius* Max-Planck-Institut f r Informatik, Im Stadtwald W-6600 Saarbr cken, Germany e-mail: socher@mpi-sb.mpg.de
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-93-237.ps.Z, 19931201 1 A Refined Version of General E-Unification Rolf Socher-Ambrosius* MPI Informatik, Im Stadtwald, D-66123 Saarbr cken, Germany Tel. +49 681 302 5367 e-mail: socher@mpi-sb.mpg.de
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-209.ps.Z, 19940223 MAX-PLANCK-INSTITUT F UR INFORMATIK Termination Orderings for Rippling David A. Basin Toby Walsh MPI{I{94{209 February 1994 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Authors' Addresses David Basin Max-Planck-Institut f ur Informatik Im Satdwald, D-66123 Saarbr ucken, Germany
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-216.ps.Z, 19940415 MAX-PLANCK-INSTITUT F UR INFORMATIK Linear -1 Inequalities and Extended Clauses Peter Barth MPI{I{94{216 April 1994 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Author's Address Peter Barth Max-Planck-Institut f ur Informatik Im Stadtwald 66123 Saarbr ucken, Germany Email:
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-208.ps.Z, 19940505 A Probabilistic Extension of Terminological Logics Manfred Jaeger MPI{I{94{208 March 1994 Author's Address Manfred Jaeger Max-Planck-Institut f ur Informatik Im Stadtwald 66123 Saarbr ucken Germany jaeger@mpi-sb.mpg.de
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-93-250.ps.Z, 19940518 MAX-PLANCK-INSTITUT F UR INFORMATIK Ordered Chaining for Total Orderings Leo Bachmair Harald Ganzinger MPI{I{93{250 December 1993 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Addresses Leo Bachmair, Department of Computer Science, SUNY at Stony Brook, Stony Brook, NY 11794,
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-93-249.ps.Z, 19940518 MAX-PLANCK-INSTITUT F UR INFORMATIK Rewrite Techniques for Transitive Relations Leo Bachmair Harald Ganzinger MPI{I{93{249 November 1993 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Addresses Leo Bachmair, Department of Computer Science, SUNY at Stony Brook, Stony Brook, NY
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-102.ps.Z, 19940520 Desnakification of Mesh Sorting Algorithms Jop F. Sibeyn
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-93-138.ps.Z, 19940520 Routing and Sorting on Circular Arrays Jop F. Sibeyn
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-93-163.ps.Z, 19940520 Deterministic 1-k Routing on Meshes With Applications to Worm-Hole Routing Jop F. Sibeyn Michael Kaufmanny
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-226.ps.gz, 19940604 MAX-PLANCK-INSTITUT F UR INFORMATIK Killer Transformations Hans J urgen Ohlbach Dov Gabbay David Plaisted MPI{I{94{226 June 94 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Author's Address Hans J urgen Ohlbach Max{Planck{Institut f ur Informatik Im Stadtwald D-66123 Saarbr ucken
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-228.ps.gz, 19940701 MAX-PLANCK-INSTITUT F UR INFORMATIK Computer Support for the Development and Investigation of Logics Hans J urgen Ohlbach MPI{I{94{228 June 94 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Author's Address Hans J urgen Ohlbach Max{Planck{Institut f ur Informatik Im Stadtwald
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-232.ps.gz, 19940718 MAX-PLANCK-INSTITUT F UR INFORMATIK An Abstract Program Generation Logic David A. Plaisted MPI{I{94{232 July 1994 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Authors' Addresses David Plaisted Max-Planck-Institut f ur Informatik Im Stadtwald D-66123 Saarbr ucken Germany
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-233.ps.gz, 19940721 MAX-PLANCK-INSTITUT F UR INFORMATIK The Search Efficiency of Theorem Proving Strategies: An Analytical Comparison David A. Plaisted MPI{I{94{233 July 1994 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Authors' Addresses David Plaisted Max-Planck-Institut f ur Informatik Im
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-235.ps.gz, 19940803 MAX-PLANCK-INSTITUT F UR INFORMATIK Ordered Semantic Hyper-Linking David A. Plaisted MPI{I{94{235 August 1994 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Authors' Addresses David Plaisted Max-Planck-Institut f ur Informatik Im Stadtwald D-66123 Saarbr ucken Germany
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-251.ps.gz, 19941128 MAX-PLANCK-INSTITUT F UR INFORMATIK Substitution Tree Indexing Peter Graf MPI{I{94{251 October 1994 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Author's Address Peter Graf (graf@mpi-sb.mpg.de), Max{Planck{Institut f ur Informatik Im Stadtwald D-66123 Saarbr ucken Germany
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-153.ps.gz, 19950113 Towards Practical Permutation Routing on Meshes Michael Kaufmann Uli Meyery Jop F. Sibeynz
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-2-005.ps.gz, 19950113 MAX-PLANCK-INSTITUT F UR INFORMATIK A Multi-Dimensional Terminological Knowledge Representation Language Franz Baader Hans J urgen Ohlbach MPI{I{95{2{005 January 1995 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Authors' Addresses Franz Baader LuFG Theoretische Informatik RWTH
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-2-001.ps.Z, 19950116 MAX-PLANCK-INSTITUT F UR INFORMATIK Proof Normalization and Subject Reduction in Extensions of Fsub Sergei Vorobyov MPI{I{95{2{001 January 1995 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Author's Address Sergei Vorobyov (sv@mpi-sb.mpg.de), Max{Planck{Institut f ur Informatik
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-1-004.ps.gz, 19950220 C. De Simone M. Diehl M. J unger P. Mutzel G. Reinelt G. Rinaldi EXACT GROUND STATES OF ISING SPIN GLASSES: NEW EXPERIMENTAL RESULTS WITH A BRANCH AND CUT ALGORITHM Caterina De Simone, Giovanni Rinaldi - Istituto di Analisi dei Sistemi ed Informatica del CNR - Viale Manzoni 30, 00185 Roma, Italy Martin
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-93-151.ps.gz, 19950220 An Implementation of the Hopcroft and Tarjan Planarity Test and Embedding Algorithm Kurt Mehlhorn Max-Planck-Institut f ur Informatik, 66123 Saarbr ucken, Germany Petra Mutzel Institut f ur Informatik, Universit at zu K oln, 50969 K oln, Germany Stefan N aher Max-Planck-Institut f ur Informatik, 66123
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/progress_report_95.ps.Z, 19950221 SECOND PROGRESS REPORT 1993 { 1995 February 1995 INFORMATIK Max{Planck{Institut f ur Informatik Im Stadtwald 66123 Saarbr ucken Germany Contents I Overview 1 II The Algorithms and Complexity Group 5 1 Personnel 7 2 Executive Summary 8 3 Research Themes 11 3.1 Parallel and Distributed Computing : : : : :
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-117.ps.gz, 19950308 On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm Kurt Mehlhorn and Petra Mutzel y
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-1-011.ps.gz, 19950403 Automatisiertes Zeichnen von Diagrammen* Petra Mutzel Max-Planck-Institut f. Informatik Im Stadtwald, D-66123 Saarbr ucken Ein sehr anwendungsnahes Forschungsgebiet, bei dem viele NP-schwere Optimierungsprobleme auftauchen ist das automatisierte Zeichnen von Diagrammen bzw. Graphen. Hierbei sind Objekte
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-147.ps.gz, 19950426 Efficient collision detection for moving polyhedra Elmar Sch omer Christian Thiely April 25, 1995
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-2-008.ps.gz, 19950504 MAX-PLANCK-INSTITUT F UR INFORMATIK Translating Graded Modalities into Predicate Logic Hans J urgen Ohlbach Renate A. Schmidt Ullrich Hustadt MPI{I{95{2{008 May 1995 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Authors' Addresses Max-Planck-Institut f ur Informatik, Im
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-2-003.ps.Z, 19950517 MAX-PLANCK-INSTITUT F UR INFORMATIK A Davis-Putnam Based Enumeration Algorithm for Linear Pseudo-Boolean Optimization Peter Barth MPI{I{95{2-003 January 1995 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Author's Address Peter Barth, Max-Planck-Institut f ur Informatik, Im
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-1-016.ps.gz, 19950726 Wait-free Consensus in In-phase" Multiprocessor Systems Marina Papatriantafilou Max-Planck-Institut f ur Informatik Im Stadtwald, 66123 Saarbr ucken, Germany & CTI & Patras University, Greece ptrianta@mpi-sb.mpg.de Philippas Tsigas Max-Planck-Institut f ur Informatik Im Stadtwald, 66123 Saarbr ucken,
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-93-230.ps.gz, 19950814 MAX-PLANCK-INSTITUT F UR INFORMATIK Classical vs Non-classical Logics The Universality of Classical Logic Dov M Gabbay MPI{I{93{230 August 1993 Oo Oo k I N F O R M A T I K Im Stadtwald W 66123 Saarbr ucken Germany Author's Address Dov M Gabbay Imperial College of Science, Technology and Medicine 180
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-92-219.ps.gz, 19950817 Unification and Matching in Church's Original Lambda Calculus Ullrich Hustadt MPI{I{92{219 June 1992 Author's Address Ullrich Hustadt Max-Planck-Institut f ur Informatik Im Stadtwald W-6600 Saarbr ucken Germany E-mail: Ullrich.Hustadt@mpi-sb.mpg.de
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-91-228.ps.gz, 19950817 A Complete Transformation System for Polymorphic Higher-Order Unification Ullrich Hustadt MPI{I{91{228 December 1991 Author's Address Ullrich Hustadt Max-Planck-Institut f ur Informatik Im Stadtwald W-6600 Saarbr ucken Germany E-mail: Ullrich.Hustadt@mpi-sb.mpg.de
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-1-007.ps.gz, 19950822 Lecture Notes Interactive Proof Systems Jaikumar Radhakrishnan and Sanjeev Saluja Theoretical Computer Science group Tata Institute of Fundamental Research Homi Bhabha Road Bombay 400005. email:fjaikumar,salujag@tcs.tifr.res.in 24 February, 1995 Technical Report No.: TCS-95/4 Preface In Spring 1994, we
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-142.ps.gz, 19950822 The rectangle enclosure and point-dominance problems revisited Prosenjit Gupta y Ravi Janardan y Michiel Smidz Bhaskar Dasguptaxy August 22, 1995
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-148.ps.Z, 19950822 Efficient Computation of Compact Representations of Sparse Graphs Srinivasa Rao Arikati Anil Maheshwariy Christos Zaroliagis Max-Planck Institute f ur Informatik Im Stadtwald, D-66123 Saarbr ucken Germany E-mail : farikati,anil,zarog@mpi-sb.mpg.de December 27, 1994
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-1-013.ps.Z, 19950822 Efficient Computation of Implicit Representations of Sparse Graphs (Revised Version) S.R. Arikati A. Maheshwari C.D. Zaroliagis MPI{I{95{1-013 June 1995 Efficient Computation of Implicit Representations of Sparse Graphs (Revised Version) Srinivasa R. Arikati 1 Anil Maheshwari 2y Christos D. Zaroliagis 1
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-93-102.ps.gz, 19950822 Randomized Data Structures for the Dynamic Closest-Pair Problem Mordecai Goliny Rajeev Ramanz Christian Schwarzx Michiel Smid{
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-1-019.ps.Z, 19950822 The Fourth Moment in Luby's Distribution Devdatt P. Dubhashi Grammati E. Pantziou Paul G. Spirakis Christos D. Zaroliagis MPI{I{95{1-019 August 1995 The Fourth Moment in Luby's Distribution Devdatt P. Dubhashi BRICS y Department of Computer Science, University of Aarhus, Ny Munkegade, DK-8000 Aarhus C,
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-93-124.ps.gz, 19950822 Algorithms for Some Intersection Searching Problems Involving Curved Objects Prosenjit Guptay Ravi Janardany Michiel Smidz August 22, 1995
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-131.ps.Z, 19950822 Hammock-on-Ears Decomposition: A Technique for the Efficient Parallel Solution of Shortest Paths and Other Problems Dimitris Kavvadias Computer Technology Institute, P.O. Box 1122, 26110 Patras, Greece and Department of Mathematics, Patras University, 26500 Patras, Greece Email: kavadias@cti.gr Grammati
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-1-001.ps.gz, 19950822 Computing a largest empty anchored cylinder, and related problems Frank Follert y Elmar Sch omer J urgen Sellen Michiel Smidz Christian Thielz
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-1-020.ps.Z, 19951011 Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms Shiva Chaudhuri Christos D. Zaroliagis MPI{I{95{1-020 August 1995 Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms Shiva Chaudhuri Christos D. Zaroliagis Max-Planck Institut f ur Informatik Im
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-1-005.ps.gz, 19951011 Self-Stabilization of Wait-Free Shared Memory Objects Jaap-Henk Hoepman1, Marina Papatriantafilou2;3, and Philippas Tsigas3 1 CWI, P.O. Box 94079, 1090 SB Amsterdam, The Netherlands. 2 CTI & CE and Informatics Dept., Patras University, Greece. 3 MPI f ur Informatik, Im Stadtwald, 66123 Saarbr ucken,
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-1-003.ps.gz, 19951011 Matching Nuts and Bolts Faster Phillip G. Bradford Rudolf Fleischer Max-Planck-Institut f ur Informatik, Im Stadtwald, 66123 Saarbr ucken, Germany. E-mail: fbradford,rudolfg@mpi-sb.mpg.de.
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-1-021.ps.Z, 19951011 Shortest Paths in Digraphs of Small Treewidth. Part II: Optimal Parallel Algorithms Shiva Chaudhuri Christos D. Zaroliagis MPI{I{95{1-021 August 1995 Shortest Paths in Digraphs of Small Treewidth. Part II: Optimal Parallel Algorithms Shiva Chaudhuri Christos D. Zaroliagis Max-Planck Institut f ur
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-149.ps.gz, 19951017 Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points O. Devillers INRIA Sophia-Antipolis France M. Goliny Hong Kong UST Hong Kong K. Kedemz Ben Gurion University Israel S. Schirrax Max-Planck-Institut f ur Informatik Germany
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-150.ps.gz, 19951017 On Characteristic Points and Approximate Decision Algorithms for the Minimum Hausdorff Distance L. Paul Chew Klara Kedemy Stefan Schirraz
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-1-027.ps.gz, 19951017 The Thickness of a Minor-Excluded Class of Graphs Michael J unger y Petra Mutzel z Thomas Odenthal y Mark Scharbrodt y
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-1-028.ps.gz, 19951017 ae Exact and Heuristic Algorithms for 2-Layer Straightline Crossing Minimization Michael J unger1* and Petra Mutzel2* 1 Institut f ur Informatik, Universit at zu K oln, Pohligstr. 1, D-50969 K oln, Germany 2 Max-Planck-Institut f ur Informatik, Im Stadtwald, D-66123 Saarbr ucken, Germany
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-2-010.ps.gz, 19951108 MAX-PLANCK-INSTITUT F UR INFORMATIK Special Cases and Substitutes for Rigid E-Unification David A. Plaisted MPI{I{95{2{010 November 1995 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Authors' Addresses Department of Computer Science CB# 3175, 352 Sitterson Hall University of
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-2-011.ps.gz, 19960105 Modelling Mixed-Integer Optimisation Problems in Constraint Logic Programming Peter Barth Alexander Bockmayr MPI{I{95{2{011 November 1995 Authors' Addresses Peter Barth, Alexander Bockmayr Max-Planck-Institut f ur Informatik, Im Stadtwald, D-66123 Saarbr ucken, Germany fbarth,bockmayrg@mpi-sb.mpg.de
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-92-101.ps.Z, 19960115 A Simple Balanced Search Tree With O(1) Worst-Case Update Time 1 by Rudolf Fleischer 2
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-92-125.ps.Z, 19960115 A New Lower Bound Technique for Decision Trees 1 by Rudolf Fleischer 2
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-2-001.ps.gz, 19960117 MAX-PLANCK-INSTITUT F UR INFORMATIK Theorem Proving in Cancellative Abelian Monoids Harald Ganzinger Uwe Waldmann MPI{I{96{2{001 January 1996 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Authors' Addresses Max-Planck-Institut f ur Informatik Im Stadtwald 66123 Saarbr ucken
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-2-003.ps.gz, 19960308 MAX-PLANCK-INSTITUT F UR INFORMATIK Using Algebraic Specification Languages for Model-Oriented Specifications Hubert Baumeister MPI{I{96{2-003 February 1996 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany i Author's Address Max-Planck-Institut f ur Informatik Im Stadtwald 66123
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-004.ps.gz, 19960308 Exact Ground States of Two-Dimensional J Ising Spin Glasses C. De Simone M. Diehl M. J unger P. Mutzel G. Reinelt G. Rinaldi
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-162.ps.gz, 19960308 On the Parallel Complexity of Degree Sequence Problems Srinivasa R. Arikati Max-Planck Institute f ur Informatik Im Stadtwald, D-66123 Saarbr ucken Germany arikati@mpi-sb.mpg.de Classification: Algorithms and data structures, Parallel algorithms.
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-155.ps.gz, 19960308 Lecture Notes Selected Topics in Data Structures (Ausgew ahlte Kapitel aus Datenstrukturen) Michiel Smid Max-Planck-Institut f ur Informatik D-66123 Saarbr ucken, Germany E-mail: michiel@mpi-sb.mpg.de January 15, 1996 Preface This text contains the lecture notes for the course Ausgew ahlte Kapitel aus
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-95-2-002.ps.gz, 19960416 MAX-PLANCK-INSTITUT F UR INFORMATIK Functional Translation and Second-Order Frame Properties of Modal Logics Revised Version Hans J urgen Ohlbach Renate A. Schmidt MPI{I{95{2{002 January 1995 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Authors' Addresses Max-Planck-Institut f
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-007.ps.gz, 19960416 All-Pairs Min-Cut in Sparse Networks Srinivasa R. Arikati Shiva Chaudhuri Christos D. Zaroliagis MPI{I{96{1-007 March 1996 All-Pairs Min-Cut in Sparse Networks Srinivasa R. Arikatiy Department of Mathematical Sciences University of Memphis, Memphis, TN 38152 E-mail: arikatis@next1.msci.memphis.edu Shiva
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-001.ps.gz, 19960416 The LEDA class real number Christoph Burnikel Kurt Mehlhorn Stefan Schirra January 24, 1996
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-002.ps.gz, 19960416 High-Precision Floating Point Numbers in LEDA Christoph Burnikel Jochen K onemann February 1, 1996 Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2. The Manual Page of data type bigfloat . . . . . . . . . . . . . . . . . . . . . . . 3 3.
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-009.ps.gz, 19960416 The Thickness of Graphs: A Survey Petra Mutzel Thomas Odenthal y Mark Scharbrodt z
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-008.ps.gz, 19960503 Efficient Algorithms for Counting and Reporting Pairwise Intersections between Convex Polygons Prosenjit Gupta y Ravi Janardanz Michiel Smidx April 17, 1996
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-115.ps.gz, 19960503 Efficient Construction of a Bounded Degree Spanner with Low Weight Sunil Arya Michiel Smid May 2, 1996
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-006.ps.gz, 19960503 On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees Gautam Dasy Sanjiv Kapoorz Michiel Smidx April 17, 1996
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-012.ps.gz, 19960715 A Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs Jesper L. Tr aff Christos D. Zaroliagis MPI{I{96{1-012 June 1996 A Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs Jesper L. Tr aff Christos D. Zaroliagis
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-020.ps.gz, 19960814 Negative Dependence Through the FKG Inequality Devdatt Dubhashi y BRICS Department of Computer Science University of Aarhus Ny Munkegade DK-8000 Aarhus C, Denmark dubhashi@daimi.aau.dk Volker Priebe Max-Planck-Institut f ur Informatik Im Stadtwald 66123 Saarbr ucken, Germany priebe@mpi-sb.mpg.de Desh
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-2-004.ps.gz, 19960814 MAX-PLANCK-INSTITUT F UR INFORMATIK Non-Symmetric Rewriting Georg Struth MPI{I{96{2{004 June 1996 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Authors' Addresses Max-Planck-Institut f ur Informatik Im Stadtwald D-66123 Saarbr ucken Germany E-Mail: struth@mpi-sb.mpg.de Phone: +49
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-013.ps.gz, 19960814 Research Report and Proposal Sanjeev Mahajan May 15, 1996 1 Semidefinite Programming Since September 1994 when I joined the Max Planck Institut as a post-doctoral fellow, I have been working at Semidefinite Programming and its applications to Approximation Problems. The techniques from Semidefinite
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-2-006.ps.gz, 19960814 MAX-PLANCK-INSTITUT F UR INFORMATIK Natural Deduction for Non-Classical Logics David Basin Se an Matthews Luca Vigan o MPI{I{96{2{006 August 1996 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany i ii Authors' Addresses David Basin, Se an Matthews, Luca Vigan o Max-Planck-Institut f
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-021.ps.gz, 19960814 Generalized k-Center Problems Shiva Chaudhuri Naveen Garg R. Raviy
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-2-002.ps.gz, 19960814 MAX-PLANCK-INSTITUT F UR INFORMATIK Labelled Propositional Modal Logics: Theory and Practice David Basin Se an Matthews Luca Vigan o MPI{I{96{2{002 February 1996 Oo Oo k I N F O R M A T I K Im Stadtwald D 66123 Saarbr ucken Germany Authors' Addresses David Basin, Se an Matthews, Luca Vigan o
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-014.ps.gz, 19960814 The Randomized Complexity of Maintaining the Minimum Gerth Stolting Brodal Shiva Chaudhuriy Jaikumar Radhakrishnanz May 14, 1996
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-019.ps.gz, 19960814 Rotations of Periodic Strings and Short Superstrings Dany Breslauer Tao Jiangy Zhigen Jiangz June 12, 1996
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-2-005.ps.gz, 19960814 Auxiliary Modal Operators and the Characterization of Modal Frames Andreas Nonnengart MPI{I{96{2{005 June 1996 i Author's Address Max-Planck-Institut f ur Informatik, Im Stadtwald, 66123 Saarbr ucken, Germany, Andreas.Nonnengart@mpi-sb.mpg.de http://www.mpi-sb.mpg.de/~nonnenga/ Publication Notes A
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-015.ps.gz, 19960814 Computational Molecular Biology Martin Vingron Deutsches Krebsforschungszentrum, Heidelberg Hans Peter Lenhof Max-Planck-Institut f ur Informatik, Saarbr ucken Petra Mutzel Max-Planck-Institut f ur Informatik, Saarbr ucken Contents 1. Books and Surveys 2. Sequence Alignment and Evolution 2.1 Pairwise
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-011.ps.gz, 19960821 The Impact of Timing on Linearizability in Counting Networks Marios Mavronicolas y Department of Computer Science University of Cyprus Nicosia, CY-1678 Cyprus mavronic@turing.cs.ucy.ac.cy Marina Papatriantafilou Max-Planck-Institut f ur Informatik Im Stadtwald D-66123 Saarbr ucken, Germany & CS Dept.,
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-96-1-010.ps.gz, 19960821 Distributed List Coloring: How to Dynamically Allocate Frequencies to Mobile Base Stations Naveen Gargy Marina Papatriantafilou Philippas Tsigas Max-Planck Institute f ur Informatik, Im Stadtwald, 66123 Saarbr ucken, Germany email: fnaveen\|ptrianta\|tsigasg@mpi-sb.mpg.de
	ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/biennial97.ps.Z, 19970604 INFORMATIK THIRD BIENNIAL REPORT March 1995 { April 1997 Contents I Overview 1 II The Algorithms and Complexity Group 5 1 Personnel 7 2 Executive Summary 9 3 Complexity and Lower Bounds 14 3.1 Deterministic Restrictions in Circuit Complexity . . . . . . . . . . . . . . . . . . . . 14 3.2 The Randomized