Wyszukiwarka
Abstrakt
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 on the heuristic using simulated annealing and tested it on graphs with induced small subgraphs G[S] being trees or graphs with bounded degree (by 3 or 4). Our approach is a generalization of the concept of property testers known from literature, but we applied our concepts to the coNP-complete problem.
Autorzy (3)
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- Licencja
-
otwiera się w nowej karcie
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:
-
Studia i Materiały Informatyki Stosowanej
strony 19 - 26,
ISSN: 1689-6300 - Język:
- polski
- Rok wydania:
- 2014
- Opis bibliograficzny:
- Hiler A., Lewoń R., Małafiejski M.: Algorithms for testing security in graphs// Studia i Materiały Informatyki Stosowanej. -., iss. 14 (2014), s.19-26
- Źródła finansowania:
-
- Publikacja bezkosztowa
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 117 razy