dr Marcin Jurkiewicz | Politechnika Gdańska

We present two greedy algorithms that determine zero-error codes and lower bounds on the zero-error capacity. These algorithms have many advantages, e.g., they do not store a whole product graph in a computer memory and they use the so-called distributions in all dimensions to get better approximations of the zero-error capacity. We also show an additional application of our algorithms.

The isolated scattering number is a parameter that measures the vulnerability of networks. This measure is bounded by formulas de- pending on the independence number. We present new bounds on the isolated scattering number that can be calculated in polynomial time.

The isolated scattering number is a parameter that measures the vulnerability of networks. This measure is bounded by formulas de- pending on the independence number. We present new bounds on the isolated scattering number that can be calculated in polynomial time.

We compare results of selected algorithms that approximate the independence number in terms of the quality of constructed solutions. Furthermore, we establish smallest hard- to-process graphs for the greedy algorithm MIN.

We present some characterizations of characteristic graphs of row and/or column symmetric channels. We also give a polynomial-time algorithm that decides whether there exists a discrete symmetric channel whose characteristic graph is equal to a given input graph. In addition, we show several applications of our results.