Search
Best results in : Research Potential Pokaż wszystkie wyniki (1)
Search results for: liczba chromatyczna
-
Zespół Algorytmów i Modelowania Systemów
Research PotentialStudiowanie problemów i modeli teoriografowych ma na celu badanie złożoności obliczeniowej uogólnień problemu klasycznego kolorowania wierzchołków i krawędzi grafu znajdujących zastosowania w modelowaniu praktycznych problemów oraz badanie nowych miar oceny skuteczności algorytmów. W zakresie szeregowania zadań badania koncentrują się na konstrukcji harmonogramów optymalnych z punktu widzenia długości harmonogramu i średniego czasu...
Other results Pokaż wszystkie wyniki (11)
Search results for: liczba chromatyczna
-
Antypodalna radiowa liczba chromatyczna grafu.
PublicationOpisane zostały podstawowe zasady i właściwości antypodalnego kolorowania grafów. Zebrano publikowane w literaturze przedmiotu twierdzenia i uzupełniono wnioskami wynikającymi z własnych badań.
-
Joanna Raczek dr inż.
PeopleEmployment 2003 -- 2019: Faculty of Applied Physics and Mathematics, Gdańsk University of Technology. 2019 - present: Faculty of Electronic, Informatics and Telecominications, Gdańsk University of Technology. Education May 2007: Doctor of Philosophy in Mathematics, University of Gdańsk. Doctoral dissertation: "Paired domination and doubly domination in graphs". Supervisor: dr hab. Jerzy Topp. 2000 -- 2004 Bachelor of Science...
-
Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
PublicationW pracy rozważamy problem szukania, dla danego grafu prostego, drzewa spinającego, którego uporządkowana liczba chromatyczna jest minimalna. K.~Miyata i inni dowiedli w [Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem,Discrete Appl. Math. 154 (2006) 2402-2410], że odpowiedni problem decyzyjny jest NP-trudny już w przypadku pytania o istnienie uporządkowanego 4-pokolorowania....
-
Modele i metody kolorowania grafów. Część I
PublicationNiniejszy artykuł jest pierwszą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano co można kolorować w grafie i jak to można kolorować. Ponieważ kolorowanie we wszystkich odmianach i wariantach jest NP-trudne, podajemy oszacowania na liczbę chromatyczną oraz potencjalne zastosowania...
-
Modele i metody kolorowania grafów. Część II
PublicationNiniejszy artykuł jest drugą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano różne kryteria i ograniczenia modyfikujące kolorowanie klasyczne. Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podano oszacowania na liczbę chromatyczną (indeks chromatyczny)...