Opis

• Tytuł:
  Algorithms for testing security in graphs
• Twórca:
  Hiler, Arkadiusz;
  Lewoń, Robert;
  Małafiejski, Michał
• Opis:
  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 in duced small subgraphs G[S] being trees or graphs with a bounded degree (by 3 or 4). Our approach is a generalization of the concept ofproperty testers known from the subject literature, but we applied our concepts to the coNP-complete problem.
• Dostępność obiektu:
  Dostęp otwarty
• Data:
  2016.04.12;
  2014
• Typ:
  Article
• Język:
  angielski;
  eng
• Format:
  application/pdf
• Wydawca:
  Fundacja Rozwoju Mechatroniki
• Temat i słowa kluczowe:
  property tester;
  pseudotester;
  secure set;
  security;
  coNP-completeness
• Identyfikator:
  Studia i Materiały Informatyki Stosowanej, 2014, T. 6, nr 14.;
  http://repozytorium.ukw.edu.pl/handle/item/3557
• Dostawca danych:
  Repozytorium Uniwersytetu Kazimierza Wielkiego w Bydgoszczy
• Czy mogę z tego obiektu skorzystać?:
  poproś o pozwolenie
• Rodzaj zawartości:
  obrazy