A textbook on parallel computing. Nowadays all optimization and big data processing techniques are performed using parallel processing (throwing parallelism away indicates a simple problem or no big data). This book introduces all three predominant approaches to parallel programming: multithreading programming for multicore architectures, message-passing programming for multiprocessor clusters and GPU programming.
There are computationally demanding problems that can be solved by k-clique search algorithms in auxiliary product graphs. The best clique search programs heavily rely upon good colorings. But obtaining a good coloring is a demanding task itself. We present some coloring schemes that exploit the property of the product graph itself and can be constructed with ease. There are indications that using these colorings some hard problems would become feasible.
This paper introduces a novel graph partitioning based on symmetries. It also demonstrates how this equivalence can be applied to speeding up a certain type of algorithms, i.e. backtracking algorithms. Since these algorithms are ubiquitous in hard optimization problems, we believe that the introduced equivalence can have a huge impact in practice. We also show how this equivalence can be efficiently computed on trees.
The paper describes a problem of unique and stable self-assembling mesh nanostructure made of short chains of molecules. Although the motivation comes from coiled-coil protein molecules, the results are applicable also to other molecules like DNA. Interactions between the individual chain links can be represented by an interaction matrix. The paper contains two main results: the number of different interaction matrices for a given set of chains and an algorithm for checking whether a set of chains specified by a given interaction matrix uniquely and stably self-assembles into a mesh structure. The experimental results show that no 2 different chains of length 4 yield such nanomesh.
The two input graphs, in which the maximum common subgraph is to be found, are multiplied to form a product graph, which is then input to the maximum clique algorithm. The maximum clique problem can be solved by a modern branch-and-bound based algorithm for general graphs but some special properties of the product graph can be exploited to form a specialized solver. Namely, we use the exploit the nature of the product graph to provide the maximum clique algorithm with a very good initial coloring or multiple such colorings. We perform experiments on a large database of small to medium sized graphs and demonstrate the efficiency of the proposed method against a state of the art method for solving maximum common subgraph problem.