Filtry
wszystkich: 396
wybranych: 306
-
Katalog
- Publikacje 306 wyników po odfiltrowaniu
- Czasopisma 1 wyników po odfiltrowaniu
- Osoby 14 wyników po odfiltrowaniu
- Wynalazki 2 wyników po odfiltrowaniu
- Projekty 3 wyników po odfiltrowaniu
- Laboratoria 1 wyników po odfiltrowaniu
- Zespoły Badawcze 3 wyników po odfiltrowaniu
- Kursy Online 57 wyników po odfiltrowaniu
- Wydarzenia 2 wyników po odfiltrowaniu
- Dane Badawcze 7 wyników po odfiltrowaniu
Filtry wybranego katalogu
Wyniki wyszukiwania dla: KOLOROWANIE LISTOWE
-
Algorytmy radiowego kolorowania grafów. XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych.
PublikacjaW pracy opisane są podstawowe zasady i właściwości radiowego kolorowania grafów. Podane są oszacowania radiowej liczby chromatycznej grafu w przypadku ogólnym, dla ścieżek i cykli oraz dokładne wartości radiowej liczby chromatycznej dla grafów pełnych k-dzielnych, kół i dwugwiazd. Zamieszczono także przykładowe wyniki porównania dobroci suboptymalnych, sekwencyjnych algorytmów radiokolorowania grafów.
-
Minimalizacja szerokości pasma w sieciach radiowych metodami szkieletowego kolorowania grafów
PublikacjaArtykuł poświęcony jest szkieletowemu kolorowaniu grafów, które jest matematycznym modelem dla problemu minimalizacji szerokości pasma w sieciach radiowych. Badamy w nim zależność szkieletowej liczby chromatycznej od parametrów zagadnienia. Dowodzimy, że dla dużych wartości parametrów ta zależność jest liniowa.
-
Wybrane zastosowania niestandardowych modeli kolorowania w szeregowniu dwu-procesowych zadań jednostkowych
PublikacjaNiniejsza praca poświęcona jest wykorzystaniu teorii chromatycznej grafów wszeregowaniu. Koncepcja ta polega na przedstawieniu zbioru zadań w postaci krawędzi tzw. grafu konfliktów.
-
O problemie przydziału częstotliwości, kontrastowym kolorowaniu grafów i częściowych k-drzewach
PublikacjaNiniejszy artykuł poświęcony jest złożoności obliczeniowej problemu przydziału częstotliwości. Zawiera dowód tego, że jest on NP-trudny nawet dla grafów interferencji, będących grafami dwudzielnymi, oraz wielomianowy algorytm rozwiązujący ten problem dla grafów interferencji, będących częściowymi k-drzewami.
-
Heterogeniczne środowisko testowe na potrzeby weryfikacji mechanizmów systemu netBaltic
PublikacjaPrzedstawiono heterogeniczne środowisko testowe integrujące różne techniki transmisji, wykorzystywane w testach elementów systemu netBaltic. Omówiono poszczególne istotne komponenty systemu testowego: sieć nabrzeżną, instalację na jednostkach pływających oraz instalację na boi pomiarowej. Jako ilustrację możliwości systemu zaprezentowano przykładowe wyniki uzyskane w opisanym środowisku.
-
Przyczółki mostowe z konstrukcją odciążającą z gruntu zbrojonego geosyntetykami
PublikacjaPrzegląd najważniejszych cech geotekstyliów i wyrobów pokrewnych, zastosowanych do budowy bloków odciążających ze szczególnym uwzględnieniem ich wytrzymałości długo i krótkookresowej oraz reologii. Określenie obciążeń działających na konstrukcję gruntową współpracującą z przyczółkiem; obciążenia normowe i rzeczywiste. Obliczenia konstrukcji z gruntu zbrojonego współpracującej z przyczółkiem
-
Compact cyclic edge-colorings of graphs
PublikacjaArtykuł 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...
-
Grafowy model macierzy ultrametrycznej i jego zastosowania w filogenezie i t-kolorowaniu
PublikacjaW pracy podano definicję macierzy ultrametrycznej i jej reprezentację grafową. Macierz ta jest wykorzystywana głównie w filogenezie, do budowy drzew ultrametrycznych. W pracy opisano jeden z algorytmów słuzący do konstrukcji takich drzew. Ponadto, omówiono inne możliwe zastosowania modelu grafowego macierzy, tym razem dla problemu przydziału częstotliwości dla nadajników. Zaproponowano również rozwiązanie tego problemu w szczególnym...
-
Liniowe skalowanie funkcji przystosowania w ewolucyjnej metodzie planowania ścieżek przejść
PublikacjaW pracy analizowano wpływ skalowania funkcji przystosowania na jakość rozwiązania problemu planowania ścieżki przejścia obiektu ruchomego metodą ewolucyjną. Opisano metody skalowania funkcji przystosowania, ze szczególnym uwzględnieniem skalowania liniowego i jego wpływu na nacisk selektywny. Przeprowadzone badania wykazały, że zastosowanie skalowania w ewolucyjnej metodzie poszukiwania ścieżek przejść pozwala w fazie eksploracji...
-
Hierarchiczny system sterowania procesem mieszania. Implementacja sprzętowa i badania testowe
PublikacjaProces mieszania jest często wykorzystywany w różnych gałęziach przemysłu. W artykule rozważana jest mieszanina aceton-octan etylu. Podstawowym celem jest uzyskanie właściwego stopnia jednorodności mieszaniny. W artykule zbudowano model matematyczny procesu mieszania i zaprojektowano warstwowy system sterowania. Składa się on z nadrzędnego regulatora rozmytego oraz warstwy bezpośredniej z regulatorami typu PID i sterowaniem binarnym....
-
Modułowe narzędzia ścierne. Diamentowe piły linowe - budowa i zastosowania
PublikacjaPrzedstawiono budowę modułowych narzędzi ściernych do przecinania, zwłaszcza dużych przekrojów. Omówiono diamentowe piły linowe, zwane także koralikowymi, przeznaczone głównie do pozyskiwania bloków skalnych w kamieniołomach oraz w pracach remontowo-budowlanych, w tym rozcinania konstrukcji budowlanych.
-
PROJEKT LISTWY ZASILAJĄCEJ W OPARCIU O KONCEPCJĘ INTERNETU RZECZY
PublikacjaW referacie przedstawiono podstawowe uwarunkowania, jakimi należy kierować się przy opracowywaniu urządzeń należących do klasy obiektów określanych mianem „Internetu Rzeczy” na przykładzie zrealizowanego prototypu listwy zasilającej. Przedstawione w pracy urządzenie przeznaczone jest do sterowanie różnorodnymi odbiornikami energii elektrycznej niemogącymi być bezpośrednio sterowanymi z sieci Ethernet. W pracy przedstawiono przyjęte...
-
Badanie właściwości czujnika elektrokatalitycznego na bazie tytanianu litowo-lantanowego
PublikacjaW pracy przedstawiono wyniki badań wpływu stężenie ditlenku azotu na kształt charakterystyk prądowo-napięciowych (I-V) nowego czujnika elektrokatalitycznego na bazie elektrolitu stałego z mobilnymi jonami litu LiLaTiO3. Czujnik ten został wykonany w technologii ceramicznej w formie pastylki z porowatymi elektrodami złotymi naniesionymi po obu jej stronach. Wykonano pomiary odpowiedzi czujnika w temperaturach 175ºC i 300ºC. Stężenie...
-
A Review of Progress in Histone Deacetylase 6 inhibitors Research: Structural Specificity and Functional Diversity.
Publikacja -
Środowisko testowe i symulacyjne do weryfikacji bezpieczeństwa kooperacyjnego w sieciach bezprzewodowych
PublikacjaWraz z rozwojem bezprzewodowych sieci komputerowych rośnie potrzeba zapewnienia zadowalającego poziomu bezpieczeństwa ich unkcjonowania. Potrzeba taka istniała już w przypadku klasycznych sieci przewodowych, lecz środowisko sieci bezprzewodowej okazuje się szczególnie podatne na różnorodne zagrożenia, poczynając od atakówtypu DoS, poprzez zagrożenia poufności i integralności danych oraz manipulację informacją o tożsamości użytkowników,...
-
Obiekty mostowe obwodnicy miasta Wolin w świetle badań podczas próbnego obciążenia.
Publikacja02 grudnia 2003r. oddano do eksploatacji obwodnicę miasta Wolin w ciągu drogi krajowej nr 3. Droga ta odgrywa ważną rolę w tranzytowym ruchu międzynarodowym (kraje skandynawskie - południe Europy) oraz krajowym (północ - południe). Obsługuje ona również port i bazy promowe w Świnoujściu. Nowa droga zlokalizowana w sąsiedztwie toru kolejowego, umożliwia bezkolizyjny przejazd przez miasto. Całkowita długość wybudowanego odcinka wynosi...
-
Weryfikacja założeń do badań sonarowych oraz pomiary testowe w basenie portowym
Publikacja.
-
Parallel query processing and edge ranking of graphs
PublikacjaArtykuł poświęcony jest problemowi szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym. Jednym z zastosowań jest poszukiwanie optymalnych harmonogramów w równoległym przetwarzaniu zapytań w relacyjnych bazach danych. Podajemy nowe oszacowanie funkcji dobroci przybliżonego algorytmu autorstwa Makino, Uno i Ibaraki wraz z rezultatami testów komputerowych przeprowadzonych dla grafów losowych.
-
Self-stabilizing algorithms for graph coloring with improved performance guarantees
PublikacjaW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.
-
The complexity of equitable vertex coloring graphs
PublikacjaW 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.
-
A note on mixed tree coloring
PublikacjaZaproponowano 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].
-
Monoubiquitinated Histone H1B Is Required for Antiviral Protection in CD4+T Cells Resistant to HIV-1
Publikacja -
Wpływ załączonych dodatkowych odbiorników mocy na testowe wyniki analizy spalin samochodu osobowego.
PublikacjaW artykule przedstawiono opracowane wyniki testów spalin przy załączonych w czasie testu dodatkowych odbiornikach energii. Badania przeprowadzono w wytwórni samochodów osobowych. Przebadano jeden samochód, po przebiegu 30 tys. km specjalnie opracowanym testem, powtarzanym pięciokrotnie dla każdego załączonego odbiornika. Wykazano wyraźny związek dodatkowej mocy pobieranej z wału silnika ze zwiększeniem ilości składników toksycznych...
-
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
PublikacjaW 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.
-
Niedeterministyczne układy równań w analizie sterowania systemami produkcyjnymi : Cz. 2 Liniowe zagadnienia stochastyczne
PublikacjaW częci pierwszej pracy przedstawiono zagadnienia przedziałowych i rozmytych układów równań liniowych w problemie sterowania systemem produkcyjnym. Wiele zagadnień może być sformułowanych w postaci stochastycznej. Poniżej omawia się problem opisany przez zmienne losowe z dokładnociš do momentów drugiego rzędu. Opierajšc się na przedstawionej w częci pierwszej metodzie rozwišzania niedeterministycznego układu równa_ liniowych...
-
Liniowe i nieliniowe modele wielowymiarowej kalibracji do predykcji stężenia substancji z pomiarów woltamperometrycznych
PublikacjaPomiary woltamperometryczne znajdują zastosowanie w wielu dziedzinach nauki i techniki, np. w przemyśle farmaceutycznym. Dane uzyskane w wyniku takich pomiarów zawierają informację odnośnie rodzaju i stężenia badanej substancji, jednakże są one często kłopotliwe w bezpośredniej interpretacji. Z tego powodu, istnieje konieczność wykorzystania odpowiednich metod matematycznych, które umożliwiają uzyskanie bezpośredniej i precyzyjnej...
-
Ocena jakości superkondensatorów wybranymi metodami, wykorzystując zjawiska losowe i badania rozkładu temperatury
PublikacjaW artykule przedstawiono metody analizy jakości wykonania próbek superkondensatorów na podstawie pomiarów szumów generowanych w ich strukturach oraz rozkładów temperatury na ich powierzchni. Prezentowane metody zostały porównane z obecnie stosowanymi parametrami oceny jakości tych elementów. Wyniki uzasadniają wprowadzenie dodatkowych parametrów, pozwalających oceniać jakość superkondensatorów.
-
Edge ranking and searching in partial orders
PublikacjaArtykuł jest poświęcony problemowi konstrukcji optymalnej (wymagającej minimalnej ilości porównań/zapytań) strategii wyszukiwania elementu w częściowym porządku. W pracy wskazano związki pomiędzy tym problemem oraz uporządkowanym kolorowaniem krawędzi grafów, co implikuje liniowy algorytm dla częściowych porządków o strukturze drzewa. Pokazano również, że znalezienie optymalnej strategii jest problemem obliczeniowo trudnym dla...
-
On the complexity of distributed greedy coloring
PublikacjaW pracy rozważono problem kolorowania grafów przy dodatkowym założeniu, że kolor żadnego wierzchołka nie może zostać zmniejszony bez zmiany kolorów przynajmniej jednego z jego sąsiadów. Przeprowadzone rozważania dotyczyły złożoności obiczeniowej problemu w modelu Liniala obliczeń rozproszonych. Podano ograniczenia dolne i górne złożoności problemu oraz zestawiono problem z innymi pokrewnymi zagadnieniami grafowymi.
-
On greedy graph coloring in the distributed model
PublikacjaArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Zaprezentowano nowy probabilistyczny algorytm dający w wyniku pokolorowanie LF. Udowodniono, że jakakolwiek rozproszona implementacja LF wymaga co najmniej D rund, gdzie D jest maksymalnym stopniem wierzchołka w grafie.
-
Self-stabilizing algorithm for edge-coloring of graphs
PublikacjaReferat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu wraz z dowodem poprawności oraz oszacowaniem jego czasu działania.
-
Otrzymywanie i właściwości materiałów anodowych zawierających nanokompozyty krzemionkowo-węglowe do ogniw litowo–jonowych
PublikacjaWzrost zapotrzebowania na urządzenia elektrochemiczne do magazynowania i konwersji energii elektrycznej prowadzi do postępu w badaniach nad materiałami elektrodowymi i elektrolitami. W zakresie badań nad nowymi materiałami elektrodowymi do baterii litowo - jonowych (LIB) najbardziej obiecującym wydaje się być krzem. Jednakże krzem podlega drastycznym zmianom objętości w procesie wprowadzania i wyprowadzania jonów litu. Alternatywnym...
-
Niedeterministyczne układy równań w analizie sterowania systemami produkcyjnymi : Cz. 1 Liniowe zagadnienia przedziałowe i rozmyte
PublikacjaRozpatruje się zagadnienia niedeterministycznych układów równań liniowych stanowišcych jeden z istotnych elementów rozwišzania zagadnienia sterowania produkcja systemów przemysłowych. Problem tenwystępuje przy badaniu przyjmowanego do realizacji bazowego rozwišzania liniowego zagadnienia planowania obcišżeń systemu. W przypadku modelu niedeterministycznego planowania, niepewnoć przenosi się na rozwišzanie jak również generuje...
-
Uproszczone liniowe modele transformacji fali w korycie rzecznym. Monografie Komitetu Gospodarki Wodnej Polskiej Akademii Nauk
PublikacjaW niniejszym opracowaniu przedstawiono analizę właściwości modeli uproszczonych stosowanych w hydrologii wód powierzchniowych. Jego celem było możliwie pełne ich wyjaśnienie. Przedmiotem zainteresowania były modele fali dyfuzyjnej, kinematycznej oraz Muskingum.
-
Equitable 4-coloring of cacti and edge-cacti in polynomial time
PublikacjaRozważono problem wyznaczania sprawiedliwej liczby chromatycznej kaktusów i drzew wielokątowych bez trójkątów i krawędzi wiszących. Podano wielomianowy algorytm wyznaczający pokolorowanie optymalne, oparty na paradygmacie programowania dynamicznego. Tym samym znaleziona została kolejna klasa grafów planarnych, dla której kolorowanie sprawiedliwe jawi się jako zagadnienie obliczeniowo łatwe.
-
Heurystyczne algorytmy szeregowania zadań wieloprocesorowych na procesorach dedykowanych
PublikacjaProblem szeregowania zadań wieloprocesorowych na procesorach dedykowanych można zaprezentować przy pomocy modelu kolorowania krawędzi hipergrafów. 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. Kolorowanie hiperkrawędzi hipergrafów jest uogólnieniem kolorowania krawędzi grafów, zatem jest problemem...
-
Szeregowanie zadań dwuprocesorowych w systemach otwartych
PublikacjaW pracy rozważany jest problem szeregowania zadań dwuoperacyjnych w systemie otwartym (open-shop), z kryterium minimalizacji długości harmonogramu oraz sumy czasów zakończenia wszystkich zadań. Zakładając jednostkowe czasy wykonywania operacji można stosować efektywne metody chromatyczne rozwiązywania problemu, poprzez sprowadzenie go do modelu grafowego oraz zastosowanie w nim wybranego modelu kolorowania, które pozwala uzyskać...
-
Classical coloring of graphs.
PublikacjaRozdział obejmuje klasyczne kolorowanie krawędzi i wierzołków w grafach prostych. Oprócz podstawowych definicji podane zostały najczęściej stosowane metody przybliżone oraz ich właściwości. Dodatkowo rozdział zawiera przegląd znanych benczmarków dla podanych metod w kontekście klasycznego modelu kolorowania.
-
Interval edge-coloring of graphs.
PublikacjaRozdział 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.
-
Parallel tabu search for graph coloring problem
PublikacjaTabu search is a simple, yet powerful meta-heuristic based on local search that has been often used to solve combinatorial optimization problems like the graph coloring problem. This paper presents current taxonomy of patallel tabu search algorithms and compares three parallelization techniques applied to Tabucol, a sequential TS algorithm for graph coloring. The experimental results are based on graphs available from the DIMACS...
-
A self-stabilizing algorithm for finding a spanning tree in a polynomial number of moves
PublikacjaW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm znajdowania drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm dla tego problemu z gwarantowaną wielomianową liczbą ruchów.
-
Cholesky factorization of matrices in parallel and ranking of graphs.
PublikacjaUporządkowane kolorowanie znajduje zastosowanie przy równoległej faktoryzacji macierzy metodą Cholesky'ego. Praca zawiera opis tego zastosowania. Podano także algorytmy optymalnego uporządkowanego kolorowania krawędzi pewnych klas grafów: grafów pełnych dwudzielnych oraz powstałych z pełnych dwudzielnych przez usunięcie O(log n) krawędzi.
-
Sum coloring of bipartite graphs with bounded degree.
PublikacjaArtykuł poświęcony jest złożoności obliczeniowej zagadnienia sumacyjnego kolorowania grafów dwudzielnych o ograniczonym stopniu. Zawiera dowód tego, że sumacyjne kolorowanie grafów dwudzielnych stopnia mniejszego równego 5 jest NP-zupełne oraz opis wielomianowego algorytmu, który optymalnie sumacyjnie koloruje grafy dwudzielne podkubiczne.
-
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
PublikacjaW artykule rozważamy listowo-kosztowe kolorowanie wierzchołków i krawędzi grafu w modelu wierzchołkowym, krawędziowym, totalnym i pseudototalnym. Stosujemy programowanie dynamiczne w celu otrzymania algorytmów wielomianowych dla drzew. Następnie uogólniamy to podejście na dowolne grafy z ograniczonymi liczbami cyklomatycznymi i na ich multikolorowania.
-
Easy and hard instances of arc ranking in directed graphs
PublikacjaArtykuł dotyczy uporządkowanego kolorowania łuków grafów skierowanych. Problem polega na takim przyporządkowaniu liczb łukom digrafu, aby każda skierowana ścieżka łącząca dwa łuki o tej samej liczbie (kolorze) zawierała łuk o kolorze wyższym. Praca podaje liniowy optymalny algorytm dla pewnego szczególnego przypadku, oraz zawiera dowód, iż problem ten jest obliczeniowo trudny dla 3-dzielnych acyklicznych digrafów i stałej liczby...
-
Distributed largest-first algorithm for graph coloring.
PublikacjaW artykule zaprezentowano rozproszony, probabilistyczny algorytm kolorowania grafów. Kolorowanie uzyskane jest optymalne lub prawie optymalne dla takich klas grafów jak koła dwudzielne, gąsienice czy korony. Udowodniono, że algorytm ten działa w czasie O(D^2 log n) rund dla dowolnego grafu n wierzchołkowegoo stopniu maksymalnym D.
-
On efficient coloring of chordless graphs
PublikacjaArtykuł omawia zagadnienie optymalnego, wielomianowego rozpoznawania i kolorowania grafów bezcięciwowych. Zawiera dowód tego, że takie grafy są zawsze 4-kolorowalne oraz opis wielomianowego algorytmu, który koloruje je minimalną możliwą liczbą kolorów.
-
A note on compact and compact circular edge-colorings of graphs
PublikacjaW 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...
-
Some results on trading model in a consensus list coloring
PublikacjaKonsensusowy model kolorowania grafów - uogólnienie kolorowania listowego, został zdefiniowany przez Mahadeva i Robertsa w 2002 jako użyteczne narzędzie teoretyczne w niektórych zagadnieniach bioinformatycznych. Pozostaje on jednak słabo rozpoznany pod względem własności algorytmicznych. Wykazujemy, że problem kolorowania grafów pełnych w tym modelu jest wielomianowy, co można uogólnić na częściowe k-drzewa przy ustalonym ograniczeniu...
-
Optymalne pokolorowania średnicowe dla wybranych klas grafów
PublikacjaW pracy opisano wybrane właściwości szczególnego przypadku radiowego kolorowania grafów, zwanego kolorowaniem średnicowym. Podano zasadę działania algorytmu optymalnego kolorowania średnicowego i oszacowania liczby średnicowej grafu w przypadku ogólnym oraz dla ścieżek i cykli. Korzystając z podanego algorytmu, znaleziono dokładne wartości liczby średnicowej dla ścieżek i cykli niewielkiej długości, co pozwoliło na obalenie wcześniej...