Search results for: WIR WIERZCHOŁKOWY

• Uporządkowane kolorowanie wierzchołków grafów

  Publication

  • M. Kubale
  • D. Dereniowski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Year 2002

  W pracy przedstawiamy stosunkowo nowy model kolorowania grafów, mianowicie kolorowanie uporządkowane. Po scharakteryzowaniu potencjalnych zastosowań tego modelu przedstawiamy liniowy algorytm kolorowania grafów w sposób przybliżony. Pokazujemy klasy grafów, które ten algorytm koloruje optymalnie i klasy grafów, dla których błąd pokolorowania może być dowolnie duży. Przedstawiamy również doświadczenia komputerowe zebrane w trakcie...

• Ograniczone (p1, p2,...,pk) kolorowanie wierzchołków grafów.

  Publication

  • H. Furmańczyk
  • K. Giaro

  - Year 2002

  Problem ograniczonego (p1,...,pk) kolorowania grafów polega na poszukiwaniu odpowiedzi na pytanie, czy istnieje takie pokolorowanie wierzchołków grafu , że krotności użycia poszczególnych barw są równe ustalonym progom p1,...,pk. W ogólnym przypadku problem ten, jako uogólnienie klasycznego kolorowania grafów pozostaje NP-zupełnym. W pracy przedstawiamy wyniki dotyczące ograniczonego kolorowania split grafów, kografów oraz...

• WATER AIR AND SOIL POLLUTION

  Journals

  ISSN: 0049-6979 , eISSN: 1573-2932

• The complexity of equitable vertex coloring graphs

  Publication

  • H. Furmańczyk
  • M. Kubale

  - Year 2005

  W artykule podajemy wzory na sprawiedliwą liczbę chromatyczną niektórych produktów grafowych. Ponadto przedstawiamy dwa algorytmy wielomianowe dla sprawiedliwego kolorowania grafów suboptymalną liczba kolorów.

• Elektronika Ir Elektrotechnika

  Journals

  ISSN: 1392-1215

• War in History

  Journals

  ISSN: 0968-3445 , eISSN: 1477-0385

• War and Society

  Journals

  ISSN: 0729-2473 , eISSN: 2042-4345

• NOVYI MIR

  Journals

  ISSN: 0130-7673

• Kolorowanie grafów z ograniczeniami na liczbę wierzchołków w określonym kolorze = Graph coloring model with restrictions on cardinalities of vertexes in particular color

  Publication

  • P. Obszarski

  - Year 2012

  W artykule rozważamy problem takiego kolorowania grafów, w którym klasy kolorów mają ograniczoną z góry moc. Zagadnie to znajduje ciekawe zastosowania praktyczne i jest naturalnym uogólnieniem problemu kolorowania grafów. W artykule ustalamy złożoność obliczeniową dla grafów pełnych $r$-dzielnych i dla kilku innych prostych klas grafów oraz dla problemu dwukolorowania.

• Efficient list cost coloring of vertices and/or edges of some sparse graphs

  Publication

  • K. Giaro
  • M. Kubale

  - Year 2007

  Rozważane jest kolorowanie wierzchołków i krawędzi grafów w modelach klasycznym, totalnym i pseudototalnym z uwzględnieniem dodatkowego ograniczenia w postaci list dostępnych kolorów. Proponujemy wielomianowy algorytm oparty na paradygmacie programowania dynamicznego dla grafów o strukturze drzewa. Wynik ten można uogólnić na grafy o liczbie cyklomatycznej ograniczonej z góry przez dowolnie wybraną stała.