- Tytuł:
-
Algorithms for testing security in graphs
Algorytmy testujące bezpieczeństwo zbioru wierzchołków grafu - Autorzy:
-
Hiler, Arkadiusz
Lewoń, Robert
Małafiejski, Michał - Powiązania:
- https://bibliotekanauki.pl/articles/41205262.pdf
- Data publikacji:
- 2014
- Wydawca:
- Uniwersytet Kazimierza Wielkiego w Bydgoszczy
- Tematy:
-
property tester
pseudotester
secure set
security
coNP-completeness
testowanie własności
zbiór bezpieczny
bezpieczeństwo
coNP-zupełność - Opis:
-
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 induced small subgraphs G[S] being trees or graphs with a bounded degree (by 3 or 4). Our approach is a generalization of the concept of property testers known from the subject literature, but we applied our concepts to the coNP-complete problem.
W niniejszym artykule przedstawiamy metodę weryfikowania bezpieczeństwa zbioru w grafie, dającą wysokie prawdopodobieństwo poprawnej weryfikacji. Problemem jest określenie, czy dla danego grafu G oraz podzbioru S zbioru wierzchołków tego grafu zbiór S jest bezpieczny, to znaczy każdy jego podzbiór X spełnia warunek: |N[X] ∩ S| ≥ |N[X] \ S|, gdzie N[X] jest domkniętym sąsiedztwem zbioru X w grafie G. Zaprojektowaliśmy pseudotester o wielomianowej złożoności obliczeniowej dla decyzyjnego problemu bezpieczeństwa zbioru w grafie wykorzystując m.in. koncepcję symulowanego wyżarzania. Wykonaliśmy testy dla grafów, w których podgraf indukowany przez zbiór S jest drzewem lub grafem ograniczonego stopnia (przez 3 oraz 4). Z uwagi na coNP-zupełność problemu bezpieczeństwa zaproponowane przez nas podejście jest uogólnieniem koncepcji testowania własności znanej z literatury. - Źródło:
-
Studia i Materiały Informatyki Stosowanej; 2014, 14; 18-26
1689-6300 - Pojawia się w:
- Studia i Materiały Informatyki Stosowanej
- Dostawca treści:
- Biblioteka Nauki
Artykuł