Wyniki wyszukiwania - BazTech

1

A Generalization of Join and an Algorithmic Recognition Problem

Shalu M. A., Yamini S. D.

Fundamenta Informaticae

|

2016

|

Vol. 145, nr 1

81--91

EN

We consider a new graph operation c2-join which generalizes join and co-join. We show that odd hole-free graphs (odd antihole-free graphs) are closed under c2-join and describe a polynomial time algorithm to recognize graphs that admit a c2-join. The time complexity of the (a) recognition problem, (b) maximum weight independent set (MWIS) problem, and (c) minimum coloring (MC) problem for odd hole-free graphs are still unknown. Let H be an odd hole-free graph that contains an odd antihole as an induced subgraph and GH be the class of all graphs generated from the induced subgraphs of H by using c2-join recursively. Then GH is odd hole-free, contains all P4-free graphs, complement of all bipartite graphs, and some imperfect graphs. We show that the MWIS problem, maximum weight clique (MWC) problem, MC problem, and minimum clique cover (MCC) problem can be solved efficiently for GH.

2

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

Mielcarek K.

Pomiary Automatyka Kontrola

|

2007

|

R. 53, nr 5

84-86

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.

3

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

Mielcarek K.

Pomiary Automatyka Kontrola

|

2007

|

R. 53, nr 7

72-74

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.