Search results for: GRAFY WIĄZAŃ
-
Interval edge-coloring of graphs.
PublicationRozdział 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.
-
The relationship between entrepreneurship and economic growth: a review of recent research achievements
PublicationRozdział przedstawia przedląd najnowszych badań światowych dotyczących relacji zachodzących pomiędzy przedsiębiorczością a wzrostem gospodarczym. Autorzy prezentują własną propozycję ujęcia powiązań pomiędzy przedsiębiorczością a makroekonomicznymi efektami wzrostu z uwzględnieniem różnorodnych - tak zwanych - ''powiązań pośrednich''(intermediate linkages).
-
A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs
PublicationWe consider the CHROMATIC SUM PROBLEM on bipartite graphs which appears to be much harder than the classical CHROMATIC NUMBER PROBLEM. We prove that the CHROMATIC SUM PROBLEM is NP-complete on planar bipartite graphs with Delta less than or equal to 5, but polynomial on bipartite graphs with Delta less than or equal to 3, for which we construct an O(n(2))-time algorithm. Hence, we tighten the borderline of intractability for this...
-
Derandomizing random walks in undirected graphs using locally fair exploration strategies
PublicationW pracy rozważono problem eksploracji anonimowego nieskierowanego grafu przez bezpamięciowego robota. Zaprojektowane strategie eksploracji cechują się własnością lokalnej sprawiedliwości, tj. kolejne krawędzie trawersowane przez robota wybierane są na podstawie lokalnych informacji tak, aby zapewnić równomierne wykorzystanie krawędzi w sensie pewnego kryterium. Okazuje się, że odpowiedni dobór kryterium jest kluczowy do zapewnienia...
-
Model of speed-varing rotor for mechatronic systems analysis and design
PublicationW 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...
-
Hydrogen generation using solar energy
PublicationWodór jest uważany za alternatywne i odnawialne źródło energii. Bezpośrednie wykorzystanie światła słonecznego do fotokatalitycznego lub fotoelektrochemicznego rozkładu wody może zapewnić w przyszłości ekonomicznie uzasadnione, alternatywne źródło wodoru. W pierwszym etapie naszych badań został zaprojektowany i zbudowany hybrydowy, fotowoltaiczno-elektrochemiczny układ, dokonujący konwersji energii promieniowania słonecznego na...
-
n-butyl 2-(3-chloro-1,2-dihydropyrazin-2-ylidene)-2-cyanoacetate
PublicationStrukturę C11H12ClN3O2 wyznaczono metodą rentgenowskiej analizy strukturalnej. Geometria i długości wiązań w pierścieniu pirazynowym są typowe dla tej klasy związków. Cała cząsteczka, poza ogonem n-butylowym, jest płaska (r.m.s. 0.0131(1)Å). Występujące intramolekularne wiązanie wodorowe N2-H2BO1 tworzy S(6) pierścień stabilizując całą cząsteczkę. W sieci krystalicznej obserwuje się nieuporządkowanie statyczne dla reszty...
-
Structural properties of water: Comparison of the SPC, SPCE, TIP4P and TIP5P models of water
PublicationDla czterech najpopularniejszych modeli wody obliczono wartości entropii absolutnej ciekłej wody w temperaturze 298 K, średnią liczbę wiązań wodorowych tworzonych przez cząsteczkę wody, średni czas życia wiązania wodorowego, średni czas życia cząsteczki wody w stanie związanym (gdy tworzy ona co najmniej jedno wiązanie wodorowe) oraz średnią energię wiązania wodorowego. Otrzymane rezultaty porównano z eksperymentem. Uzyskane wyniki...
-
The structure of dimethylsulfoxide-solvated magnesium and calcium ions in solution and the solid state, and overview of the coordination chemistry of hydrated and solvated alkaline earth metal ions
PublicationOznaczono strukturę w stanie stałym i ciekłym solwatowanych jonów magnezu i wapnia w dimetylosulfotlenku. Stwierdzono, ze jony te tworzą sześciokoordynacyjne solwaty ze średnią długością wiązań Mg-O i Ca-O 2.062(4) i 2.303(5)A. Przegląd literaturowy ukazał, że jony berylu i magnezu we wszystkich rozpuszczalnikach tworzą odpowiednio cztero- i sześciokoordynacyjne solwaty, podczas gdy jony wapnia i strontu istnieją jako ośmiokoordynacyjne...
-
Wpływ odbiorników energii elektrycznej pojazduna parametry silnika spalinowego
PublicationW artykule przedstawiono model systemu energetycznego pojazdu napędzanego silnikiem spalinowym w postaci grafów wiązań (GW). W modelu tym uwzględniono szczególnie część elektryczną systemu składającą się z generatora, akumulatora elektrochemicznego i odbiorników energii elektrycznej. Podano zależności na podstawowe parametry systemu energetycznego w konwencji GW. W oparciu o przedstawioną w pracy [11] wielowymiarową charakterystykę...
-
Model procesu hamowania w pojeździe hybrydowym
PublicationW tradycyjnym procesie hamowania cała energia kinetyczna pojazdu jest rozpraszana do otoczenia w postaci energii cieplnej. W pojazdach hybrydowych istnieje możliwość odzyskania części tej energii przez przekazanie do akumulatorów i wykorzystania jej do napędu pojazdu. W pracy przedstawiono model energetyczny procesu hamowania pojazdu hybrydowego w układzie szeregowym, stosując metodę grafów wiązań (GW). Stosując konwencję GW podano...
-
Lucyna Nyka prof. dr hab. inż. arch.
PeopleLucyna Nyka (Ph.D., D.Sc., Prof.) is a Professor at the Faculty of Architecture, Gdańsk University of Technology, in 2008-2016 a Vice-Dean for Research, and since 2016 – Dean of the Faculty of Architecture. Her research interests focus on issues concerning water-related architecture and urban landscapes. She is the author and co-author of many projects focused on urban renewal. She was an author of the EU-founded (Audiovisual...
-
Szkodliwe dla zdrowia izomery trienowych kwasów tłuszczowych w mleku początkowym i następnym do żywienia niemowląt
PublicationZbadano zawartość kwasów tłuszczowych zawierających układ trzech sprzężonych wiązań podwójnych TCFA, szkodliwych dla zdrowia produktów oksydacji lipidów, w tłuszczu wolnym i w tłuszczu związanym mleka początkowego MP i następnego MN do żywienia niemowląt (5-ciu różnych producentów, łącznie 17 produktów). Liczbowo zawartość TCFA wyrażono umownie jako parametr K [%] będący stosunkiem absorbancji układu trzech sprzężonych wiązań podwójnych...
-
Persistent homology as a new method of the assessment of heart rate variability
PublicationHeart rate variability (hrv) is a physiological phenomenon of the variation in the length of the time interval between consecutive heartbeats. In many cases it could be an indicator of the development of pathological states. The classical approach to the analysis of hrv includes time domain methods and frequency domain methods. However, attempts are still being made to define new and more effective hrv assessment tools. Persistent...
-
Wykorzystanie klastrów do efektywnego i zrównoważonego rozwoju polskiej gospodarki morskiej
PublicationSzerokie zastosowanie ''klastrów'' jako nowoczesnych systemów zintegrowanych sieci powiązań społeczno-gospodarczych zrównoważonego rozwoju badanych obszarów. Przykłady zinterpretowanej sieci powiązań w polskiej gospodarce morskiej (przemysły morskie i racjonalne, zrównoważone obszary morskie i nadbrzeżne wzdłuż polskiego wybrzeża Bałtyku). Założenia programowe polskich klastrów.
-
Ionic liquids: predictions of physicochemical properties with experimental and/or DFT-calculated LFER parameters to understand molecular interactions in solution
PublicationPublikacja zawiera modele pozwalające na przewidywanie współczynnika podziału oktanol-woda (log P), rozpuszczalności w wodzie oraz krytycznego stężenia micelizacji (CMC) cieczy jonowych oraz współczynników aktywności anionowej i hydrofobowości w wodzie i w mieszaninie oktanolu z wodą. Modele oparte są na liniowych zależnościach energii swobodnej (LFER) i wykorzystują parametry zmierzone i/lub wyliczone na podstawie funkcjonalnej...
-
Bilans energetyczny w pojeździe hybrydowym z napędem szeregowym.
PublicationPrzedstawiono model pojazdu hybrydowego z napędem szeregowym sformułowany przy użyciu grafów wiązań (GW) i równań stanu (RS). Podano składowe bilansu energetycznego hybrydowego układu napędowego i zdefiniowano najważniejsze sprawności, które mogą posłużyć do oceny ogólnej sprawności eksploatacji pojazdu. Krótko opisano pojazd hybrydowy zbudowany w Politechnice Gdańskiej w celu przeprowadzenia weryfikacji eksperymentalnej modelu...
-
Algorytm konstruowania modeli matematycznych złożonych układów dynamicznych dla programu Simulink
PublicationW pracy omówiono metodę budowy modelu matematycznego w postaci schematu blokowego dla złożonych pod względem natury fizycznej układów. Istota proponowanej metody polega na tym, że równania opisujące układ wyprowadzane są w sposób tradycyjny. Jednak podejście energetyczne i podział badanego układu na podukłady - wielowrotniki pozwala na kontrolowane wyprowadzanie równań. Następnie, wykorzystując tę samą, co w grafach wiązań procedurę...
-
Modelowanie układów napędowych pojazdów z silnikami spalinowymi
PublicationW analizie struktur układów napędowych pojazdów wykorzystano metodę Grafów Wiązań, która daje możliwość modelowania elementów o różnej naturze fizycznej. Jest to bardzo istotne przy analizie energetycznej systemów o złożonej i zróżnicowanej strukturze energetycznej, np. w przypadku pojazdów samochodowych z klasycznym lub hybrydowym układem napędowym. W pracy przedstawiono również przykłady popularnych programów komputerowych do...
-
Optimising the sounding pulse of the rotational directional transmissionsonar
PublicationPrzedmiotem artykułu jest cyfrowa realizacja techniki ciągłego obrotu wiązki nadawczej w sonarach. W klasycznych rozwiązaniach analogowych polega ona na pobudzaniu elementów anteny hydroakustycznej sygnałami quasi-harmonicznymi o zmieniających się w czasie przesunięcia fazy. W cyfrowej realizacji zmienne w czasie przesunięcia fazy sprowadzają się do pobudzenia elementów anteny sygnałami harmonicznymi o specjalnie dobranych częstotliwościach...
-
Liczby Ramseya on-line dla różnych klas grafów
PublicationRozpatrujemy grę rozgrywaną na nieskończonej liczbie wierzchołków, w której każda runda polega na wskazaniu krawędzi przez jednego gracza - Budowniczego oraz pokolorowaniu jej przez drugiego gracza - Malarkę na jeden z dwóch kolorów, czerwony lub niebieski. Celem Budowniczego jest zmuszenie Malarki do stworzenia monochromatycznej kopii wcześniej ustalonego grafu H w jak najmniejszej możliwej liczbie ruchów. Zakładamy, że gracze...
-
Rola instytucji wspierających rozwój regionalny (w tym agencji rozwoju regionalnego) w systemie wdrażania nowej polityki regionalnej
PublicationSystem instytucjonalny polityki regionalnej w Polsce jest niekompletny. Istniejące Agencje Rozwoju Regionalnego są rozmieszczone nierównomiernie i są bardzo zróżnicowane. Kierunek zmian powinien wiązać się z innowacjami. Takie są rekomendacje OECD i praktyka niektórych krajów UE. Opis autorskiej koncepcji Regionalnych Agencji Partnerstwa
-
Badania naprężeń własnych laserowo przetopionej stali X20Cr13
PublicationPrzedstawiono badania naprężeń własnych stali X20Cr13 przetopionej wiązką lasera CO2 o dwóch różnych energiach liniowych. Przetapianie wiązką lasera o energii liniowej 16,7 Ws/m3 powodowało większe naprężenia w kierunku prostopadłym do kierunku przetopienia podczas gdy przetapianie z energią 70,8 Ws/m3 powoduje sytuację odwrotną.
-
Dynamics of Field Line Mappings in Magnetic Flux Tubes
PublicationWe study the topological constraints on the dynamics of magnetic field lines in flux tubes. Our approach is based on the application of the topological invariant: fixed point index. We consider periodic flux tubes and find various restrictions on the field lines that come from the sequence of fixed point indices of iterations. We also analyze the case of a tube with a cylindrical obstacle, deducing some special dynamical properties...
-
Kompozytowe materiały poliuretanowo-gumowe otrzymywane z lanych elastomerów uretanowych i recyklatów gumowych
PublicationW pracy prezentujemy wyniki badań dotyczących nowej grupy kompozytowych materiałów poliuretanowo-gumowych (KPG), otrzymywanych przy udziale różnej ilości recyklatu gumowego (RG), w których jako osnowę wykorzystano opracowane w Katedrze Technologii Polimerów Politechniki Gdańskiej lane nienasycone poliestrouretany (PEUR), poddawane rodnikowej kopolimeryzacji sieciującej ze styrenem. Zastosowanie PEUR umożliwiło uzyskanie nowej grupy...
-
Model biznesu przedsiębiorstwa wodociągowego
PublicationW artykule przedstawiono badania nad wartościami modelu biznesu przedsiębiorstw wodociągowych w Polsce oraz przeprowadzono dyskusję nad ich postrzeganiem przez same przedsiębiorstwa. Wartości te w wielu aspektach postrzegane są w zbliżony sposób przez klientów. O ile jednak przedsiębiorstwa, jako istotne wartości postrzegały elementy związa-ne ze sprawnością i ciągłością procesu o tyle klienci kładli nacisk na sferę społeczną doty-czącą...
-
Nowa wizja dla gdańskiej Wyspy Spichrzów
PublicationArtykuł obejmuje analize proponowanych obecnie rozwiązań w zakresie zagospodarowania obszaru gdańskiej Wyspy Spichrzów. Omówiono w nim koncepcję stworzoną przez S. Fiszera jako syntezy prac warsztatowych, prowadzonych w ciągu ostatniego roku przez firmę GRAY International.
-
Chiralne i achiralne struktury supramolekularne z udziałem oksamidów i ich pochodnych tiokarbonylowych
PublicationCelem pracy była synteza serii oksamidów oraz ich analogów tio- i ditiokarbonylowych, a następnie zbadanie zdolności tych związków do samoorganizacji w kryształach oraz kokryształach z innymi substancjami. Istotnym elementem tych badań było ustalenie wpływu chiralności cząsteczek na sposób ich upakowania w sieci krystalicznej. Ponadto długofalowa absorpcja tiopochodnych umożliwiła przeprowadzenie studiów spektroskopowych otrzymanych...
-
Problemy odwzorowywania ontologii opartych na logice opisowej w schemat relacyjnej bazy danych.
PublicationArtkuł prezentuje ogólną koncepcję odwzorowywania ontologii opartych na logice opisowej na schemat relacyjnej bazy danych i dane zapisane zgodnie z tym schematem. przedstawia również istniejące podejścia wykorzystujące metody powiązań słabych i powiązań silnych. Prezentuje zalety i wady opisywanych metod, jak również pojawiające się w nich problemy i ograniczenia.
-
Paired bondage in trees
PublicationW pracy zdefiniowano pojęcie liczby zniewolenia parami jako moc najmniejszego zbioru krawędzi, którego usunięcie z grafu spowoduje wzrost liczby dominowania parami. W szczególności scharakteryzowane są wszystkie drzewa, w których liczba zniewolenia wynosi 0, czyli takie, w których usunięcie dowolnego podzbioru krawędzi nie zwiększy liczby dominowania parami.
-
Kolorowanie hipergrafów
PublicationHipergraf to struktura stanowiąca pewne uogólnienie grafu. Oprócz tradycyjnych krawędzi dwuelementowych dopuszcza ona także krawędzie, które zawierają inną, przeważnie większą liczbę wierzchołków. W tej pracy pokażemy kilka modeli kolorowania hipergrafów, takich jak kolorowanie krawędzi, kolorowanie wierzchołków i tzw. CD-kolorowanie, przedstawimy ich podstawowe własności oraz wskażemy zastosowania.
-
Robustness of the Rotor-router Mechanism
PublicationW 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''). Przeanalizowano czas stabilizacji agenta do trajektorii w postaci cyklu Eulera w przypadku wystąpienia zaburzeń w grafie: usunięcie krawędzi, dodanie krawędzi, lokalna zamiana portów
-
Distributed largest-first algorithm for graph coloring.
PublicationW 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.
-
Detekcja obiektów graficznych i ekstrakcja ich parametrów
PublicationW rozdziale przedstawiono wybrane metody wykrywania obiektów na obrazach, a także sposoby ich opisywania za pomocą parametrów umożliwiających późniejszą klasyfikację. Zaprezentowano algorytmy analizy obrysu obiektu (podział linii brzegowej na tokeny, wykorzystanie symetrii) oraz analizy tekstury (NxM-gramy, lokalne wzorce, filtry Gabora), omówiono także wykrywanie obiektów metodą AdaBoost.
-
Żywice epoksydowe i poliuretany - wzajemne oddziaływania modyfikujące. Cz. II. Przenikające się sieci polimerowe (IPN).
PublicationNa podstawie przeglądu literatury przedstawiono sposoby wzajemnej modyfikacji żywic epoksydowych (EP) i poliuretanów (PUR) prowadzące do tworzenia przenikających się sieci polimerowych (IPN) oraz szczepionych sieci polimerowych(graf-IPN).Podstawowym celem modyfikacji EP jest poprawa ich elastyczności...
-
Rozproszone kolorowanie grafów
PublicationW pracy rozważany jest rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowe, rozproszone algorytmy kolorowania grafów wraz z dokładną analizą teoretyczną i wynikami eksperymentów obliczeniowych.
-
Compact scheduling of zero-one time operations in multi-stage systems.
PublicationRozważamy szeregowanie zwarte na maszynach dedykowanych z zero-jedynkowymi operacjami w modelu otwartym, przepływowym i mieszanym. Harmonogramy zostały zmodelowane przy pomocy pokolorowań krawędzi grafu konfliktów z pewnymi dodatkowymi ograniczeniami. Dowodzimy NP-trudności problemów w przypadku ogólnym oraz prezentujemy przegląd znanych wielomianowych algorytmów szeregujących dla systemów o specyficznej budowie.
-
Ordinal Pattern Statistics for RR Intervals during Head-Up Tilt Test in Patients with the History of Vasovagal Syncope
PublicationWe apply ordinal pattern analysis to quantify differences in distribution of patterns of length 3 and 4 in basal state and during head-up tilt test (HUTT) in patients with the history of syncope and positive (HUTT(+)) or negative (HUTT(-)) responses to the test. We identify the patterns related to prevalence of sympathetic or parasympathetic cardiac modulation as well as describe the relations between the response to the test and...
-
Ordinal pattern statistics for the assessment of heart rate variability
PublicationThe recognition of all main features of a healthy heart rhythm (the so-called sinus rhythm) is still one of the biggest challenges in contemporary cardiology. Recently the interesting physiological phenomenon of heart rate asymmetry has been observed. This phenomenon is related to unbalanced contributions of heart rate decelerations and accelerations to heart rate variability. In this paper we apply methods based on the concept...
-
Differentiating patients with obstructive sleep apnea from healthy controls based on heart rate-blood pressure coupling quantified by entropy-based indices
PublicationWe introduce an entropy-based classification method for pairs of sequences (ECPS) for quantifying mutual dependencies in heart rate and beat-to-beat blood pressure recordings. The purpose of the method is to build a classifier for data in which each item consists of two intertwined data series taken for each subject. The method is based on ordinal patterns and uses entropy-like indices. Machine learning is used to select a subset...
-
Images of apples for the use of the Viola-Jones method. Data set no. 2 - grey scale
Open Research DataThe database contains pictures of apples made at different angles, from different sides and containing different varieties. In this way, two bases of apple images were created (each database contains 1,100 images). This set is data set no. 2 - grey scale: processed images in shades of gray. The photos were prepared for the best possible detection process...
-
Ustalenie prędkości zderzenia w oparciu o zakres uszkodzeń samochodu z wykorzystaniem metod energetycznych – badania pilotażowe
PublicationW artykule przedstawiono omówienie możliwości technicznych mierzenia profi lu odkształcenia samochodu powypadkowego przy użyciu specjalnie do tego celu zaprojektowanego i wykonanego przyrządu pomiarowego. Przyrząd ten zastosowany w metodzie grafi cznej wyznaczania wartości pracy deformacji, powoduje zwiększenie wykorzystania metod energetycznych jako niezwykle istotnych w praktyce opiniowania szczególnie trudnych i złożonych zdarzeń...
-
Algorytmy radiowego kolorowania grafów. XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych.
PublicationW 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.
-
Complixity results on open shop scheduling to minimize total cost of operations
PublicationW 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.
-
Chapter 2: Modelling and analysis of rotor with magnetic bearing system
PublicationThe paper is concerned with rotor magnetic bearing system modelling. Such system is a relatively complex electromechanical system and can be considered as typical mechatronic one. The port-based modelling of physical systems has been used to obtain discrete-continuous model of considered system. Proposed approach enables to obtain reduced low-order lumped parameter representation of the system including gyroscopic interactions....
-
Supramolecular structures of bis-thionooxalamic acid esters derived from (±)-cyclohexane-1,2-diamine and (±)-1,2-diphenylethylenediamine
PublicationZsyntezowano dwa racemiczne estry kwasu bis(tiooksamowego) i zbadano ich sposób upakowania w sieci krystalicznej. Analiza rentgenograficzna monokryształów badanych związków wykazała, że organizują się one w jednowymiarowe struktury, które tworzone są przez molekuły o przeciwnej chiralności, połączone za pomocą trójcentrowych wiązań wodorowych C=S...NH...O=C. Powstające agregaty są dodatkowo stabilizowane przez słabe oddziaływania...
-
Wspomagana komputerowo weryfikacja określonego poziomu nienaruszalności bezpieczeństwa sil z wykorzystaniem autorskiej aplikacji ProSIL
PublicationW referacie przedstawiono oprogramowanie Pro SIL wspomagające zarządzanie bezpieczeństwem funkcjonalnym. Program ProSIL składa się z trzech modułów wspomagających: określanie wymaganego poziomu SIL (moduł ProSILen) weryfikację SIL (moduł ProSILer) oraz przeprowadzenie analizy warstw zabezpieczeń metodą LOPA. W aplikacji ProSIL zaimplementowano opracowaną w trakcie badań metodykę analizy bezpieczeństwa funkcjonalnego w projektowaniu...
-
Cost minimisation in unbounded multi-interface networks
PublicationW pracy badano problem odłączania niektórych urządzeń komunikacyjnych w wielointerfejsowych sieciach bezprzewodowych w taki sposób, by zapewnić realizację wymaganego grafu połączeń przy jednoczesnej minimalizacji zużycia energii. Sformułowano problem optymalizacyjny, podano wyniki dotyczące jego trudności i zaproponowano algorytmy optymalizacyjne dla wariantu, w którym liczba interfejsów komunikacyjnych jest potencjalnie nieograniczona...
-
NP-completeness of convex and weakly convex domiating set decision problems.
PublicationLiczby dominowania wypukłego i słabo wypukłego są nowymi rodzajami liczb dominowania. W tym artykule pokazujemy, że problemy decyzyjne dominowania wypukłegi i słabo wypukłego są NP-zupełne w przypadku grafów dwudzielnych oraz split grafów. Posługując się zmodyfikowanym algorytmem Washalla możemy w czasie wielomianowym określić, czy dany podzbiór wierzchołków grafu jest spójny bądź słabo spójny.
-
Analiza przybliżonego algorytmu dla problemu szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym.
PublicationW 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.