Global defensive secure structures - Publikacja - MOST Wiedzy

Wyszukiwarka

Global defensive secure structures

Abstrakt

Let S ⊂ V (G) for a given simple non-empty graph G. We define for any nonempty subset X of S the predicate SECG,S(X) = true iff |NG[X]∩S| ≥ |NG[X]\S|. Let H be a non-empty family of graphs such that for each vertex v ∈ V (G) there is a subgraph H of G containing v and isomorphic to a member of H. We introduce the concept of H-alliance extending the concept of global defensive secure structures. By an H-alliance in a graph G we mean a set S ⊂ V (G) such that (1) each vertex v ∈ S belongs to a subgraph H of G that is isomorphic to a member of H, and (2) for each H ⊂ G[S] isomorphic to a member of H, SECG,S(V (H)) = true. If S is also a dominating set of G, we call it a global H-alliance of G. If H = {K1}, then such an H-alliance we call a defensive alliance (GA) [1] or a vertex alliance. If H = {K2}, then such an H-alliance we call an edge alliance [2]. In the case of H is a class of all complete graphs (i.e., K1, K2, . . .), then an H-alliance we call a complete alliance [3]. If H = {K1, . . . , Kk}, then an H-alliance we call k-complete alliance. In this talk we present general properties of global defensive secure structures (i.e., H-alliances), algorithms for H-alliance problems (exact and approximation ones), and we provide new N P-complete results for global defensive secure structures for bounded degree graphs. We formulate also H-alliance problem in some special cases as ILP problem and study a few algorithmic approaches.

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Aktywność konferencyjna
Typ:
publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Język:
angielski
Rok wydania:
2022
Opis bibliograficzny:
Małafiejski M., Wereszko K.: Global defensive secure structures// / : , 2022,
Weryfikacja:
Politechnika Gdańska

wyświetlono 72 razy

Publikacje, które mogą cię zainteresować

Meta Tagi