Iloczyny kartezjańskie grafów znajdują zastosowanie w informatyce,
chemii teoretycznej jak rownież w biologii. Typowymi przykładami
iloczynów są hiperkostki (potęgi ), grafy Hamminga (iloczyny grafów pełnych) oraz kraty (iloczyny scieżek). W latach 70. ubiegłego wieku
zaczęto zastanawiać się nad wielomianowym algorytmem rozpoznającym
produkt kartezjański. W 1985 roku Feigenbaum zaprezentowal algorytm o
zlozonosci
. Podczas referatu przedstawiony zostanie
algorytm W. Imricha i I. Peterina rozpoznający iloczyn kartezjański w
czasie liniowym (względem liczby krawędzi).
), grafy Hamminga (iloczyny grafów pełnych) oraz kraty (iloczyny scieżek). W latach 70. ubiegłego wieku
zaczęto zastanawiać się nad wielomianowym algorytmem rozpoznającym
produkt kartezjański. W 1985 roku Feigenbaum zaprezentowal algorytm o
zlozonosci
. Podczas referatu przedstawiony zostanie
algorytm W. Imricha i I. Peterina rozpoznający iloczyn kartezjański w
czasie liniowym (względem liczby krawędzi).