Product Graph Invariants with Applications in the Theory of Information

Marcin Jurkiewicz; Marek Kubale

Product Graph Invariants with Applications in the Theory of Information

Abstrakt

There are a large number of graph invariants. In the paper, we consider some of them, e.g. the independence and chromatic numbers. It is well know that we cannot efficiently calculate these numbers for arbitrary graphs. In the paper we present relations between these invariants and concepts from the theory of information. Concepts such as source coding and transmission over a noisy channel with zero probability of error are modeled using graph theoretical structures and are measured by the independence and chromatic numbers of some products of graphs, i.e. graphs arise from other graphs. It turns out that for some classes of product graphs, there exist algorithms and methods for determining these invariants. Using optimization algorithms together with some theoretical results we can establish some values and bounds on previously mentioned invariants of product graphs.

Autorzy (2)

Marcin Jurkiewicz
Marek Kubale prof. dr hab. inż.

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Aktywność konferencyjna
Typ:: publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Tytuł wydania:: 5th International Interdisciplinary Technical Conference of Young Scientists InterTech 2012 : proceedings, Poznań, Poland, 16-18 May 2012 strony 253 - 255
Język:: angielski
Rok wydania:: 2012
Opis bibliograficzny:: Jurkiewicz M., Kubale M.: Product Graph Invariants with Applications in the Theory of Information// 5th International Interdisciplinary Technical Conference of Young Scientists InterTech 2012 : proceedings, Poznań, Poland, 16-18 May 2012/ Poznań: Politechnika Poznańska, 2012, s.253-255
Weryfikacja:: Politechnika Gdańska