Repozytorium publikacji - Politechnika Gdańska

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

• Arkadiusz Hiler link otwiera się w nowej karcie ,
• dr inż. Robert Lewoń link otwiera się w nowej karcie ,
• dr hab. inż. Michał Małafiejski link otwiera się w nowej karcie