Supercomputing for Industry www.it4i.cz

Methods od Discrete Mathematics

The development of discrete mathematics is marked by the boom of computers in the second half of the last century. The well known problems include the shortest path problem, maximal flows in networks, traveling salesman problem, scheduling or optimization of traffic lights.

The main problem lies not only in designing some algorithm to solve the problem, but mostly in the designing an algorithm that can solve the problem fast. Though the shortest path problem between two nodes and the traveling salesman problem seem very closely related, there is a major difference in the complexity of their solution. While the former can be solved in linear time with respect to the number of edges (roads in a network), the latter belongs to the family of NP complete problems. No algorithm with polynomial (especially not with linear) complexity is known! Since problems that can be solved using methods of discrete mathematics are often an essential part of IT, one has to choose suitable methods and formulate his problems in such a way that the complexity of the solution does not grow over a reasonable bound.

One of the optimization problems that have an elegant formulation and solution using discrete mathematics is the balance of computation load as well as data amount distributed among the nodes of a parallel machine. Using graph theory (decompositions of complete graphs) and number theory, we succeeded in designing such distribution in which not only the computational load is balanced but, moreover, the distribution of data fragments enables each fragment to be used only by one core during the entire computation. In such way the memory of each core can be exploited maximally, and tasks can be solved that are larger than in any other possible distribution.

This distribution is in a sense perfect and for certain number of – nodes N cannot be improved any more. Nowadays we are involved in the search for an optimal distribution for additional – values N.

Fair incomplete tournaments

Various systems are employed in sport tournament scheduling.
In those systems unique number is assigned to teams or players. Depend on the system this number could be random or could take into account their strength in comparison to others. Then, the schedule can influence the difficulty of tournaments for particular teams which is not necessarily fair.

We can design such schedules that are in a sense equally fair to each team in a tournament. Such schemes are modeled using graph theory in which the difficulty is expressed using labels and weights in graphs. We focus on designing fair schemes as well as their generalizations that will make tournaments more challenging for strong teams and easier for weaker teams. Such schedules can be interesting for general audience since one can expect balanced games throughout the entire season.

Factorizations of complete graphs

Since 1980 the factorization of complete graphs into isomorphic spanning trees has been studied intensely. While for complete bipartite graphs the problem is solved completely, for complete graphs a complete solution is beyond reach. Mathematicians succeeded in the classification of certain classes of trees and have shown a number of surprising results that account for the overall difficulty of a general answer.

Surprisingly, it is easier to answer factorization problems for “larger graphs” while for “small graphs” one usually relies on computer brute force search. But the complexity grows exponentially with the size of a given graph, which makes the computation extremely source demanding despite many clever enhancements. We develop and continually improve parallel software that can find decompositions and factorizations of complete graphs into isomorphic subgraphs.