@phdthesis{18972, author = {{Damerow, Valentina}}, isbn = {{3-939350-09-5}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Average and Smoothed Complexity of Geometric Structures}}}, volume = {{190}}, year = {{2006}}, } @inproceedings{18999, abstract = {{We present a web computing library (PUBWCL) in Java that allows to execute tightly coupled, massively parallel algorithms in the bulk-synchronous (BSP) style on PCs distributed over the internet whose owners are willing to donate their unused computation power. PUBWCL is realized as a peer-to-peer system and features migration and restoration of BSP processes executed on it. The use of Java guarantees a high level of security and makes PUBWCL platform- independent. In order to estimate the loss of efficiency inherent in such a Java-based system, we have compared it to our C-based PUB-Library. As the unused computation power of the participating PCs is unpredictable, we need novel strategies for load balancing that have no access to future changes of the computation power available for the application. We develop, analyze, and compare different load balancing strategies for PUBWCL. In order to handle the influence of the fluctuating available computation power, we classify the external work load. During our evaluation of the load balancing algorithms we simulated the external work load in order to have repeatable testing conditions. With the best performing load balancing strategy we could save 39% of the execution time on average and even up to 50% in particular cases, in our test environment. }}, author = {{Bonorden, Olaf and Meyer auf der Heide, Friedhelm and Gehweiler, Joachim}}, booktitle = {{Journal on Scalable Computing: Practice and Experience}}, pages = {{1--14}}, title = {{{A Web Computing Environment for Parallel Algorithms in Java}}}, year = {{2006}}, } @inproceedings{19001, abstract = {{We present a novel architecture for distributed computing in a peer-to-peer network. In particular, we realize the Paderborn University BSP-based Web Computing Library (PUBWCL), which formerly used a centralized client-server architecture for scheduling and load balancing, as a pure peer-to-peer system. Using distributed heterogeneous hash tables (DHHT), our architecture features scheduling and load balancing of tightly coupled, massively parallel algorithms in the bulk-synchronous (BSP) style with a minimal number of migrations. }}, author = {{Gehweiler, Joachim and Schomaker, Gunnar}}, booktitle = {{Proceeedings of 10th IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications (DS-RT)}}, isbn = {{0769526977}}, pages = {{51--58}}, title = {{{Distributed Load Balancing in Heterogeneous Peer-to-Peer Networks for Web Computing Libraries}}}, doi = {{10.1109/ds-rt.2006.15}}, year = {{2006}}, } @article{23881, abstract = {{Computing a maximum weighted stable set in a bipartite graph is considered well-solved and usually approached with preflow-push, Ford–Fulkerson or network simplex algorithms. We present a combinatorial algorithm for the problem that is not based on flows. Numerical tests suggest that this algorithm performs quite well in practice and is competitive with flow based algorithms especially in the case of dense graphs.}}, author = {{Faigle, Ulrich and Frahling, Gereon}}, issn = {{0166-218X}}, journal = {{Discrete Applied Mathematics}}, pages = {{1380--1391}}, title = {{{A combinatorial algorithm for weighted stable sets in bipartite graphs}}}, doi = {{10.1016/j.dam.2005.05.037}}, year = {{2006}}, } @inproceedings{23882, abstract = {{In this paper we develop an efficient implementation for a k-means clustering algorithm. Our algorithm is a variant of KMHybrid [28, 20], i.e. it uses a combination of Lloyd-steps and random swaps, but as a novel feature it uses coresets to speed up the algorithm. A coreset is a small weighted set of points that approximates the original point set with respect to the considered problem. The main strength of the algorithm is that it can quickly determine clusterings of the same point set for many values of k. This is necessary in many applications, since, typically, one does not know a good value for k in advance. Once we have clusterings for many different values of k we can determine a good choice of k using a quality measure of clusterings that is independent of k, for example the average silhouette coefficient. The average silhouette coefficient can be approximated using coresets.To evaluate the performance of our algorithm we compare it with algorithm KMHybrid [28] on typical 3D data sets for an image compression application and on artificially created instances. Our data sets consist of 300,000 to 4.9 million points. We show that our algorithm significantly outperforms KMHybrid on most of these input instances. Additionally, the quality of the solutions computed by our algorithm deviates less than that of KMHybrid.We also computed clusterings and approximate average silhouette coefficient for k=1,…,100 for our input instances and discuss the performance of our algorithm in detail.}}, author = {{Frahling, Gereon and Sohler, Christian}}, booktitle = {{Proceedings of the twenty-second annual symposium on Computational geometry - SCG '06}}, title = {{{A fast k-means implementation using coresets}}}, doi = {{10.1145/1137856.1137879}}, year = {{2006}}, } @inproceedings{2401, abstract = {{ This paper presents a novel method for optimal temporal partitioning of sequential circuits for time-multiplexed reconfigurable architectures. The method bases on slowdown and retiming and maximizes the circuit's performance during execution while restricting the size of the partitions to respect the resource constraints of the reconfigurable architecture. We provide a mixed integer linear program (MILP) formulation of the problem, which can be solved exactly. In contrast to related work, our approach optimizes performance directly, takes structural modifications of the circuit into account, and is extensible. We present the application of the new method to temporal partitioning for a coarse-grained reconfigurable architecture. }}, author = {{Plessl, Christian and Platzner, Marco and Thiele, Lothar}}, booktitle = {{Proc. Int. Conf. on Field Programmable Technology (ICFPT)}}, keywords = {{temporal partitioning, retiming, ILP}}, pages = {{345--348}}, publisher = {{IEEE Computer Society}}, title = {{{Optimal Temporal Partitioning based on Slowdown and Retiming}}}, doi = {{10.1109/FPT.2006.270344}}, year = {{2006}}, } @article{2043, author = {{Bagchi, Amitabha and Bhargava, Ankur and Chaudhary, Amitabh and Eppstein, David and Scheideler, Christian}}, journal = {{Theory Comput. Syst.}}, number = {{6}}, pages = {{903----928}}, title = {{{The Effect of Faults on Network Expansion}}}, doi = {{10.1007/s00224-006-1349-0}}, year = {{2006}}, } @misc{20436, author = {{Hamann, Heiko}}, title = {{{Modeling and Investigation of Robot Swarms}}}, year = {{2006}}, } @article{17979, author = {{Schindelhauer, Christian and Volbert, Klaus and Ziegler, Martin}}, issn = {{0925-7721}}, journal = {{Computational Geometry}}, pages = {{197--214}}, title = {{{Geometric spanners with applications in wireless networks}}}, doi = {{10.1016/j.comgeo.2006.02.001}}, year = {{2006}}, } @article{17985, author = {{Ziegler, Martin}}, issn = {{0885-064X}}, journal = {{Journal of Complexity}}, pages = {{827--849}}, title = {{{Effectively open real functions}}}, doi = {{10.1016/j.jco.2006.05.002}}, year = {{2006}}, } @inbook{17987, author = {{Meer, Klaus and Ziegler, Martin}}, booktitle = {{Logical Approaches to Computational Barriers}}, isbn = {{9783540354666}}, issn = {{0302-9743}}, title = {{{Uncomputability Below the Real Halting Problem}}}, doi = {{10.1007/11780342_39}}, year = {{2006}}, } @inproceedings{18351, abstract = {{In this paper the ideas of a new research project are presented. The material flow simu- lator d3FACT insight shall manage multiple parallel and time synchronous simulations to grand the power of real-time visualization in combination with statistical analysis. This research is issued to overcome the conflict of simulation run repetition for a good statistical basis and real-time immersive visualization. A side effect will be the reduc- tion of time needed for simulation experiments. The planned simulation tool has the feature of triggered cloning, i.e., the user can decide during runtime to clone a set of simulations after changing parameters to preserve the original system. The simulations will be aggregated by visualization and statistics. The rendering is planned to overlay several simulations using effects like inking and transparency. Simulation data will be aggregated with statistical functions and diagrams.}}, author = {{Dangelmaier, Wilhelm and Huber, Daniel and Laroque, Christoph and Aufenanger, Mark and Fischer, Matthias and Krokowski, Jens and Kortenjan, Michael}}, booktitle = {{Simulation and Visualization 2006 (SimViS)}}, pages = {{79--88}}, publisher = {{SCS European Publishing House}}, title = {{{d³FACT insight goes parallel - Aggregation of multiple simulations}}}, year = {{2006}}, } @article{18672, author = {{Sohler, Christian and Czumaj, Artur}}, journal = {{EATCS Bulletin}}, number = {{89}}, pages = {{23----47}}, title = {{{Sublinear-time Algorithms}}}, year = {{2006}}, } @inproceedings{2213, author = {{Scheideler, Christian}}, booktitle = {{6th International HNI Symposium on New Trends in Parallel and Distributed Computing}}, title = {{{Towards a paradigm for robust distributed algorithms and data structures}}}, year = {{2006}}, } @inproceedings{21777, author = {{Domik, Gitta and Goetz, Frank}}, booktitle = {{EG Education Papers}}, editor = {{Brown, Judy and Hansmann, Werner}}, pages = {{1--5}}, publisher = {{The Eurographics Association}}, title = {{{A Breadth-First Approach for Teaching Computer Graphics}}}, doi = {{10.2312/eged.20061001}}, year = {{2006}}, } @inproceedings{21778, author = {{Goetz, Frank and Domik, Gitta}}, booktitle = {{ACM SIGGRAPH 2006 Research Posters}}, isbn = {{1595933646}}, pages = {{51–es}}, publisher = {{Association for Computing Machinery}}, title = {{{Visual Shaditor: A Seamless Way to Compose High-Level Shader Programs}}}, doi = {{10.1145/1179622.1179681}}, year = {{2006}}, } @proceedings{7780, editor = {{Pleuß, Andreas and Van den Bergh, Jan and Hußmann, Heinrich and Sauer, Stefan and Bödcher, Alexander}}, publisher = {{CEUR-WS.org}}, title = {{{Proceedings of the Workshop on Model Driven Development of Advanced User Interfaces, satellite of the MoDELS 2006 conference}}}, volume = {{214}}, year = {{2006}}, } @inproceedings{7947, author = {{Loeser, Christoph and Schomaker, Gunnar and Schubert, Matthias and Schattkowsky, Tim}}, booktitle = {{Proceedings of the 5th International Conference on Networking (ICN 2006), Morne (Mauritius)}}, pages = {{105}}, publisher = {{IEEE Computer Society}}, title = {{{Fairness Considerations in Replication and Placement Strategies for large Documents in heterogeneous Content Delivery Networks}}}, doi = {{http://dx.doi.org/10.1109/ICNICONSMCL.2006.96}}, year = {{2006}}, } @inproceedings{7948, author = {{Schattkowsky, Tim and Förster, Alexander and Loeser, Christoph}}, booktitle = {{Proceedings of the 5th International Conference on Networking (ICN 2006), Morne (Mauritius)}}, pages = {{86}}, publisher = {{IEEE Computer Society}}, title = {{{Secure Storage for Physically Exposed Web- and Application Servers}}}, year = {{2006}}, } @inproceedings{7949, author = {{Schattkowsky, Tim and Hendrik Hausmann, Jan and Engels, Gregor}}, booktitle = {{Proceedings of the International Conference on Model Driven Engineering Languages and Systems (MoDELS 2006), Genova (Italy)}}, pages = {{737--752}}, publisher = {{Springer}}, title = {{{Using UML Activities for System-on-Chip Design and Synthesis}}}, doi = {{dx.doi.org/10.1007/11880240_51}}, volume = {{4199/2006}}, year = {{2006}}, }