Rok 2016

• On the hardness of computing span of subcubic graphs

  Publikacja

  • R. Janczewski
  • K. Turowski

  - INFORMATION PROCESSING LETTERS - Rok 2016

  In the paper we study the problem of finding ξ-colorings with minimal span, i.e. the difference between the largest and the smallest color used.

  Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2015

• The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones

  Publikacja

  • R. Janczewski
  • K. Turowski

  - INFORMATION PROCESSING LETTERS - Rok 2015

  Given a graph G, a spanning subgraph H of G and an integer λ>=2, a λ-backbone coloring of G with backbone H is a vertex coloring of G using colors 1, 2, ..., in which the color difference between vertices adjacent in H is greater than or equal to lambda. The backbone coloring problem is to find such a coloring with maximum color that does not exceed a given limit k. In this paper, we study the backbone coloring problem for bounded-degree...

  Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2013

• Trees having many minimal dominating sets

  Publikacja

  • M. Krzywkowski

  - INFORMATION PROCESSING LETTERS - Rok 2013

  We provide an algorithm for listing all minimal dominating sets of a tree of order n in time O(1.4656^n). This leads to that every tree has at most 1.4656^n minimal dominating sets. We also give an infinite family of trees of odd and even order for which the number of minimal dominating sets exceeds 1.4167^n, thus exceeding 2^{n/2}. This establishes a lower bound on the running time of an algorithm for listing all minimal dominating...

  Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2009

• Maximum vertex occupation time and inert fugitive: recontamination does help [online]

  Publikacja

  • D. Dereniowski

  - INFORMATION PROCESSING LETTERS - Rok 2009

  Rozważamy problem przeszukania danego grafu prostego G w celu przechwycenia niewidocznego i leniwego uciekiniera. Parametrem optymalizacyjnym, który minimalizujemy jest maksymalny czas (liczba tur strategii przeszukiwania), podczas których wierzchołek może być strzeżony (okupowany przez strażnika). Strategia monotoniczna to taka, która nie dopuszcza sytuacji, w której uciekinier dociera do wierzchołka, który wcześniej został oczyszczony....

  Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2008

• A note on mixed tree coloring

  Publikacja

  • H. Furmańczyk
  • A. Kosowski
  • P. Żyliński

  - INFORMATION PROCESSING LETTERS - Rok 2008

  Zaproponowano liniowy algorytm dla problemu kolorowania mieszanego w drzewach, uzyskując tym samym poprawę w stosunku do algorytmu o złożoności O(n^2) podanego w pracy [P. Hansen, J. Kuplinsky, D. de Werra, Mixed graph colorings, Math. Methods Oper. Res. 45 (1997) 145-160].

  Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2006

• An approximation algorithm for maximum P3-packing in subcubic graphs

  Publikacja

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

  - INFORMATION PROCESSING LETTERS - Rok 2006

  W pracy podano algorytm 4/3-przyliżony dla trudnego obliczeniowo problemu umieszczania wierzchołkowo rozłącznych dwukrawędziowych ścieżek w grafach o stopniu maksymalnym 3 i stopniu minimalnym 2. Poprawiono tym samym wcześniejsze wyniki dla grafów kubicznych (A. Kelmans, D. Mubayi, Journal of Graph Theory 45, 2004).

  Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2002

• Complexity of weak acceptonic conditions in tree automata

  Publikacja

  • J. Neumann
  • A. Szepietowski
  • I. Walukiewicz

  - INFORMATION PROCESSING LETTERS - Rok 2002

  Rozważano złożoność problemu pustości dla automatów na drzewach ze słabymi warunkami akceptowalności. Rozważano także translacje pomiędzy słabymi i silnymi warunkami akceptowalności.

Rok 2000

• Edge-chromatic sum of trees and bounded cyclicity graphs

  Publikacja

  • K. Giaro
  • M. Kubale

  - INFORMATION PROCESSING LETTERS - Rok 2000

  Pełny tekst do pobrania w serwisie zewnętrznym