Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Czasopismo
Rocznik
Tom
Strony
29--45
Opis fizyczny
Bibliogr. 6 poz.
Twórcy
autor
- Gdańsk University of Technology, Poland, Department of Algorithms and System Modeling, ul. Gabriela Narutowicza 11/12, 80-233 Gdańsk Wrzeszcz
autor
- Gdańsk University of Technology, Poland, Department of Algorithms and System Modeling, ul. Gabriela Narutowicza 11/12, 80-233 Gdańsk Wrzeszcz
autor
- Gdańsk University of Technology, Poland, Department of Algorithms and System Modeling, ul. Gabriela Narutowicza 11/12, 80-233 Gdańsk Wrzeszcz
Bibliografia
- [1] Dutton, R., Secure set algorithms and complexity, In: Proceedings of the Thirty-Seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing, Vol. 180, 2006, pp. 115–121.
- [2] Raskhodnikova, S., Property Testing: Theory and Applications, Ph.D. thesis, Massachusetts Institute of Technology, 2003.
- [3] Goldreich, O., Goldwasser, S., and Ron, D., Property testing and its connection to learning and approximation, Journal of the ACM (JACM), Vol. 45, No. 4, 1998, pp. 653–750.
- [4] Blukis, T., Zbiory bezpieczne w grafach, Master’s thesis, Politechnika Gdańska, 2012.
- [5] Brigham, R., Dutton, R., and Hedetniemi, S., Security in graphs, Discrete applied mathematics, Vol. 155, No. 13, 2007, pp. 1708–1714.
- [6] Dutton, R. D., Lee, R., and Brigham, R. C., Bounds on a graph’s security number, Discrete Appl. Math., Vol. 156, No. 5, March 2008, pp. 695–704.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-9e323242-4290-40bc-a6d1-d648196ce19b