Fixed-Parameter Algorithms for Cluster Vertex Deletion

We initiate the first systematic study of the NP-hard Cluster Vertex Deletion (CVD) problem (unweighted and weighted) in terms of fixed-parameter algorithmics. In the unweighted case, one searches for a minimum number of vertex deletions to transform a graph into a collection of disjoint cliques. The parameter is the number of vertex deletions. We present efficient fixed-parameter algorithms for CVD applying the fairly new iterative compression technique. Moreover, we study the variant of CVD where the maximum number of cliques to be generated is prespecified. Here, we exploit connections to fixed-parameter algorithms for (weighted) Vertex Cover.     

A geometric data structure for parallel finite elements and the application to multigrid methods with block smoothing

We present a data structure for parallel computing which is directly linked to geometric quantities of an underlying mesh and which is well adapted to the requirements of a general finite element realization. In addition, we define an abstract linear algebra model which supports multigrid methods (extending our previous work in Comp. Vis. Sci. 1 (1997), 27–40). Finally, we apply the parallel multigrid preconditioner to several configurations in linear elasticity and we compute the condition number numerically for different smoothers, resulting in a quantitative evaluation of parallel multigrid performance.     

Rechtliche Fragen zur Praxis IT-forensischer Analysen in Organisationen

Der Einsatz von Informationstechnologie (IT) in Organisationen bietet viele M?glichkeiten des Missbrauchs. Besch?ftigte k?nnen sich die besonderen Eigenschaften der IT zunutze machen, um sich etwa in gesch?ftssch?digender Weise Vorteile zu verschaffen. Gleichzeitig erm?glicht IT aber auch, verbotene Handlungen aufzuspüren und zu belegen (IT-Forensik). Der Beitrag beschreibt die technische Praxis von IT-forensischen Analysen und geht auf damit verbundene rechtliche Fragestellungen ein.     

Experimental investigation and thermodynamic assessment of the Cu-Sn-Ti ternary system

The Cu-Sn-Ti ternary system has been studied via experiments and thermodynamic modelling. In the experimental section, the composition of the alloys was selected based on the preliminary calculations and available literature data. Metallography, scanning electron microscopy and electron probe microanalysis were employed to analyse alloy samples prepared by arc-melting after annealing at 800 °C for 760 h. Solid phase relations at 800 °C were established. In contrast to earlier reports, the CuSn₃Ti₅ phase was interpreted as a binary intermetallic compound (Sn₃Ti₅) with extended Cu solubility. In the modelling section, three binary sub-systems were critically evaluated and updated according to the new experimental data and theoretical calculations reported in literature. According to their crystal structures and homogeneity ranges, appropriate sublattice models were proposed for SnTi₃,SnTi₂,Sn₃Ti₅ and Sn₅Ti₆. A set of self-consistent thermodynamic parameters for the Cu-Sn-Ti ternary system was obtained by considering the present experimental results and reported experimental information. The calculated results compare with the available experimental data to validate the present thermodynamic assessment.     

An Evaluation of an OS-Based Coherence Scheme for Tiled CMPs

The interconnect mechanisms (shared bus or crossbar) used in current chip-multiprocessors (CMPs) are expected to become a bottleneck that prevents these architectures from scaling to a larger number of cores. Tiled CMPs offer better scalability by integrating relatively simple cores with a lightweight point-to-point interconnect. However, such interconnects make snooping impractical and, thus, require alternative solutions to cache coherence. In this article, we investigate a novel, cost-effective mechanism to support shared-memory parallel applications that forgoes hardware maintained cache coherence. This mechanism is based on the key ideas that mapping of lines to physical caches is done at the page level with OS support and that hardware supports remote cache accesses. We extend our previous work by investigating in detail the impact of system design parameters and extending the system to support multi-level cache hierarchies. Results show that the choice of implementation of multi-level cache hierarchies can have a significant impact on performance.     

IEEE 802.21: Media independence beyond handover

The IEEE 802.21 standard facilitates media independent handovers by providing higher layer mobility management functions with common service primitives for all technologies. Right after the base specification was published, several voices rose up in the working group advocating to broaden the scope of IEEE 802.21 beyond handovers. This paper aims at updating the reader with the main challenges and functionalities required to create a Media Independence Service Layer, through the analysis of scenarios which are being discussed within the working group: 1) Wireless Coexistence, and 2) Heterogeneous Wireless Multihop Backhaul Networks.     

A trick for computing expected values in high-dimensional probabilistic models

Sensory stimuli are generally encoded by the activity of thousands of neurons in parallel. Coding theories dealing with such high-dimensional representations face hard numerical problems. One of them is the computation of expected values according to the underlying probability distributions. Direct computations are generally avoided also because of the high numerical precision required. Here, a numerical trick is described that overcomes the problem of numerical precision, thereby providing a simple alternative to indirect methods based on stochastic sampling (Monte-Carlo methods).     

Symmetric active/active metadata service for high availability parallel file systems

High availability data storage systems are critical for many applications as research and business become more data driven. Since metadata management is essential to system availability, multiple metadata services are used to improve the availability of distributed storage systems. Past research has focused on the active/standby model, where each active service has at least one redundant idle backup. However, interruption of service and even some loss of service state may occur during a fail-over depending on the replication technique used. In addition, the replication overhead for multiple metadata services can be very high. The research in this paper targets the symmetric active/active replication model, which uses multiple redundant service nodes running in virtual synchrony. In this model, service node failures do not cause a fail-over to a backup and there is no disruption of service or loss of service state. A fast delivery protocol is further discussed to reduce the latency of the total order broadcast needed. The prototype implementation shows that metadata service high availability can be achieved with an acceptable performance trade-off using the symmetric active/active metadata service solution.