@inproceedings{2425, abstract = {{ We present instance-specific custom computing machines for the set covering problem. Four accelerator architectures are developed that implement branch \& bound in 3-valued logic and many of the deduction techniques found in software solvers. We use set covering benchmarks from two-level logic minimization and Steiner triple systems to derive and discuss experimental results. The resulting raw speedups are in the order of four magnitudes on average. Finally, we propose a hybrid solver architecture that combines the raw speed of instance-specific reconfigurable hardware with flexible bounding schemes implemented in software. }}, author = {{Plessl, Christian and Platzner, Marco}}, booktitle = {{Proc. Int. Symp. on Field-Programmable Custom Computing Machines (FCCM)}}, pages = {{163--172}}, publisher = {{IEEE Computer Society}}, title = {{{Custom Computing Machines for the Set Covering Problem}}}, doi = {{10.1109/FPGA.2002.1106671}}, year = {{2002}}, } @article{24336, abstract = {{We define here a distributed abstract state machine (DASM) [7] of the network or routing layer of mobile ad hoc networks [13]. Such networks re- quire routing strategies substantially different from those used in static commu- nication networks, since storing and updating large routing tables at mobile hosts would congest the network with administration packets very fast. In [1], the hypercubic location service is presented, which considers a very strong definition of fault-tolerance thereby improving state-of-the-art ad hoc routing protocols in several respects. Our goal in modeling the protocols for the distrib- uted location service and the position based routing is twofold. First, we support the definition and validation of wireless communication protocols and imple- mentations based thereon. Second, we feel that the abstract computation model naturally reflects the layering principle of communication architectures in com- bination with an uncompromisingly local view of the application domain. Thus we can identify fundamental semantic concepts, such as concurrency, reactivity and asynchronism, directly with the related concepts as imposed by the given application context. }}, author = {{ Benczúr, András and Glässer, Uwe and Lukovszki, Tamás}}, journal = {{Proc. of 10th International Workshop on Abstract State Machines, LNCS}}, title = {{{Formal Description of a Distributed Location Service for Mobile Ad Hoc Networks}}}, year = {{2002}}, } @inproceedings{24338, author = {{Grünewald, Matthias and Lukovszki, Tamás and Schindelhauer, Christian and Volbert, Klaus}}, booktitle = {{Proceedings of the 8th International Euro-Par Conference}}, issn = {{0302-9743}}, title = {{{Distributed Maintenance of Resource Efficient Wireless Network Topologies}}}, doi = {{10.1007/3-540-45706-2_134}}, year = {{2002}}, } @inproceedings{26412, author = {{Volbert, Klaus}}, booktitle = {{Proceedings 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing}}, title = {{{A simulation environment for ad hoc networks using sector subdivision}}}, doi = {{10.1109/empdp.2002.994324}}, year = {{2002}}, } @article{3241, author = {{Wehrheim, Heike}}, journal = {{Nord. J. Comput.}}, number = {{4}}, pages = {{405----435}}, title = {{{Relating State-based and Behaviour-oriented Subtyping}}}, year = {{2002}}, } @inproceedings{3242, author = {{Olderog, Ernst-Rüdiger and Wehrheim, Heike}}, booktitle = {{Formal Methods for Components and Objects, First International Symposium, {FMCO} 2002, Leiden, The Netherlands, November 5-8, 2002, Revised Lectures}}, editor = {{S. de Boer, Frank and M. Bonsangue, Marcello and Graf, Susanne and P. de Roever, Willem}}, pages = {{361----379}}, title = {{{Specification and Inheritance in {CSP-OZ}}}}, doi = {{10.1007/978-3-540-39656-7_15}}, year = {{2002}}, } @inproceedings{3243, author = {{Wehrheim, Heike}}, booktitle = {{Formal Methods for Open Object-Based Distributed Systems V, {IFIP} {TC6/WG6.1} Fifth International Conference on Formal Methods for Open Object-Based Distributed Systems {(FMOODS} 2002), March 20-22, 2002, Enschede, The Netherlands}}, editor = {{Jacobs, Bart and Rensink, Arend}}, pages = {{79----93}}, title = {{{Checking Behavioural Subtypes via Refinement}}}, year = {{2002}}, } @article{3034, author = {{Albanese, Andres and Blömer, Johannes and Edmonds, Jeff and Luby, Michael and Sudan, Madhu}}, issn = {{0018-9448}}, journal = {{IEEE Transactions on Information Theory}}, number = {{6}}, pages = {{1737--1744}}, publisher = {{Institute of Electrical and Electronics Engineers (IEEE)}}, title = {{{Priority encoding transmission}}}, doi = {{10.1109/18.556670}}, volume = {{42}}, year = {{2002}}, } @inproceedings{3040, author = {{Albanese, A. and Blömer, Johannes and Edmonds, J. and Luby, M. and Sudan, M.}}, booktitle = {{Proceedings 35th Annual Symposium on Foundations of Computer Science}}, isbn = {{0818665807}}, publisher = {{IEEE Comput. Soc. Press}}, title = {{{Priority encoding transmission}}}, doi = {{10.1109/sfcs.1994.365731}}, year = {{2002}}, } @article{2134, author = {{Feige, Uriel and Scheideler, Christian}}, journal = {{Combinatorica}}, number = {{3}}, pages = {{361----399}}, title = {{{Improved Bounds for Acyclic Job Shop Scheduling}}}, doi = {{10.1007/s004930200018}}, year = {{2002}}, } @inproceedings{2135, author = {{Kolman, Petr and Scheideler, Christian}}, booktitle = {{SODA}}, pages = {{184----193}}, publisher = {{ACM/SIAM}}, title = {{{Improved bounds for the unsplittable flow problem}}}, year = {{2002}}, } @inproceedings{2136, author = {{Brinkmann, André and Salzwedel, Kay and Scheideler, Christian}}, booktitle = {{SPAA}}, pages = {{53----62}}, title = {{{Compact, adaptive placement schemes for non-uniform requirements}}}, year = {{2002}}, } @inproceedings{2137, author = {{Bagchi, Amitabha and Chaudhary, Amitabh and Scheideler, Christian and Kolman, Petr}}, booktitle = {{SPAA}}, pages = {{265----274}}, title = {{{Algorithms for fault-tolerant routing in circuit switched networks}}}, year = {{2002}}, } @inproceedings{2138, author = {{Scheideler, Christian}}, booktitle = {{STACS}}, pages = {{27----49}}, publisher = {{Springer}}, title = {{{Models and Techniques for Communication in Dynamic Networks}}}, volume = {{2285}}, year = {{2002}}, } @article{18853, author = {{Sohler, Christian and Czumaj, Artur}}, journal = {{Proceedings of the 43th Symposium on Foundations of Computer Science (FOCS)}}, pages = {{83--92}}, title = {{{Abstract Combinatorial Programs and Efficient Property Testers}}}, year = {{2002}}, } @techreport{18961, author = {{Lukovszki, Tamás and Benczúr, A.}}, title = {{{A Degree O(log log n) Fault Tolerant Distributed Location Service for Geographic Ad-Hoc Routing}}}, year = {{2002}}, } @inproceedings{1921, author = {{Ngo-Quynh, Thu and Karl, Holger and Wolisz, Adam and Rebensburg, Klaus}}, booktitle = {{Proc. IST Mobile & Wireless Telecommunications Summit 2002.}}, title = {{{New Scheduling Algorithm for Providing Proportional Jitter in Differentiated Service Network }}}, year = {{2002}}, } @phdthesis{18169, abstract = {{Die Implementierung von Algorithmen zur Lösung geometrischer Probleme im Euklidischen Raum (z.B. Berechnung der konvexen Hülle oder des Durchschnitts zweier Polyeder) stellt sich oftmals als hochgradig nichttrivial heraus. Ob und unter welchen Voraussetzungen die verursachenden numerischen Instabilitäten überhaupt ini den Griff zu kriegen oder vielmehr dem Problem inhärent sind, untersucht diese Arbeit in einem auf Turing zurückgehenden Rechenmodell. Im Gegensatz zu algebraischen Ansätzen geht jenes nicht von der Verfügbarkeit exakter Tests auf z.B. Gleichheit reeller Zahlen aus, sondern berücksichtigt die auf Digitalcomputern tatsächlich realisierbare Approximation durch rationale Zahlen. In diesem Rahmen werden beweisbar stabile Algorithmen zum Lösen linearer Gleichungssysteme, zur Matrix-Diagonalisierung und zur linearen wie nichtlinearen Optimierung präsentiert. Als wichtiges technisches Hilfsmittel dient ein neuer Berechenbarkeitsbegriff für reguläre unendliche Mengen reller Zahlen, der sich aus dem systematischen Vergleich verschiedener der Literatur entnommener ad-hoc Ansätze ergibt.}}, author = {{Ziegler, Martin}}, isbn = {{3-935433-24-7}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Zur Berechenbarkeit reeller geometrischer Probleme}}}, volume = {{115}}, year = {{2002}}, } @article{18176, author = {{Ziegler, Martin}}, issn = {{0942-5616}}, journal = {{Mathematical Logic Quarterly (MLQ)}}, number = {{S1}}, pages = {{157--181}}, title = {{{Computability on Regular Subsets of Euclidean Space}}}, doi = {{10.1002/1521-3870(200210)48:1+<157::aid-malq157>3.0.co;2-4}}, volume = {{48}}, year = {{2002}}, } @inproceedings{18177, abstract = {{Consider the classical point location problem: for a fixed arrangement of m hyperplanes and its induced partition of d-space report, upon input of some point, which face it lies in. With sufficient memory, this is easy to solve in logarithmic time O(log m). But how fast can algorithms (formalized as Linear Decision Trees) of *minimum* size be? The present work gives lower and upper bounds for the time complexity of point location under this constraint. They show that, in addition to m, the maximum number w of walls of a cell turns out to be a crucial parameter. We also consider a relaxation of the strict minimum-size condition allowing for constant factor overhead.}}, author = {{Ziegler, Martin and Damerow, Valentina and Finschi, Lukas}}, booktitle = {{Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02)}}, title = {{{Point Location Algorithms of Minimum Size}}}, year = {{2002}}, }