Grafy doskonałe metodą dziur nieparzystych w automatycznej syntezie sterowników

• Autorzy: Mielcarek K.

Warianty tytułu

EN

Perfect Graphs Using Odd-Hole Free Graph Properties In Automatic High Level Synthesis

• Języki publikacji: PL

Abstrakty

PL

Obserwowany rozwój elektroniki i wszechobecna miniaturyzacja, obja-wiającą się coraz większą ilością urządzeń realizujących coraz bardziej skomplikowane zadania. Rozwój pociąga za sobą konieczność opracowy-wania nowych, bardziej efektywnych metod panowania nad ogromem zależności. Złożoność układów dawno przerosła możliwości pojedynczej osoby i obecnie takimi zadaniami obciąża się specjalizowane systemy komputerowe, jednak tego typu system należy odpowiednio przygotować. Pożądane jest, aby dawał wyniki optymalne w jak najkrótszym czasie. Złożoność problemów występujących w czasie automatycznego przygotowania układów cyfrowych powoduje, że w praktyce stosowane są algorytmy heurystyczne, dające wyniki przybliżone i nie zawsze w najkrótszym możliwym czasie. Pogoń za nowymi rozwiązaniami doprowadziła do pomysłu wykorzystania grafów doskonałych, które przez swoje własności pozwalają zmniejszyć wymagania czasowe a zatem i wymaganą moc obliczeniową, dając w zamian wyniki optymalne. Algorytmy wykorzystujące specyficzne własności grafów doskonałych charakteryzują się złożonością obliczeniową na poziomie wielomianowym. Zanim można będzie operować na grafach doskonałych należy sprawdzić czy dany graf jest grafem doskonałym. Najnowsze prace wskazują, że grafy doskonałe można rozpoznawać (pośród innych metod) z użyciem algorytmów wyszukiwania dziur nieparzystych. Jednocześnie obserwuje się, że znacząca większość grafów opisujących rzeczywiste układy zawiera się w podklasach grafów doskonałych. W roku 1960, Claude Berge wysunął tezę mówiącą ze graf jest doskonały wtedy i tylko wtedy, gdy nie zawiera ani dziur nieparzystych ani anty-dziur nieparzystych. Teza jest znana jako Strong Perfect Graph Conjecture. (Chvátal i Sbihi zaproponowali nazwę grafu Bergea) wg propozycji Dziura natomiast, jest bezcięciwowym cyklem o długości przynajmniej cztery, zaś anty-dziura jest dopełnieniem takiego cyklu. Dziury i anty-dziury są natomiast parzyste i nieparzyste zgodnie z parzystością ich liczby wierzchołków. Nieparzysta dziura jak i nieparzysta anty-dziura nie są doskonałe, bowiem ich liczby klikowe wynoszą odpowiednio 2 oraz 2k+1 natomiast liczby chromatyczne mają odpowiednio 3 oraz k+1, co jednoznacznie uniemożliwia im być grafem doskonałym (liczba chromatyczna grafu doskonałego G, jest równa liczbie kliki grafu, dla każdego indukowanego podgrafu grafu G). Artykuł ma na celu wskazanie potencjalnej użyteczności algorytmów do rozpoznawania grafów doskonałych. Zagadnienia występujące w procesach automatycznej syntezy dają się rozwiązać w czasie wielomianowym, gdzie dla grafów w ogólności problem złożoności należy do klasy problemów NP-zupełnych. Zastosowanie grafów doskonałych jako pośredniego modelu formalnego jest o tyle użyteczne, że znacząca większość zależności, opisujących rzeczywiste układy sekwencyjne, daje w wyniku grafy nale-żące do podklasy grafów doskonałych [5].

EN

This paper should to point out potential strenght of prerfect graph algorithms - specially algorithms with use of odd-hole-free graph - for automated synthesis of digital circuits. Typically known problems are NP-complete but using perfect graphs complexity is decreasing to polynomial. Studies in this matter shows that plenty of dependencies describing real sequential circuits can be described using perfect graphs. There shown the analysis of digital controller described in SFC. In analysis was used methods for testing perfect graphs.

Słowa kluczowe

PL

grafy doskonałe; algorytmy rozpoznawania grafów doskonałych; teoria grafów; synteza sterowników automatyczna

EN

prefect graphs; odd-hole free graphs; prefect graphs recognizing algorithms; graph theory; automatic synthesis of digital controllers

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2007
• Tom: R. 53, nr 7
• Strony: 72--74
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Mielcarek K.

• Instytut Informatyki i Elektroniki, Uniwersytet Zielonogórski,

Bibliografia

• [1] Golumbic M. C.: Algorithmic Graph Theory and Perfect Graphs, Courant Institute of Mathematical Science, New York University, Academic Press 1980.
• [2] Lovasz L.: A Characterization of Perfect Graphs, Journal of Combinatorial Theory, Series B, vol. 13, 1972, pp. 95-98.
• [3] Comuejols G.: The Strong Perfect Graph Conjecture, International Congress of Mathematicians, Bejing, China, 2002.
• [4] Comuejols G.: The Strong Perfect Graph Theorem, Ann. of Math, 2006.
• [5] O. Coudert: Exact Coloring of Real-Life Graphs is Easy, Synopsys, Inc. 700 East Middlefield Rd., Moutain View, Proc. of the 34th Desia. Automation Conference DAC, Anaheim, CA, USA, 1997, pp. 121-126.
• [6] Comuejols G., Xining Liu, Vuskovic K.: A polynomial algorithm for recognizing perfect graphs, Proceeding 44th Annual IEEE Symposium, 2003.
• [7] Mielcarek K: Grafy doskonałe jako alternatywa dla automatycznej syntezy i optymalizacji układów cyfrowych, Metody i systemy komputerowe w badaniach naukowych i projektowaniu inżynierskim, IV Krajowa Konferencja. Kraków, Polska, 2003, Oprogramowanie Naukowo-Techniczne, 2003.
• [8] Mielcarek K: Rozpoznawanie grafów doskonałych na potrzeby automatycznej syntezy układów cyfrowych, KNWS`06, Pomiary Automatyka Kontrola 6bis/2006.
• [9] Giovani De Micheli: Synteza i optymalizacja układów cyfrowych, Wydawnictwa Naukowo-Techniczne, Warszawa 1998.
• [10] Leuker G. S., Interval graph algorithms. Ph. D. thesis, Princeton University.
• [11] Conforti M., Comuejols G., Kapoor A., Vuškovič K., Even-hole-freegraphs, Part II: Recognition algorithm, Journal of Graph Theory 40, 2002, pp. 238-266.
• [12] Cornuérnuéjols G., Cunnigham W.H.: Compositions for perfect graphs Discrete Mathematics 55, 1985, pp. 245-254.
• [13] Nikolopoulosy S. D., Paliosz L.: Hole and Antihole Detection in Graphs, Algorithmica, Springer Science + Busines Media Inc., 2007.
• [14] Chudnovsky M., Comurnuéjols G., Xining L., Seymour P., Vuškovič K.: Recognizing Berge Graphs, Princeton University, Carnegie Mellon Princeton University and Princeton, University of Leeds, 2002, revised 2004.
• [15] International Electrotechnical Commission: Programable controllers. Part 3 - Programing Languages IEC 1131-3, Genewa, 1993.
• [16] Adamski M.: Metodologia projektowania reprogramowalnych sterowników logicznych z wykorzystaniem elementów CPLD i FPGA, Reprogramowalne Układy Cyfrowe RUC 98, Szczecin, 1998, pp. 15-22.
• [17] Adamski M.: Aplication Specific logic Controler for Safety Critical Systems, IFAC Triennial Congress, Beijing Chiny, 1999, vol. 0, pp. 519-529.