Wyniki wyszukiwania dla: KOLOROWANIE KRAWEDZI

• Compact cyclic edge-colorings of graphs

  Publikacja

  • A. Nadolski

  - DISCRETE MATHEMATICS - Rok 2008

  Artykuł jest poświęcony modelowi zwartego cyklicznego kolorowania krawędzi grafów. Ten wariant kolorowania jest stosowany w modelowaniu uszeregowań w systemach produkcyjnych, w których proces produkcyjny ma charakter cykliczny. W pracy podano konstrukcje grafów, które nie zezwalają na istnienie pokolorowania w rozważanym modelu. Wykazano także kilka własności teoretycznych, takich jak ograniczenia górne na liczbę kolorów w optymalnym...

  Pełny tekst do pobrania w serwisie zewnętrznym

• Hipergrafowy model szeregowania w rozrzedzonych systemach zadań wieloprocesorowych

  Publikacja

  • P. Oszarski
  • J. Dąbrowski

  - Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne - Rok 2006

  Hipergrafem nazywamy pewne uogólnienie grafu, w którym krawędzie mogą zawierać dowolnie wiele wierzchołków. Model taki pozwala symulować rozmaite zjawiska praktyczne oraz teoretyczne. W tym artykule będziemy mówić o kolorowaniu krawędzi hiperdrzew. Pokażemy jaki jest indeks chromatyczny dla tej klasy hipergrafów oraz jaki jest sumacyjny indeks chromatyczny dla hiperdrzew prostych. Zademonstrujemy także wielomianowe algorytmy szukające...

• 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

• Grafo-mania, czyli rzecz o grafach i algorytmach. Liczby Ramseya

  Publikacja

  • M. Kubale

  - Pismo PG - Rok 2022

  Zdefiniowano liczby Ramseya i wskazano na trudności obliczeniowe ich wyznaczania już przy niewielkich wartościach takich liczb.

  Pełny tekst do pobrania w serwisie zewnętrznym

• Circular colorings of graphs.

  Publikacja

  • A. Nadolski

  - Rok 2004

  Rozdział poświęcony jest cyrkularnemu modelowi kolorowania krawędzi. Rozważana jest zarówno wersja wierzchołkowa i krawędziowa. Szczególny nacisk położono na złożoność obliczeniową i zastosowania dla omawianych modeli kolorowania.

• Interval edge-coloring of graphs.

  Publikacja

  • K. Giaro

  - Rok 2004

  Rozdział poświęcony prezentacji modelu zwartego kolorowania krawędziowego grafów i jego znanych własności. Szczególny nacisk położono na opis klas grafów dających się pokolorować zwarcie w czasie wielomianowym. Omówiono także stratność jako miarę niepodatności grafu na kolorowanie zwarte.