Graph security testing

• Autorzy: Gieniusz T. , Lewoń R. , Małafiejski M.
• Języki publikacji: EN

Abstrakty

EN

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

EN

secure set; property testing

PL

zbiór bezpieczny; badanie właściwości

• Wydawca: Wydawnictwo Politechniki Łódzkiej
• Czasopismo: Journal of Applied Computer Science
• Rocznik: 2015
• Tom: Vol. 23, nr 1
• Strony: 29--45
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Gieniusz T.

• Gdańsk University of Technology, Poland, Department of Algorithms and System Modeling, ul. Gabriela Narutowicza 11/12, 80-233 Gdańsk Wrzeszcz

autor

Lewoń R.

• Gdańsk University of Technology, Poland, Department of Algorithms and System Modeling, ul. Gabriela Narutowicza 11/12, 80-233 Gdańsk Wrzeszcz

autor

Małafiejski M.

• 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.