Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "odd hole-free graphs" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-3 z 3
    Tytuł:
    One-Three Join: A Graph Operation and Its Consequences
    Autorzy:
    Shalu, M.A.
    Devi Yamini, S.
    Powiązania:
    https://bibliotekanauki.pl/articles/31341697.pdf
    Data publikacji:
    2017-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    one-three join
    bipartite-join
    homogeneous set
    odd hole-free graphs
    Opis:
    In this paper, we introduce a graph operation, namely one-three join. We show that the graph G admits a one-three join if and only if either G is one of the basic graphs (bipartite, complement of bipartite, split graph) or G admits a constrained homogeneous set or a bipartite-join or a join. Next, we define ℳH as the class of all graphs generated from the induced subgraphs of an odd hole-free graph H that contains an odd anti-hole as an induced subgraph by using one-three join and co-join recursively and show that the maximum independent set problem, the maximum clique problem, the minimum coloring problem, and the minimum clique cover problem can be solved efficiently for ℳH.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 3; 633-647
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Wyszukiwanie dziur nieparzystych jako jeden z aspektów rozpoznania grafów doskonałych w automatycznej syntezie układów cyfrowych
    Recognizing odd-hole free graphs for testing perfect graphs for automatic synthesis of digital circuits
    Autorzy:
    Mielcarek, K.
    Powiązania:
    https://bibliotekanauki.pl/articles/152900.pdf
    Data publikacji:
    2007
    Wydawca:
    Stowarzyszenie Inżynierów i Techników Mechaników Polskich
    Tematy:
    algorytmy rozpoznawania grafów doskonałych
    teoria grafów
    automatyczna synteza sterowników
    prefect graphs
    odd-hole free graphs
    prefect graphs recognizing algorithms
    Opis:
    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).
    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.
    Źródło:
    Pomiary Automatyka Kontrola; 2007, R. 53, nr 5, 5; 84-86
    0032-4140
    Pojawia się w:
    Pomiary Automatyka Kontrola
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Grafy doskonałe metodą dziur nieparzystych w automatycznej syntezie sterowników
    Perfect Graphs Using Odd-Hole Free Graph Properties In Automatic High Level Synthesis
    Autorzy:
    Mielcarek, K.
    Powiązania:
    https://bibliotekanauki.pl/articles/155619.pdf
    Data publikacji:
    2007
    Wydawca:
    Stowarzyszenie Inżynierów i Techników Mechaników Polskich
    Tematy:
    grafy doskonałe
    algorytmy rozpoznawania grafów doskonałych
    teoria grafów
    automatyczna synteza sterowników
    prefect graphs
    odd-hole free graphs
    prefect graphs recognizing algorithms
    graph theory
    automatic synthesis of digital controllers
    Opis:
    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].
    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.
    Źródło:
    Pomiary Automatyka Kontrola; 2007, R. 53, nr 7, 7; 72-74
    0032-4140
    Pojawia się w:
    Pomiary Automatyka Kontrola
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-3 z 3

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies