Wyszukiwarka
Abstrakt
Set S ⊂ V is called secure set iff ∀ X ⊂ S | N [ X ] ∩ S | ≥ | N ( X ) \ S | [3]. That means that every subset of a secure set has at least as many friends (neighbour vertices in S) as enemies (neighbour vertices outside S) and will be defended in case of attack. Problem of determining if given set is secure is co −NP -complete, there is no efficient algorithm solving it [3]. Property testers are algorithms that distinguish inputs with a given property from those that are far from satisfying the property [6]. Property testers are allowed to be probabilistic and approximate in exchange for much reduced complexity. In our work we apply the idea of testing to construct probabilistic and approximate algorithms for graph security problems that run in polynomial time. Our goal was to formalize the testing model and propose various approaches for security testing and general methods of rating them. We take into account possibilities of practical application, algorithm complexity and quality of the approximation.
Autorzy (3)
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Opublikowano w:
-
Journal of Applied Computer Science
nr 23,
strony 29 - 45,
ISSN: 1507-0360 - Język:
- angielski
- Rok wydania:
- 2015
- Opis bibliograficzny:
- Gieniusz T., Lewoń R., Małafiejski M.: Graph security testing// Journal of Applied Computer Science. -Vol. 23., nr. 1 (2015), s.29-45
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 84 razy
Publikacje, które mogą cię zainteresować
Device-independent quantum key distribution based on measurement inputs
- R. Rahaman,
- M. Parker,
- P. A. Mironowicz
- + 1 autorów