@inproceedings{18655, abstract = {{We study graph properties which are testable for bounded degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and graphs that are far from every graph having that property. It is believed that almost all, even very simple graph properties require a large complexity to be tested for arbitrary (bounded degree) graphs. Therefore in this paper we focus our attention on testing graph properties for special classes of graphs. We call a graph family non-expanding if every graph in this family is not a weak expander (its expansion is O(1/log2 n), where n is the graph size). A graph family is hereditary if it is closed under vertex removal. Similarly, a graph property is hereditary if it is closed under vertex removal. Next, we call a graph property Π to be testable for a graph family F if for every graph G ε F, in time independent of the size of G we can distinguish between the case when G satisfies property Π and when it is far from every graph satisfying property Π. In this paper we prove thatIn the bounded degree graph model, any hereditary property is testable if the input graph belongs to a hereditary and non-expanding family of graphs.As an application, our result implies that, for example, any hereditary property (e.g., k-colorability, H-freeness, etc.) is testable in the bounded degree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. No such results have been known before and prior to our work, in the bounded degree graph model very few graph properties have been known to be testable for any graph classes.}}, author = {{Sohler, Christian and Czumaj, Artur}}, booktitle = {{Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA'07)}}, isbn = {{9780898716245}}, pages = {{494--501}}, title = {{{On Testable Properties in Bounded Degree Graphs}}}, year = {{2007}}, } @inproceedings{18656, abstract = {{In the StrSort model [2], the input is given as a stream, e.g. a sequence of points, and an algorithm can perform (a) streaming and (b) sorting passes to process the stream. A streaming pass reads the input stream from left to right and writes an output stream, which is the input of the next pass. A sorting pass is a black box operation that sorts a stream according to some partial order. In this paper, we develop algorithms for two basic geometric problems in the StrSort model. At first, we propose a divide-and-conquer algorithm that computes the convex hull of a point set in 2D in O(log2 n) passes using O(1) memory. Then we give a StrSort algorithm to compute a (1+ε)-spanner for a point set in Rd for constant d and constant epsilon that uses O(logd-1 n) passes and O(log n) space. This result implies a (1+ε)-approximation of the Euclidean minimum spanning tree in Rd, for constant d and ε.}}, author = {{Sohler, Christian and Lammersen, Christiane}}, booktitle = {{Proceedings of the 23rd European Workshop on Computational Geometry (EWCG)}}, pages = {{69--72}}, title = {{{StrSort Algorithms for Geometric Problems}}}, year = {{2007}}, } @inproceedings{18660, author = {{Sohler, Christian and Czumaj, Artur}}, booktitle = {{Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS)}}, pages = {{570 -- 578}}, title = {{{Testing Expansion in Bounded-Degree Graphs}}}, year = {{2007}}, } @inproceedings{18662, author = {{Sohler, Christian and Czumaj, Artur}}, booktitle = {{Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS'07)}}, pages = {{536--548}}, title = {{{Small Space Representations for Metric Min-Sum k-Clustering and their Applications}}}, year = {{2007}}, } @article{18665, abstract = {{We present a novel analysis of a random sampling approach for four clustering problems in metric spaces: k-median, k-means, min-sum k-clustering, and balanced k-median. For all these problems, we consider the following simple sampling scheme: select a small sample set of input points uniformly at random and then run some approximation algorithm on this sample set to compute an approximation of the best possible clustering of this set. Our main technical contribution is a significantly strengthened analysis of the approximation guarantee by this scheme for the clustering problems.The main motivation behind our analyses was to design sublinear-time algorithms for clustering problems. Our second contribution is the development of new approximation algorithms for the aforementioned clustering problems. Using our random sampling approach, we obtain for these problems the first time approximation algorithms that have running time independent of the input size, and depending on k and the diameter of the metric space only. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007A preliminary extended abstract of this work appeared in Proceedings of the 31st Annual International Colloquium on Automata, Languages and Programming (ICALP), pp. 396407, 2004.}}, author = {{Sohler, Christian and Czumaj, Artur}}, journal = {{Random Structures & Algorithms}}, number = {{1-2}}, pages = {{226 ---- 256}}, title = {{{Sublinear-time approximation algorithms for clustering via random sampling}}}, volume = {{30}}, year = {{2007}}, } @inproceedings{18668, author = {{Sohler, Christian and Monemizahdeh, Morteza and Feldman, Dan}}, booktitle = {{Proceedings of the 23rd annual symposium on computational geometry (SoCG'07)}}, pages = {{11--18}}, title = {{{A PTAS for k-means clustering based on weak coresets}}}, year = {{2007}}, } @inproceedings{18669, author = {{Sohler, Christian and Czumaj, Artur and Frahling, Gereon}}, booktitle = {{Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG)}}, pages = {{157--160}}, title = {{{Efficient kinetic data structures for MaxCut}}}, year = {{2007}}, } @inproceedings{2214, abstract = {{We present a randomized block-level storage virtualization for arbitrary heterogeneous storage systems that can distribute data in a fair and redundant way and can adapt this distribution in an efficient way as storage devices enter or leave the system. More precisely, our virtualization strategies can distribute a set of data blocks among a set of storage devices of arbitrary non-uniform capacities so that a storage device representing x% of the capacity in the system will get x% of the data (as long as this is in principle possible) and the different copies of each data block are stored so that no two copies of a data block are located in the same device. Achieving these two properties is not easy, and no virtualization strategy has been presented so far that has been formally shown to satisfy fairness and redundancy while being time- and space-eflcient and allowing an efficient adaptation to a changing set of devices.}}, author = {{Brinkmann, André and Effert, Sascha and Meyer auf der Heide, Friedhelm and Scheideler, Christian}}, booktitle = {{IEEE International Conference on Distributed Computing Systems (ICDCS)}}, title = {{{Dynamic and redundant data placement}}}, year = {{2007}}, } @inproceedings{21776, author = {{Krevert, B. and Dang, T. B. and Weise, R. and Fricke, H. and Domik, Gitta and Buchert, W.}}, booktitle = {{45. Jahrestagung der DGN}}, title = {{{Ein plattformunabhängiges Softwaretool für die schnelle Qualitätskontrolle von Transmissions- und dynamischen Emissionsdaten in der PET}}}, year = {{2007}}, } @article{2209, author = {{Aggarwal, Vinay and Feldmann, Anja and Scheideler, Christian}}, journal = {{ACM Computer Commucation Review}}, title = {{{Can ISPs and P2P users cooperate for improved performance?}}}, doi = {{10.1145/1273445.1273449}}, year = {{2007}}, } @proceedings{7778, editor = {{Engels, Gregor and Opdyke, B. and C. Schmidt, D. and Weil, F.}}, publisher = {{Springer}}, title = {{{Proceedings of the 10th International Conference on Model Driven Engineering Languages and Systems (MoDELS 2007), Nashville, TN (USA)}}}, doi = {{http://dx.doi.org/10.1007/978-3-540-75209-7}}, volume = {{4735}}, year = {{2007}}, } @proceedings{7779, editor = {{Pleuß, Andreas and Van den Bergh, Jan and Hußmann, Heinrich and Sauer, Stefan and Görlich, Daniel}}, publisher = {{University of Aachen}}, title = {{{Proceedings of the MoDELS 2007 Workshop on Model Driven Development of Advanced User Interfaces (MDDAUI '07), Nashville, Tennessee (USA)}}}, volume = {{297}}, year = {{2007}}, } @inproceedings{7958, author = {{Schattkowsky, Tim and Engels, Gregor and Förster, Alexander}}, booktitle = {{Proceedings of the 40th Annual Hawaii International Conference on System Sciences (HICSS 2007)}}, pages = {{286ff.}}, publisher = {{IEEE Computer Society}}, title = {{{A Model-Based Approach for Platform-Independent Binary Components with Precise Timing and Fine-Grained Concurrency}}}, doi = {{http://doi.ieeecomputersociety.org/10.1109/HICSS.2007.22}}, year = {{2007}}, } @inproceedings{7960, author = {{Küster, Jochen and Ryndina, Ksenia and Gall, Harald}}, booktitle = {{Proceedings of the conference on Business Process Management (BPM 2007), Brisbane (Australia)}}, pages = {{165--181}}, publisher = {{Springer}}, title = {{{Generation of Business Process Models for Object Life Cycle Compliance}}}, doi = {{https://groups.uni-paderborn.de/fg-engels/Publications/dx.doi.org/10.1007/978-3-540-75183-0_13}}, volume = {{4714}}, year = {{2007}}, } @inproceedings{7961, author = {{Pleuß, Andreas and Van den Bergh, Jan and Sauer, Stefan and Hußmann, Heinrich and Bödcher, Alexander}}, booktitle = {{MoDELS 2006 Workshops}}, pages = {{101--105}}, publisher = {{Springer}}, title = {{{Model Driven Development of Advanced User Interfaces (MDDAUI) - MDDAUI'06 Workshop Report}}}, doi = {{http://dx.doi.org/10.1007/978-3-540-69489-2_13}}, volume = {{4364}}, year = {{2007}}, } @inproceedings{7962, abstract = {{GUI builder tools are widely used in practice to develop the user interface of software systems. Typically they are visual programming tools that support direct-manipulative assembling of the user interface components. We have developed the tool GuiBuilder which follows a model-driven approach to the development of graphical (multimedia) user interfaces. This allows a meta-design approach where user interface developers as well as prospective users of the system are supported in modelling the desired functionality of the GUI on a high level of abstraction that is easy to understand for all involved stakeholders. The model consists of compositional presentation diagrams to model the structure of the user interface and hierarchical statechart diagrams to model its behaviour. GuiBuilder then supports the transformation of the model to Java, i.e., the generation of a working user interface and the simulation of the modelled behaviour. Interactive sessions with the user interface can be recorded and replayed.}}, author = {{Sauer, Stefan and Engels, Gregor}}, booktitle = {{Proceeding of the 4th International Conference on Universal Access in Human-Computer Interaction (UAHCI, as Part of HCI International, 2007), Beijing (China)}}, pages = {{537--546}}, publisher = {{Springer}}, title = {{{Easy Model-Driven Development of Multimedia User Interfaces with GuiBuilder}}}, doi = {{http://dx.doi.org/10.1007/978-3-540-73279-2_60}}, volume = {{4554}}, year = {{2007}}, } @inproceedings{7963, author = {{Bals, Jan-Christopher and Christ, Fabian and Engels, Gregor and Erwig, Martin}}, booktitle = {{Proceedings of the TOOLS Europe Conference (TOOLS 2007), Zürich (Swiss)}}, number = {{9}}, pages = {{383--398}}, publisher = {{Journal of Object Technology}}, title = {{{ClassSheets - model-based, object-oriented design of spreadsheet applications}}}, doi = {{http://www.jot.fm/issues/issue_2007_10/paper19/index.html}}, volume = {{6}}, year = {{2007}}, } @inproceedings{7964, author = {{Mlynarski, Michael and Hinkelmann, Knut and Magenheim, Johannes and Nelkner, Tobias and Reinhardt, Wolfgang and Holzweissig, Kai}}, booktitle = {{Creating New Learning Experiences on a Global Scale, Second European Conference on Technology Enhanced Learning, EC-TEL 2007, Crete, Greece, September 17-20, 2007}}, pages = {{487--492}}, publisher = {{Springer}}, title = {{{KnowledgeBus - An Architecture to Support Intelligent and Flexible Knowledge Management}}}, year = {{2007}}, } @inproceedings{7965, author = {{Förster, Alexander and Engels, Gregor and Schattkowsky, Tim and Van Der Straeten, Ragnhild}}, booktitle = {{Proceedings of the First Joint IEEE/IFIP Symposium on Theoretical Aspects of Software Engineering (TASE 2007), Shanghai (China)}}, pages = {{197--208}}, publisher = {{IEEE Computer Society}}, title = {{{Verification of Business Process Quality Constraints Based on Visual Process Patterns}}}, doi = {{http://dx.doi.org/10.1109/TASE.2007.56}}, year = {{2007}}, } @inproceedings{7966, author = {{Hess, Andreas and Humm, Bernhard and Voß, Markus and Engels, Gregor}}, booktitle = {{Proceedings of the 11th IEEE International Enterprise Distributed Object Computing Conference (EDOC 2007)}}, pages = {{122--129}}, publisher = {{IEEE Computer Society}}, title = {{{Structuring Software Cities - A Multidimensional Approach}}}, year = {{2007}}, }