SOFSEM
SOFSEM 2005
31st Annual Conference on Current Trends in
Theory and Practice of Informatics
January 22 - 28, 2005
Hotel MAJ, Liptovsky Jan,
Slovak Republic, Europe


Hans Bodlaender: Discovering Treewidth

Abstract: Treewidth is a graph parameter with several interesting theoretical and practical applications. This survey reviews algorithmic results on determining the treewidth of a given graph, and finding a tree decomposition of small width. Both theoretical results, establishing the asymptotic computational complexity of the problem, as experimental work on heuristics (both for upper bounds as for lower bounds), preprocessing, exact algorithms, and postprocessing are discussed.
Emmanuel Cecchet: From research prototypes to industrial strength open source products - The ObjectWeb experience

Abstract: Open source software has become a common way of disseminating research results. In this talk, we first introduce the motivations and implications of releasing research prototypes as open source software (OSS). ObjectWeb is an international consortium fostering the development of open source middleware. We give an overview of tools available for OSS development and management based on ObjectWeb experiences. The infrastructure required for hosting such developments is also described. We report various experiences and practices of small and large ObjectWeb projects in their way to reach the quality of industrial strength products. Finally, we summarize the lessons learned from the success and failures of these projects.
Faith Fich: How Hard is it to Take a Snapshot?

Abstract: The snapshot object is an important and well-studied primitive in distributed computing. This paper will present some implementations of snapshots from registers, in both asycnhronous and synchronous systems, and discuss known lower bounds on the time and space complexity of this problem.
Maurizio Lenzerini: Logical foundations for data integration

Abstract: Integrating heterogeneous data sources, which are distributed over highly dynamic computer networks, is one of the crucial challenges at the current evolutionary stage of Information Technology infrastructures. Large enterprises, business organizations, e-government systems, and, in short, any kind of internetworking community, need today an integrated and virtualized access to distributed information resources, which grow in number, kind, and complexity.

Several papers published in the last decades point out the need for a formal approach to data integration. Most of them, however, refer to an architecture based on a global schema and a set of sources. The sources contain the real data, while the global schema provides a reconciled, integrated, and virtual view of the underlying sources. As observed in several contexts, this centralized achitecture is not the best choice for supporting data integration, cooperation and coordination in highly dynamic computer networks. A more appealing architecture is the one based on peer-to-peer systems. In these systems every peer acts as both client and server, and provides part of the overall information available from a distributed environment, without relying on a single global view.

In this talk, we review the work done for rigorously defining centralized data integration systems, and then we focus on peer-to-peer data integration, with the aim of singling out the principles that should form the basis for data integration in this architecture. Particular emphasis is given to the problem of assigning formal semantics to peer-to-peer data integration systems. We discuss two different methods for defining such a semantics, and we compare them with respect to the above mentioned principles.


Walter Didimo: Spine and Radial Drawings of Graphs

Abstract: Graph drawing is devoted to the design of models and algorithms for the visualization of graphs, with the purpose of computing pleasant and readable drawings. This is typically done by taking into account the optimization of important aesthetic requirements, like for example the number of edge crossings, the number of bends on edges, and the area of the drawing.

Among the wide set of graph drawing conventions, layered drawings have a long tradition; they require that the vertices of the graph are placed on geometric "layers". Spine and radial drawings of graphs are layered drawings such that the layers are parallel straight lines and concentric circles, respectively. They are relevant both in traditional and in emerging application fields, which include computer and social networks analysis, cybergeography, software engineering, and bioinformatics.

In this talk recent advances on crossing-free spine and radial drawings of graphs are presented, and the relationships between the number of layers and the number of bends in these drawings are discussed. From the investigation of these relationships, several intriguing theoretical and practical open problems arise.


Hans-Jörg Schek: The Hyperdatabase Network ­ New Middleware for Searching and Maintaining the Information Space

Abstract: The hyperdatabase network, a project at ETH Zurich since 1998, is a new middleware for the information space and includes new multi-object multi-feature search facilities for multimedia objects. It applies database technology at the level of services and combines peer-to-peer, grid, and service-oriented architectures.
Thomas Seidmann: Architecture of a Business Framework for the .NET Platform and Open Source Environments

Abstract: This paper contains a description of the architecture and components of a software framework for building enterprise style applications based on the .NET platform. The process and achieved results of porting this business framework to an open source platform based on GNU/Linux/Mono is described as well.
Laszlo Szekely: Progress on Crossing Number Problems

Abstract: Crossing numbers have drawn much attention in the last couple of years and several surveys and bibliographies have been published. The present survey tries to give pointers to some of the most significant recent developments and identifies computational challenges.


Department of Computer Science, Faculty of Mathematics, Physics, and Informatics, Comenius University, Bratislava
All rights reserved. © 2004, 2005