Rok 2022

• On zero-error codes produced by greedy algorithms

  Publikacja

  • M. Jurkiewicz

  - JOURNAL OF COMBINATORIAL OPTIMIZATION - Rok 2022

  We present two greedy algorithms that determine zero-error codes and lower bounds on the zero-error capacity. These algorithms have many advantages, e.g., they do not store a whole product graph in a computer memory and they use the so-called distributions in all dimensions to get better approximations of the zero-error capacity. We also show an additional application of our algorithms.

  Pełny tekst do pobrania w portalu

• Paired domination versus domination and packing number in graphs

  Publikacja

  • M. Dettlaff
  • D. Gözüpek
  • J. Raczek

  - JOURNAL OF COMBINATORIAL OPTIMIZATION - Rok 2022

  Given a graph G = (V(G), E(G)), the size of a minimum dominating set, minimum paired dominating set, and a minimum total dominating set of a graph G are denoted by γ (G), γpr(G), and γt(G), respectively. For a positive integer k, a k-packing in G is a set S ⊆ V(G) such that for every pair of distinct vertices u and v in S, the distance between u and v is at least k + 1. The k-packing number is the order of a largest kpacking and...

  Pełny tekst do pobrania w portalu

Rok 2021

• Secure Italian domination in graphs

  Publikacja

  • M. Dettlaff
  • M. Lemańska
  • J. A. RODRíGUEZ-VELáZQUEZ

  - JOURNAL OF COMBINATORIAL OPTIMIZATION - Rok 2021

  An Italian dominating function (IDF) on a graph G is a function f:V(G)→{0,1,2} such that for every vertex v with f(v)=0, the total weight of f assigned to the neighbours of v is at least two, i.e., ∑u∈NG(v)f(u)≥2. For any function f:V(G)→{0,1,2} and any pair of adjacent vertices with f(v)=0 and u with f(u)>0, the function fu→v is defined by fu→v(v)=1, fu→v(u)=f(u)−1 and fu→v(x)=f(x) whenever x∈V(G)∖{u,v}. A secure Italian dominating...

  Pełny tekst do pobrania w portalu

Rok 2018

• Computational aspects of greedy partitioning of graphs

  Publikacja

  • P. Borowiecki

  - JOURNAL OF COMBINATORIAL OPTIMIZATION - Rok 2018

  In this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs P (the problem is also known as P-coloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy...

  Pełny tekst do pobrania w portalu

Rok 2016

• An O ( n log n ) algorithm for finding edge span of cacti

  Publikacja

  • R. Janczewski
  • K. Turowski

  - JOURNAL OF COMBINATORIAL OPTIMIZATION - Rok 2016

  Let G=(V,E) be a nonempty graph and xi be a function. In the paper we study the computational complexity of the problem of finding vertex colorings c of G such that: (1) |c(u)-c(v)|>=xi(uv) for each edge uv of E; (2) the edge span of c, i.e. max{|c(u)-c(v)|: uv belongs to E}, is minimal. We show that the problem is NP-hard for subcubic outerplanar graphs of a very simple structure (similar to cycles) and polynomially solvable for...

  Pełny tekst do pobrania w portalu

Rok 2015

• Zero-visibility cops and robber and the pathwidth of a graph

  Publikacja

  • D. Dereniowski
  • D. Dyer
  • R. M. Tifenbach
  • B. Yang

  - JOURNAL OF COMBINATORIAL OPTIMIZATION - Rok 2015

  We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops and robber game in one way: the robber is invisible. We show that this model is not monotonic. We show that the zero-visibility copnumber of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the...

  Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2007

• Packing [1,Delta]-factors in graphs of small degree

  Publikacja

  • A. Kosowski
  • M. Małafiejski
  • P. Żyliński

  - JOURNAL OF COMBINATORIAL OPTIMIZATION - Rok 2007

  Rozważano problem znalezienia w grafie zadanej liczby k krawędziowo rozłącznych [1,Delta]-faktorów, gdzie Delta oznacza stopień grafu. Problem ten można rozwiązać w czasie liniowym dla k=2, jest on jednak NP-trudny dla każdego k>=3. Pokazano, że wariant minimalizacjny problemu dla k=2 jest NP-trudny dla grafów planarnych podkubicznych, jednak w ogólności istnieje algorytm (42 Delta - 30) / (35 Delta - 21) - aproksymacyjny.

  Pełny tekst do pobrania w serwisie zewnętrznym