Wyszukiwanie dziur nieparzystych jako jeden z aspektów rozpoznania grafów doskonałych w automatycznej syntezie układów cyfrowych

• Autorzy: Mielcarek K.

Warianty tytułu

EN

Recognizing odd-hole free graphs for testing perfect graphs for automatic synthesis of digital circuits

• Języki publikacji: PL

Abstrakty

PL

Obserwujemy gwałtowny rozwój elektroniki i wszechobecną miniaturyzację, objawiającą się coraz większą ilością urządzeń realizujących coraz bardziej skomplikowane zadania. Ten rozwój pociąga za sobą konieczność opracowywania nowych, bardziej efektywnych metod panowania nad takim ogromem zależności. 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. 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).

EN

This paper should to point out potential strenght of prerfect graph algorithms - especially 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 show that plenty of dependencies describing real-life sequential circuits can be described using perfect graphs. There shown simplified methods to recognize perfect graphs, placed basic knowledge about the subject and shown simplified analysis of digital controller described in SFC. In this analysis some methods for recognizing perfect graphs was used.

Słowa kluczowe

PL

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

EN

prefect graphs; odd-hole free graphs; prefect graphs recognizing algorithms

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

Twórcy

autor

Mielcarek K.

• Instytut Informatyki i Elektroniki, Uniwersytet Zielonogórski,

Bibliografia

• [1] Conforti M., Comuejols G., Kapoor A., Virglcovre K., „Even-hole-free-graphs, Part II: Recognition algorithm", Journal of Graph Theory 40 (2002) 238-266.
• [2] Comuejols G., „The Strong Perfect Graph Conjecture".
• [3] Comuejols G., „The Strong Perfect Graph TheMem".
• [4] Comuejols G., Cunnigham W.H., „Compositions for perfect graphs", Discrete Mathematics 55 (1985) 245-254.
• [5] Comuejols G., Xinming L., Virgkovie K., "A polynomial algorithm for recognizing perfect graphs", Proceeding 44th Annual IEEE Symposium, 2003.
• [6] Coudert 0., „Exact Coloring of Real-Life Graphs is Easy", Synopsys, Inc. 700 East Middlefield Rd., Moutain View, CA 94043, Proc. of th 34th Design Automation Conference DAC„ Anaheim, CA, USA, June 1997, pp. 121-126.
• [7] Giovani De Micheli: „Synteza i optymalizacja układów cyfrowych", Wydawnictwa Naukowo-Techniczne, Warszawa 1998.
• [8] Golumbic M. C., „Algorithmic Graph Theory and Perfect Graphs", Courant Institute of Mathematical Science, New York University, Academic Press 1980.
• [9] Leuker G. S., "Interval graph algorithms. Ph. D. thesis", Princeton University.
• [10] Lovasz L., „A Characterization of Perfect Graphs", Journal of Combinatorial Theory (1972).
• [11] Mielcarek K, „Grafy doskonałe jako altenatywa 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.
• [12] Mielcarek Kamil, " Rozpoznawanie grafłw doskonałych na potrzeby automatycznej syntezy układów cyfrowych", KNWS'06, Pomiary Automatyka Kontrola 6bis/2006.
• [13] Nikolopoulosy S. D., Paliosz L., "Hole and Antihole Detection in Graphs"
• [14] International Electrotechnical Commission, "Programable controllers. Part 3 – Programing Languages IEC 1131-3", Genewa, 1993.
• [15] Chudnovsky M., Comuéjols G., Xinming L., Seymour P., Vuškovič K., "Cleaning for Bergeness", 2002.
• [16] Chudnovsky M., Comuéjols G., Xinming L., Seymour P., Vuškovič K., „ Recognizing Berge Graphs", 2002.
• [17] Comuéjols G., Cunnigham W.H., "Compositions for perfect graphs", Discrete Mathematics 55 (1985) 245-254.