Wyniki wyszukiwania dla: property tester

• Graph security testing

  Publikacja

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

  - Journal of Applied Computer Science - Rok 2015

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

  Pełny tekst do pobrania w serwisie zewnętrznym

• Algorithms for testing security in graphs

  Publikacja

  • A. Hiler
  • R. Lewoń
  • M. Małafiejski

  - Studia i Materiały Informatyki Stosowanej - Rok 2014

  In this paper we propose new algorithmic methods giving with the 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] \cap S| >= |N[X] \ S|, where N[X] is a closed neighbourhood of X in graph G. We constructed a polynomial time property pseudotester based...

  Pełny tekst do pobrania w portalu