Najprostsze reprezentacje wykresów wykorzystują macierze / listy przyległości, co oznacza, że każdy węzeł i krawędź są wyraźnie reprezentowane. Znaczenie ukrytych reprezentacji dla wykresów wykazujących silne prawidłowości od dawna zostało uznane. Na przykład Galperin i Wigderson (1983), Papadimitriou i Yannakakis ( Nota o zwięzłych reprezentacjach grafów , 1986) badali kwestię wykresów, których macierz przylegania jest reprezentowana przez formułę logiczną odpowiadającą, czy (i, j) jest krawędzią biorąc pod uwagę binarną reprezentację numerów węzłów i i j. Zgodnie z niektórymi często ograniczonymi ograniczeniami redukcji problemy P-zupełne dla jawnych wykresów stają się PSPACE-zupełne dla tej reprezentacji, problemy NP-zupełne stają się NEXPTIME-complete itp.
Naturalnym podejściem do takich regularnych wykresów jest reprezentowanie formuły logicznej przy użyciu ROBDD; trudność polega na tym, że klasyczne algorytmy mają tendencję do wyliczania węzłów jeden po drugim, co pociąga za sobą wykładniczy koszt takiej reprezentacji i dlatego należy go unikać. Opublikowano artykuły na temat rozwiązywania klasycznych problemów za pomocą takiej reprezentacji, np. Gentilini i in. ( Obliczanie silnie połączonych komponentów w liniowej liczbie kroków symbolicznych ), Woelfel ( Symboliczne sortowanie topologiczne z OBDD ).
Zastanawiam się, czy istnieje przegląd takich technik, ponieważ pogłębianie literatury w takim stanie techniki jest niewygodne ...
źródło