Search
Abstract
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.
Authors (3)
Cite as
Full text
- Publication version
- Accepted or Published Version
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Published in:
-
Studia i Materiały Informatyki Stosowanej
pages 19 - 26,
ISSN: 1689-6300 - Language:
- Polish
- Publication year:
- 2014
- Bibliographic description:
- 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
- Sources of funding:
-
- Free publication
- Verified by:
- Gdańsk University of Technology
seen 117 times