Search results for: metody kolorowania grafow - Bridge of Knowledge

Search

Search results for: metody kolorowania grafow

Search results for: metody kolorowania grafow

  • Modele i metody kolorowania grafów. Część I

    Publication

    Niniejszy 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

    Publication

    Niniejszy 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)...

    Full text to download in external service

  • Zespół Algorytmów i Modelowania Systemów

    Studiowanie 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...

  • Robert Janczewski dr hab. inż.

  • Marek Kubale prof. dr hab. inż.

     Details concerning: Qualifications, Experiences, Editorial boards, Ph.D. theses supervised, Books, and Recent articles can be found at http://eti.pg.edu.pl/katedra-algorytmow-i-modelowania-systemow/Marek_KubaleGoogle ScholarSylwetka prof. Marka Kubalego Prof. Marek Kubale pracuje na Wydziale ETI Politechniki Gdańskiej nieprzerwanie od roku 1969. W tym czasie napisał ponad 150 prac naukowych, w tym ponad 40 z listy JCR. Ponadto...

  • Jerzy Konorski dr hab. inż.

    Jerzy Konorski received his M. Sc. degree in telecommunications from Gdansk University of Technology, Poland, and his Ph. D. degree in computer science from the Polish Academy of Sciences, Warsaw, Poland. In 2007, he defended his D. Sc. thesis at the Faculty of Electronics, Telecommunications and Informatics, Gdansk University of Technology. He has authored over 150 papers, led scientific projects funded by the European Union,...

  • Zdzisław Kowalczuk prof. dr hab. inż.

    Zdzislaw Kowalczuk received his M.Sc. degree in 1978 and Ph.D. degree in 1986, both in Automatic Control from Technical University of Gdańsk (TUG), Gdańsk, Poland. In 1993 he received his D.Sc. degree (Dr Habilitus) in Automatic Control from Silesian Technical University, Gliwice, Poland, and the title of Professor from the President of Poland in 2003. Since 1978 he has been with Faculty of Electronics, Telecommunications and Informatics...

  • Variacionnye metody

    Publication
    • J. Glazunov

    - Year 2006

    Monografia zawiera metody wariacyjne dla rozwiązywania zadań fizyki matematycznej. Rozwiązane zastałe odwrotne zagadnienie rachunku wariacyjnego dla nieliniowych równań różniczkowych. Zbudowana jedyną teorię takich zadań dla liniowych i nieliniowych równań różniczkowych.

  • Quantitative Methods in Economics

    Journals

    ISSN: 2082-792X , eISSN: 2543-8565

  • Algorytm samostabilizujący dla problemu kolorowania krawędzi grafu.

    Publication

    Referat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu. Jest to prawdopodobnie pierwszy algorytm krawędziowego kolorowania grafów w tym modelu. Rozważania teoretyczne zostały poparte eksperymentami komputerowymi.

  • Przybliżone algorytmy uporządkowanego kolorowania krawędzi multidrzew.

    Publication

    Niniejszy referat omawia zagadnienie uporządkowanego kolorowania krawędzi multidrzew. Opisano w nim dwa przybliżone algorytmy dla tego problemu, zbadano ich własności teoretyczne oraz przedstawiono wyniki testów komputerowych, jakim zostały poddane.

  • O pewnym zastosowaniu uporządkowanego kolorowania grafów

    Praca opisuje związki pomiędzy problemami uporządkowanego kolorowania wierzchołków grafów oraz szukania drzewa eliminacji o minimalnej wysokości dla danego grafu. Stąd wynika przydatność tytułowego problemu przy równoległej faktoryzacji macierzy metodą Cholsky´ego.

  • Szeregowanie zadań wieloprocesorowych metodą kolorowania hiperkrawędzi

    Publication

    W artykule rozważamy problem szeregowania jednostkowych zadań wieloprocesorowych na procesorach dedykowanych z repetycją zadań i ograniczeniami dostępności. Prezentujemy zebrane wyniki złożoności dla różnych typów instancji powyższego problemu szeregowania z kryteriami długości harmonogramu, sumy czasów zakończenia zadań i kosztu całkowitego. Problem ten opisujemy modelem kolorowania krawędzi różnych klas hipergrafów.

    Full text available to download

  • Sekwencyjne algorytmy antypodalnego kolorowania radiowego grafów.

    Praca zawiera charakterystykę suboptymalnych algorytmów antypodalnego kolorowania grafów, stanowiących adaptację algorytmów sekwencyjnych S, SL, LF stosowanych przy klasycznym kolorowaniu grafów. Dla tych algorytmów wskazano grafy dość trudne i trudne do pokolorowania (HC i SHC). Porównano ich funkcję dobroci i rozpiętości uzyskiwanych pokolorowań dla grafów o różnej gęstości krawędziowej.

  • Samostabilizujące się algorytmy wierzchołkowego kolorowania grafów.

    Publication

    - Year 2004

    Artykuł jest poświęcony kolorowaniu grafów w modelu rozproszonym. Podano schemat konstruowania samostabilizujących się algorytmów wierzchołkowego kolorowania grafów z możliwością nadawania wierzchołkom priorytetów. W oparciu o tę technikę skonstruowano samostabilizujący się algorytm LF który został szczegółowo opisany. Przeprowadzono również testy komputerowe porównując algorytm LF ze znanymi wcześniej algorytmami samostabilizującymi.

  • Zachłanne algorytmy kolorowania grafów w modelu rozproszonym

    W artykule porównano cztery rozproszone algorytmy kolorowania grafów. Zaprezentowano wyniki eksperymentów komputerowych, w których badano liczbę rund i kolorów uzyskanych dla grafów losowych.

  • Algorytm przybliżony dla cyrkularnego kolorowania krawędzi grafów

    W artykule autorzy proponują algorytm przybliżony dla cylkularnego kolorowania krawędzi grafu. Przedstawione są oszacowania na złożoność obliczeniową tego algorytmu, a także wyniki testów na grafach o małej liczbie wierzchołków jak i na grafach losowych.

  • Wybrane własności problemu routingu oraz kolorowania ścieżek w grafie.

    Publication

    - Year 2004

    Referat dotyczy zagadnienia ścieżkowego kolorowania grafu, które stanowi naturalny model dla problemu routingu i przydziału częstotliwości w czysto optycznej sieci światłowodowej. Opisano podstawowe zasady i właściwości ścieżkowego kolorowania grafów. Zaprezentowano wybrane twierdzenia, oparte w dużej mierze na wynikach badań własnych. Omówiono złożoność obliczeniową problemu routingu chromatycznego i kolorowania ścieżek zarówno...

  • Metaheurystyki dla problemu routingu oraz kolorowania ścieżek w grafie.

    Publication

    - Year 2004

    Referat dotyczy zagadnienia ścieżkowego kolorowania grafu, które stanowi naturalny model dla problemu routingu i przydziału częstotliwości w czysto optycznej sieci światłowodowej. Zagadnienie optymalizacyjne dla zadanego zbioru zgłoszeń polega na minimalizacji największej użytej wartości koloru ścieżki (tzw. liczby chromatycznej zbioru zgłoszeń). Opisano podstawowe zasady i właściwości ścieżkowego kolorowania grafów. Porównano...

  • Samostabilizujący się algorytm kolorowania grafów dwudzielnych i kaktusów

    Publication

    - Year 2006

    W 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.

  • Metody bezsiatkowe - nowe perspektywy zastosowania w geoinżynierii.Część II. Rozwiązanie zagadnienia Flamanta z zastosowaniem metody MLPG

    Publication

    W artykule przedstawiono praktyczny przykład zastosowania metody MLPG do klasycznego zagadnienia mechaniki gruntów. Rozważanym zagadnieniem jest fundament pasmowy na podłożu sprężystym (uogólnione zagadnienie Flamanta). Dla rozważanego problemu dobrano optymalne parametry funkcji multikwadratowych z bazą radialną, na których oparta jest interpolacja. Zbadano również dokładność obliczeniową w zależności od parametrów definiujących...

  • Zastosowanie algorytmów rojowych do kolorowania grafów

    Publication

    Przedstawiamy sposób adaptacji heurystycznej metody przeszukiwania PSO (ang. Particle Swarm Optimization) do znajdowania suboptymalnych pokolorowań wierzchołkowych grafów prostych. Prezentujemy sposób przeprowadzenia eksperymentów obliczeniowych oraz ich wyniki.

  • Eksperymenty z zastosowanie algorytmów genetycznych do problemu kolorowania grafów

    Publication

    - Year 2005

    Niniejsza praca przedstawia wykorzystanie algorytmów genetycznych (AG) do problemu kolorowania wierzchołków grafu (GCP). Przeprowadzono szereg symulacji mających na celu porównanie skuteczności operatorów krzyżownia, mutacji i selekcji oraz sposobu generacji i parametrów populacji. Uzyskane wyniki pokazały znaczną przewagę operatorów korzystających z wiedzy o problemie nad operatorami losowymi. Dla wybranej konfiguracji algorytmu...

  • Metody Informatyki Stosowanej

    Journals

    ISSN: 1898-5297

  • Algorytmy radiowego kolorowania grafów. XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych.

    W 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.

  • The complexity of equitable vertex coloring graphs

    Publication

    - 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.

  • Parallel scheduling by graph ranking

    Publication

    - Year 2006

    Nr dokum.: 73017Praca dotyczy jednego z nieklasycznych modeli kolorowania grafów - uporządkowanego kolorowania. Celem było uzyskanie wyników, które mogo być wykorzystane w praktycznych zastosowaniach tego modelu, do których należą: równoległe przetwarzanie zapytań w relacyjnych bazach danych, równoległa faktoryzacja macierzy metodą Choleskiego, równoległa asemblacja produktu z jego części składowych. W pracy wskazano uogólnienia...

  • A note on mixed tree coloring

    Publication

    - INFORMATION PROCESSING LETTERS - Year 2008

    Zaproponowano 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].

    Full text to download in external service

  • Szeregowanie zadań sprzężonych metodą kolorowania grafów

    Publication

    - Automatyka / Automatics - Year 2003

    Rozważono problem szeregowania zadań sprzężonych na pojedynczym procesorze w obecności ograniczeń kolejnościowych. Zidentyfikowano przypadki wielomianowe dla tego zagadnienia NP-trudnego.

  • Szeregowanie zadań metodami kolorowania grafów.Monografie 37.

    Publication

    - Year 2003

    Niniejsza praca poświęcona jest wykorzystaniu teorii chromatycznej grafów w szeregowaniu. Koncepcja ta polega na przedstawieniu zbioru zadań w postaci krawędzi tzw. grafu konfliktów.

  • Self-stabilizing algorithms for graph coloring with improved performance guarantees

    Publication

    - Year 2006

    W 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.

  • Self-stabilizing algorithm for edge-coloring of graphs

    Referat 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.

    Full text available to download

  • On the complexity of distributed greedy coloring

    Publication

    - Year 2007

    W 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.

    Full text to download in external service

  • Metody interdyscyplinarne

    Publication

    - Year 2015

    W rozdziale przedstawiono metody interdyscyplinarne jako złożenie metod ilościowych i jakościowych w zarządzaniu humanistycznym na przykładzie badań nad polskimi instytucjami akademickimi.

  • Generowanie sąsiedztwa w algorytmach lokalnych poszukiwań uporządkowanego kolorowania grafów

    Publication

    - Year 2006

    Przedstawienie rozwiązań problemów kombinatorycznych w postacipermutacji daje podstawy do konstrukcji algorytmów lokalnychposzukiwań. Uporządkowane pokolorowanie grafu można zapisać w postaci permutacji wierzchołków grafu. Podstawowe operacje prowadzącedo generowania sąsiedztwa rozwiązania to zamiana dwóch elementówlub przesunięcie elementu permutacji. W artykule wskazujemy metodępozwalającą na wykonanie takich operacji w czasie...

  • Planowanie rozmieszczenia strażników w galeriach sztuki metodą kolorowania grafów

    Publication
    • P. Żyliński

    - Year 2002

    W niniejszym rozdziale zaprezentujemy podejście chromatyczne do wyznaczenialiczby straży w galeriach dowolnego kształtu bez dziur oraz w galeriach or-togonalnych z dziurami, a także bez dziur. Rozważane tu problemy są NP-trud-ne pod względem złożoności obliczeniowej.

  • Easy and hard instances of arc ranking in directed graphs

    Publication

    Artykuł 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...

    Full text available to download

  • Metody analizy zapachu

    Publication

    Zmysł węchu to jeden z dwóch, oprócz smaku, zmysłów chemicznych. Istota tego zmysłu polega na umiejętności rozpoznawania i występowania zapachu określonych związków chemicznych lub ich mieszanin w otoczeniu. W artykule przedstawione zostały metody analizy zapachu m.in. metody klasycznej analizy sensorycznej, chromatografii gazowej połączonej z detekcją olfaktometryczną oraz elektroniczny nos.

  • Minimalizacja szerokości pasma w sieciach radiowych metodami szkieletowego kolorowania grafów

    Publication

    Artykuł 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.

  • ASYNCHRONICZNE METODY RADIOLOKALIZACYJNE

    Publication

    - Year 2018

    W pracy przedstawiono wybrane problemy lokalizowania obiektów w asynchronicznych sieciach radiowych. W pierwszej kolejności zostały zdefiniowane kryteria jakościowe do oceny efektywności pracy opracowanych metod oraz przedstawiono model symulacyjny, który został użyty do badań. W kolejnych trzech rozdziałach szczegółowo opisano trzy oryginalne asynchroniczne metody radiolokalizacyjne w różnych wariantach. Przeprowadzono analizę...

    Full text to download in external service

  • Metody badania struktury triacylogliceroli.

    Omówiono strukturę triacylogliceroli oraz liczbę możliwych kombinacji różnych triacylogliceroli w zależności od ilości występujących w nich kwasów tłuszczowych. Przedstawiono różne metody określania rozmieszczenia kwasów tłuszczowych w poszczególnych pozycjach cząsteczek triacylogliceroli. Pokazano metody enzymatyczne z zastosowaniem lipaz regio - i stereospecyficznych oraz metody wykorzystujące wysokosprawną chromatografię cieczową...

  • Metody pomiaru rezystancji uziemienia

    Publication

    - Year 2007

    W referacie przestawiono stosowane w praktyce metody pomiaru rezystancji uziemienia. Omówiono klasyczne metody pomiarowe oraz metody, które nie wymagają rozłączania zacisków kontrolnych, a nawet rozmieszczania sond pomiarowych na czas pomiaru. Zaprezentowano zasady pomiaru rezystancji uziemienia złożonych systemów uziemiających w stacjach elektroenergetycznych najwyższych napięć. Przedstawiono możliwości pomiaru rezystancji uziemienia,...

  • Metody pomiaru parametrów uziemień.

    Publication

    - Year 2004

    Omówiono metody pomiarów parametrów uziemień odgromowych metodami statycznymi, częstotliwościowymi i udarowymi.

  • Wybrane zastosowania niestandardowych modeli kolorowania w szeregowniu dwu-procesowych zadań jednostkowych

    Publication

    Niniejsza 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.

  • Metody wspomagania wyszukiwania informacji

    Publication

    - Year 2011

    Wyszukiwanie informacji analizowane może być z perspektywy użytkownika i w kontekście tego, jakie czynności może on podjąć, aby odnaleźć interesujące go informacje bez wsparcia ze strony analizatora języka. Użytkownicy stosują wyszukiwarki internetowe, jednak często nie są świadomi pełnego zakresu ich możliwości. Wyszukiwanie za pomocą wyszukiwarek polega na wprowadzaniu zapytań w polu tekstowym. Opracowane zostały liczne metody...

  • Szybkie metody spektroskopii impedancyjnej

    Publication

    - Year 2011

    W pracy przedstawiono metody i układy przyspieszające pomiary widma impedancji i identyfikację elementów układów zastępczych obiektów technicznych. Zostały one ukierunkowane na implementację w tanich przyrządach diagnostycznych nadających się do pracy w różnych warunkach, m. in. w terenie. Aby skrócić czas pomiaru impedancji zastosowano różne sygnały pobudzenia: harmoniczne, wieloharmoniczne, impuls prostokątny. Do identyfikacji...

  • Metody formułowania ontologicznych zapytań

    Artykuł dotyczy problemu wydobywania danych wyrażonych w postaci ontologii opisanej językiem Web Ontology Language. Dane takie mogą być wydobywane przy użyciu ontologicznych zapytań. Artykuł przedstawia rodzaje języków umożliwiających formułowanie tego rodzaju zapytań. Ontologiczne zapytania mogą być formułowane przez użytkowników podobnie jak zapytania w wyszukiwarkach internetowych tworzone w celu znajdowania stron internetowych....

    Full text available to download

  • METODY OGRZEWANIA ROZJAZDÓW KOLEJOWYCH

    Rozjazdy kolejowe są elementem dróg kolejowych o krytycznym znaczeniu dla zachowania bezpieczeństwa ruchu pojazdów szynowych w warunkach zimowych. W pracy przedstawiono współczesne metody ogrzewania rozjadów kolejowych.

    Full text to download in external service

  • Metody cyfrowego przetwarzania obrazów

    Publication

    - Year 2005

    W celu efektywnego wykorzystania obrazu jako źródła informacji należy przetworzyć go na postać cyfrową. Obraz cyfrowy stanowi punkt wyjścia dla komputerowego przetwarzania obrazów.Niniejsza książka prezentuje wybrane metody i problemy cyfrowego przetwarzania obrazów. Składa się z ośmiu rozdziałów i załączników, w których omawia się operacje na pikselach obrazu, histogramy, progowanie obrazów, filtry liniowe i nieliniowe, wykrywanie...

  • Wybrane metody wytwarzania nanoproszków

    Publication

    - Year 2012

    Przedstawione zostały trzy metody wytwarzania nanoproszków, które są jednymi z najczęściej wykorzystywanych technik: mielenie, zol-żel i piroliza. Cechuje je przede wszystkim prostota oraz możliwość wykorzystania tych technik na szerszą skalę.