Wyszukiwarka
Wyniki wyszukiwania dla: KOLOROWANIE GRAFÓW PRZEDZIAŁOWYCH
-
Analiza przybliżonego algorytmu dla problemu szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym.
PublikacjaW pracy rozważamy kombinatoryczny problem MERST polegający na szukaniu, dla danego grafu, drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym. Dla ogólnych grafów problem MERST jest NP-trudny. W pracy zaproponowano nową funkcję dobroci dla pewnego przybliżonego algorytmu rozwiązującego powyższy problem i przeprowadzono doświadczenia komputerowe w celu porównania nowej z wcześniej znaną funkcją dobroci.
-
Jak transportować produkty chemiczne, czyli przypadek wsadowego szeregowania zadań kompatybilnych
PublikacjaPokazano, że pewien problem transportu produktów chemicznych może być sprowadzony do problemu szeregowania identycznych zadań kompatybilnych na wsadowych maszynach jednorodnych i rozwiązany metodami kolorowania grafów. Ponieważ problem ten jest NP-trudny, zbadano przypadki szczególne, które dają się rozwiązać w czasie kwadratowym. Rozważania ogólne są wsparte doświadczeniami komputerowymi zebranymi w trakcie implementacji wybranych...
-
Zastosowanie programów Mathematica i 20-sim do modelowania i analizy układów o parametrach rozłożonych
PublikacjaCelem pracy jest zaprezentowanie zastosowania pojęcia transmitancji układów o parametrach rozłożonych do konstruowania modalnych grafów wiązań dla układów zawierających jednowymiarowe podukłady o parametrach rozłożonych. Zaprezentowano sposób i efekty zastosowania programów Mathematica (do przygotowania parametrów modeli) i programu 20-Sim (do konstruowania modeli i do symulacji) w procesie modelowania i analizy układów zawierających...
-
Euler tour lock-in problem in the rotor-router model
PublikacjaW pracy rozważano model eksploracji grafu nieskierowanego przez pojedynczego agenta, w którym sterowanie agentem odbywa się zgodnie z zasadą ''rotor-router'' (inaczej: ''Propp machine''). Porównano czas stabilizacji agenta do trajektorii w postaci cyklu Eulera dla różnych klas grafów, prowadząc rozważania w kontekście teorii gier. Przydział początkowych portów i wskaźników w modelu jest traktowany jako rozgrywka pomiędzy graczem...
-
Graph decomposition for improving memoryless periodic exploration
PublikacjaW ostatnich latach często badanym problem jest eksploracja anonimowych grafów z lokalnymi etykietami portów przy każdym wierzchołku. Niedawno pokazano [Czyzowicz et al., Proc. SIROCCO'09], że dla każdego grafu istnieje poetykietowanie prowadzące do eksploracji przez automat bezpamięciowy z okresem co najwyżej 13n/3. W niniejszej pracy poprawiamy to ograniczenie do 4n-2, stosując całkowicie nową technikę dekompozycji grafu.
-
Modele typu ''czarna skrzynka'' elektrycznych elementów napędu hybrydowego
PublikacjaOpisano opracowany przy zastosowaniu grafów wiązań (GW) i równań stanu (RS) model pojazdu hybrydowego. Uzasadniono potrzebę stworzenia uproszczonych modeli maszyn elektrycznych i akumulatora elektrochemicznego i przedstawiono koncepcję modelu w postaci "czarnej skrzynki", w którym uwzględniono jedynie związki między parametrami energetycznymi na wejściu i wyjściu elementu. Podano przykłady zastosowania tego podejścia do modelu...
-
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...
-
Packing [1,Delta]-factors in graphs of small degree
PublikacjaRozważano problem znalezienia w grafie zadanej liczby k krawędziowo rozłącznych [1,Delta]-faktorów, gdzie Delta oznacza stopień grafu. Problem ten można rozwiązać w czasie liniowym dla k=2, jest on jednak NP-trudny dla każdego k>=3. Pokazano, że wariant minimalizacjny problemu dla k=2 jest NP-trudny dla grafów planarnych podkubicznych, jednak w ogólności istnieje algorytm (42 Delta - 30) / (35 Delta - 21) - aproksymacyjny.
-
Wyznaczanie sygnału sterowania silnikiem dla zadanych parametrów ruchu pojazdu.
PublikacjaW pracy zaprezentowano model układu napędowego pojazdu w formie grafów wiązań i równań stanu. Przedstawiono również model oporów ruchu pojazdu. Wyszczególniono parametry sterowania pojazdem oraz parametry określające ruch pojazdu. W pracy zawarto schemat wyznaczania parametru sterowania silnikiem, którego uzyskanie dla zadanych parametrów ruchu pojazdu jest niezbędnym elementem badań symulacyjnych i weryfikacyjnych opracowywanych...
-
On the complexity of distributed graph coloring with local minimality constraints
PublikacjaArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Omówiono algorytmy rozproszone, dające w wyniku pokolorowanie spełniające warunki dla pokolorowań sekwencyjnych typu S oraz Largest-First (LF). Udowodniono również, że każda rozproszona implementacja algorytmu S wymaga co najmniej Omega(log n / log log n) rund, a algorytmu LF co najmniej Omega (n^{1/2}) rund, gdzie n oznacza liczbę wierzchołków grafu.
-
Symulacja pracy mechanizmu prasującego pojazdu do usuwania odpadów z pojemników (PUOP)
PublikacjaW pracy przedstawiono analizę pracy wybranego typu mechanizmu prasującego PUOP oraz wpływ różnych konfiguracji elementów składowych tego urządzenia na energochłonność pracy w warunkach przyjętego cyklu obciążenia. W tym celu wykorzystano model mechanizmu prasującego PUOP w formie grafów wiązań oraz wyniki pomiarów ciśnienia roboczego w siłownikach hydraulicznych mechanizmu prasującego w trakcie jednego pełnego cyklu pracy przeprowadzonych...
-
Modele i algorytmy dla grafowych struktur defensywnych
PublikacjaW niniejszej pracy przeprowadzono analizę złożoności istnienia struktur defensywnych oraz równowag strategicznych w grafach. W przypadku struktur defensywnych badano modele koalicji defensywnych, zbiorów defensywnych i koalicji krawędziowych - każdy z nich w wersji globalnej, tj. z wymogiem dominacji całego grafu. W przypadku modeli równowagi strategicznej badano równowagę strategiczną koalicji defensywnych, równowagę strategiczną...
-
Sztuczne systemy immunologiczne w optymalizacji dyskretnej
PublikacjaSztuczne systemy immunologiczne to modele komputerowe oparte na niektórych właściwościach systemu odpornościowego kręgowców. Znajdują one szereg zastosowań m. in. w optymalizacji dyskretnej. Praca ta przedstawia informacje na temat trzech modeli obliczeniowych inspirowanych funkcjonowaniem układu immunologicznego, ich podstaw biologicznych i moŜliwych zastosowań. Artykuł zawiera opis algorytmu selekcji klonalnej w wersji optymalizacyjnej...
-
Model chłodnicy płytowej pracującej w układzie chłodzenia samochodowego silnika spalinowego
PublikacjaW artykule przedstawiono zastosowanie chłodnic płytowych w nowoczesnych układach chłodzenia silników spalinowych. uzasadniono potrzebę budowy modelu chłodnicy pozwalającego na przeprowadzenie badań symulacyjnych w nieustalonych warunkach pracy silnika samochodowego. Jako metodę modelowania przyjęto metodę grafów wiązań i równań stanu. Przyjęta metoda pozwala na powiązanie modelu chłodnicy z elementami systemu energetycznego silnik-pojazd,...
-
Kompleksowy model nowej generacji układu chłodzenia silnika spalinowego
PublikacjaPrzedstawiono tendencje w konstrukcji układów chłodzenia i dostępne komercyjne metody modelowania pracy układu chłodzenia. Przeprowadzono obliczenia symulacyjne temperatury cieczy komercyjnym programem komputerowym AmeSIM i porównano wyniki z pomiarami wykonanymi na hamowni podwoziowej. Opisano wybrane procesy wymiany ciepła występujące w układach chłodzenia. Przedstawiono ogólny model elementu cieplnego w postaci grafów wiązań...
-
program verification strategy and edge ranking of graphs
PublikacjaW artykule rozważamy model, w którym zakładamy, że dany jest zbiór asercji/testów dla pewnych bloków programu. Celem jest znalezienie optymalnej, tzn. wymagającej wykonania minimalnej liczby testów strategii wyszukiwania błędu w kodzie programu. Pomimo założenia w modelu, iż program posiada dokładnie jeden błąd, rozważania można uogólnić na testowanie kodu z dowolną liczbą błędów. Analizujemy teoretyczne własności tego modelu oraz...
-
Szkoła letnia na WETI
WydarzeniaKatedra Algorytmów i Modelowania Systemów WETI organizuje szkołę letnią pt.: "Gdansk Summer School of Advanced Science on Algorithms for Discrete Optimization" dla osób zainteresowanych algorytmiką i teorią grafów.
-
Model formalny dla problemu lokalizacji błędów w kodzie programu
PublikacjaIstnieje szereg sposobów badania poprawności programów komputerowych. W niniejszym referacie podejmujemy problem automatycznego testowania oprogramowania przy założeniu, iż dany jest zbiór testów (asercji) dla poszczególnych fragmentów kodu. Dla uproszczenia analizy zakładamy, że badany fragment kodu zawiera dokładnie jeden błąd, co nie zmniejsza ogólności rozważań. W artykule analizujemy praktyczne aspekty powyższego problemu...
-
Model of speed-varing rotor for mechatronic systems analysis and design
PublikacjaW artykule przedstawiono sposób modelowania złożonych układów mechatronicznych w oparciu o metodę grafów wiązań. Celem zilustrowania metody posłużono się przykładem liczbowym, w którym rozważano wirnik obracający się ze zmienną prędkością kątową. Prezentowana metodyka doskonale nadaje się do modelowania układów o zróżnicowanej naturze fizycznej. Otrzymany model ma charakter obiektu o pewnej liczbie wejść i wyjść, który można w...
-
Detection of roles of actors in social networks using the properties of actors' neighborhood structure.
PublikacjaArtykuł opisuje metodę identyfikacji ról aktorów sieci społecznej. Metoda ta może być szczególnie przydatna w sieciach społecznych, o których posiadamy ograniczoną wiedzę, głównie zawężoną do lokalnych powiązań pomiędzy aktorami. Przedstawiona w artykule metoda korzysta z grafu relacji społecznych, algorytmu identyfikacji ról oraz zbioru grafów wzorców relacji. Rozwiązanie zostało przetestowane w społeczności użytkowników serwisu...