Wyniki wyszukiwania dla: GRAF DWUDZIELNY

• A note on compact and compact circular edge-colorings of graphs

  Publikacja

  • D. Dereniowski
  • A. Nadolski

  - DISCRETE MATHEMATICS - Rok 2008

  W pracy rozważamy dwa warianty kolorowania krawędzi grafów prostych i ważonych, mianowicie kolorowania zwarte oraz zwarte cyrkularne. Rozważamy relacje pomiędzy nimi. Dowodzimy, że każdy zewnętrznie planarny graf dwudzielny posiada zwarte pokolorowanie krawędziowe oraz, że problem ten dla grafów ogólnych jest NP-zupełny. Podajemy również wielomianowy 1.5-przybliżony algorytm oraz pseudowielomianowy dokładny algorytm zwartego cyrkularnego...

  Pełny tekst do pobrania w serwisie zewnętrznym

• Szeregowanie identycznych zadań na czterech procesorach jednorodnych z dwudzielnymi grafami konfliktów

  Publikacja

  • M. Kubale

  - Rok 2016

  Rozważono problem szeregowania n zadań jednostkowych na 4 procesorach jednorodnych o szybkościach s1>=s2>=s3>=s4. Celem szeregowania jest utworzenie najkrótszego możliwego harmonogramu. Zadania podlegają ograniczeniom zasobowym mówiącym, że niektóre pary zadań nie mogą być wykonane na tym samym procesorze. Podajemy algorytm dokładny, który rozwiązuje problem w czasie liniowym, o ile graf niezgodności jest kubiczny. Ponadto podajemy...

• Complixity results on open shop scheduling to minimize total cost of operations

  Publikacja

  • K. Giaro
  • M. Kubale
  • K. Piwakowski

  - International Journal of Signs and Semiotic Systems - Rok 2002

  W pracy zaprezentowano serię rezultatów dotyczących złożoności obliczeniowejproblemu szeregowania w systemie otwartym z kryterium łącznego kosztu opera-cji. W ogólności problem jest NP-trudny nawet w przypadku 1-procesorowym.Dlatego zaprezentowano możliwie wiele przypadków szczególnych, które są wie-lomianowe. Są one funkcją długości operacji i struktury grafu konfliktów po-między zadaniami.