Wyniki wyszukiwania dla: GLOBAL EDGE ALLIANCE

• Global edge alliances in graphs

  Publikacja

  • R. Lewoń
  • A. Małafiejska
  • M. Małafiejski
  • K. Wereszko

  - DISCRETE APPLIED MATHEMATICS - Rok 2019

  In the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the...

  Pełny tekst do pobrania w portalu

• Tight bounds on global edge and complete alliances in trees

  Publikacja

  • K. Wereszko
  • R. Kozakiewicz
  • R. Lewoń
  • M. Małafiejski

  - Rok 2020

  In the talk the authors present some tight upper bounds on global edge alliance number and global complete alliance number of trees. Moreover, we present our NP-completeness results from [8] for global edge alliances and global complete alliances on subcubic bipartite graphs without pendant vertices. We discuss also polynomial time exact algorithms for finding the minimum global edge alliance on trees [7] and complete alliance...

  Pełny tekst do pobrania w serwisie zewnętrznym

• Global defensive secure structures

  Publikacja

  • M. Małafiejski
  • K. Wereszko

  - Rok 2022

  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...

  Pełny tekst do pobrania w serwisie zewnętrznym

• Modele i algorytmy dla grafowych struktur defensywnych

  Publikacja

  • R. Lewoń

  - Rok 2023

  W niniejszej pracy przeprowadzono analizę złożoności istnienia struktur defensywnych oraz równowag strategicznych w grafach. W przypadku struktur defensywnych badano modele koalicji defensywnych, zbiorów defensywnych i koalicji krawędziowych – każdy z nich w wersji globalnej, tj. z wymogiem dominacji całego grafu. W przypadku modeli równowagi strategicznej badano równowagę strategiczną koalicji defensywnych, równowagę strategiczną...

  Pełny tekst do pobrania w portalu

• Justyna Szostak dr inż.

  Osoby

  Instytut Fizyki i Informatyki Stosowanej

  I Gdańsk University of Technology: Chair of the Rector’s Internationalization Committee (October 2020 - Present) Erasmus + Coordinator for students and staff members, Faculty of Applied Physics and Mathematics (Mar 2017 - Present) Dean's Proxy for Internationalization, Faculty of Applied Physics and Mathematics (October 2020 - Present) Coordinator of the International Relations Office of the Faculty of Applied Physics and...

• Global defensive sets in graphs

  Publikacja

  • R. Lewoń
  • A. Małafiejska
  • M. Małafiejski

  - DISCRETE MATHEMATICS - Rok 2016

  In the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph G and a subset S of a vertex set of G, we define for every subset X of S the predicate SEC ( X ) = true if and only if | N [ X ] ∩ S | ≥ | N [ X ] \ S | holds, where N [ X ] is a closed neighbourhood of X in graph G. A set S is a defensive alliance if and only if for...

  Pełny tekst do pobrania w portalu

• Leading Edge

  Czasopisma

  ISSN: 1070-485X

• Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graphs

  Publikacja

  • M. Dettlaff
  • J. Raczek
  • I. G. Yero

  - Opuscula Mathematica - Rok 2016

  Given a graph G= (V, E), the subdivision of an edge e=uv∈E(G) means the substitution of the edge e by a vertex x and the new edges ux and xv. The domination subdivision number of a graph G is the minimum number of edges of G which must be subdivided (where each edge can be subdivided at most once) in order to increase the domination number. Also, the domination multisubdivision number of G is the minimum number of subdivisions...

  Pełny tekst do pobrania w portalu

• Optimal edge-coloring with edge rate constraints

  Publikacja

  • D. Dereniowski
  • W. Kubiak
  • B. Ries
  • Y. Zwols

  - NETWORKS - Rok 2013

  We consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not [Grötschel et al., Combinatorica (1981), 169–197], we show that several questions about the length of the sequence are computationally intractable....

  Pełny tekst do pobrania w serwisie zewnętrznym

• Edge-coloring of 3-uniform hypergraphs

  Publikacja

  • P. Obszarski
  • A. Jastrzębski

  - DISCRETE APPLIED MATHEMATICS - Rok 2016

  We consider edge-colorings of 3-uniform hypergraphs which is a natural generalization of the problem of edge-colorings of graphs. Various classes of hypergraphs are discussed and we make some initial steps to establish the border between polynomial and NP-complete cases. Unfortunately, the problem appears to be computationally difficult even for relatively simple classes of hypergraphs.

  Pełny tekst do pobrania w portalu