Skip to content ↓

Grafy dowolnie podzielne

Badanie dowolnie podzielnych grafów (a dokładniej mówiąc - drzew) zostało zapoczątkowane niezależnie przez dwa zespoły odpowiadające zbiorom autorów dwóch pierwszych prac na ten temat:

  • D.Barth, O.Baudon and J.Puech, Decomposable trees: a polynomial algorithm for tripodes, Discrete Appl. Math. 119 (2002), 205-216.
  • M. Horňák, M. Woźniak, Arbitrarily vertex decomposable trees are of maximum degree at most six, Opuscula Mathematica 23 (2003), 49-62.

Motywacją grupy francuskiej (z LRI w Orsay) były zagadnienia podziału dużej sieci komputerowej na części i przydziału ich niezalełnym użytkownikom. Grupa słowacko-polska (z UJPS w Koszycach i AGH) chciała przenieść rozważania odnośnie dowolnego podziału zbioru krawędzi grafu na przypadek zbioru wierzchołków.

Przegląd wyników do roku 2008 zawiera np. referat przeglądowy [wygłoszony jako wykład plenarny na II Polskiej Konferencji Kombinatorycznej (2nd Polish Combinatorial Conference, 2PCC) w Będlewie w 2008 roku.]

Stopka