Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: zbiór bezpieczny

Sortuj według:

Ogranicz wyniki do:

Graph security testing

Gieniusz T., Lewoń R., Małafiejski M.

Journal of Applied Computer Science

2015

Vol. 23, nr 1

29--45

In this paper we consider probabilistic approach to the decision problem of security in graphs. In this purpose we define general model (called property tester) and criteria for approximating answers for decision problems. We constructed two property testers and one heuristics for the problem of security in graphs.

Algorithms for testing security in graphs

Hiler Arkadiusz, Lewoń Robert, Małafiejski Michał

Studia i Materiały Informatyki Stosowanej

2014

nr 14

18--26

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.