Repozytorium Uniwersytetu Kazimierza Wielkiego w Bydgoszczy
    • Zaloguj
    Zobacz pozycję 
    •   Strona główna
    • Czasopisma naukowe
    • Studia i Materiały Informatyki Stosowanej
    • Studia i Materiały Informatyki Stosowanej, 2014, Tom 6, Numer 14
    • Zobacz pozycję
    •   Strona główna
    • Czasopisma naukowe
    • Studia i Materiały Informatyki Stosowanej
    • Studia i Materiały Informatyki Stosowanej, 2014, Tom 6, Numer 14
    • Zobacz pozycję
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Algorithms for testing security in graphs

    Thumbnail
    Oglądaj/Otwórz
    Algorithms for testing security in graphs.pdf (251.4KB)
    Data
    2014
    Autor
    Hiler, Arkadiusz
    Lewoń, Robert
    Małafiejski, Michał
    Metadata
    Pokaż pełny rekord
    Streszczenie
    In this paper we propose new algorithmic methods giving with a high probability the correct answer to the decision problem of security in graphs. For a given graph G and a subset S of a vertex set of G we have to decide whether S is secure, i.e. every subset X of S fulfils the condition: |N[X] S| |N[X] \ S|, where N[X] is a closed neighbourhood of X in graph G. We constructed a polynomial time property pseudotester based on the heuristic using simulated annealing and tested it on graphs with in duced small subgraphs G[S] being trees or graphs with a bounded degree (by 3 or 4). Our approach is a generalization of the concept ofproperty testers known from the subject literature, but we applied our concepts to the coNP-complete problem.
    URI
    http://repozytorium.ukw.edu.pl/handle/item/3557
    Collections
    • Studia i Materiały Informatyki Stosowanej, 2014, Tom 6, Numer 14 [2]

    Biblioteka Uniwersytetu Kazimierza Wielkiego
    Kontakt z nami | Wyślij uwagi | Deklaracja dostępności
    Biblioteka Uniwersytetu Kazimierza Wielkiego
    ul. Karola Szymanowskiego 3
    85-074 Bydgoszcz
     

     

    Przeglądaj

    Całe repozytoriumZbiory i kolekcje Daty wydaniaAutorzyTytułyTematyTa kolekcjaDaty wydaniaAutorzyTytułyTematy

    Moje konto

    ZalogujZarejestruj

    Statystyki

    Przejrzyj statystyki użycia

    Informacje

    Deklaracja dostępnościZasady udostępnianiaAspekty prawneJak dodać publikacjęSprawdź politykę wydawcy

    Biblioteka Uniwersytetu Kazimierza Wielkiego
    Kontakt z nami | Wyślij uwagi | Deklaracja dostępności
    Biblioteka Uniwersytetu Kazimierza Wielkiego
    ul. Karola Szymanowskiego 3
    85-074 Bydgoszcz