Filtry
wszystkich: 605
-
Katalog
Wyniki wyszukiwania dla: EKSTREMALNA TEORIA GRAFÓW
-
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...
-
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.
-
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.
-
Studia Aurea-Revista de Literatura Espanola y Teoria Literaria del Renacimiento y Siglo de Oro
Czasopisma -
The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree
PublikacjaW pracy pokazano, że problem L(p,q)-kolorowania przy użyciu ''t'' kolorów jest NP-zupełny nawet w wersji ograniczonej do grafów planarnych dwudzielnych małego stopnia, nawet dla stosunkowo niewielkich wartości ''t''. Jako wniosek z uzyskanych wyników stwierdzono, że problem L(2,1)-kolorowania grafów planarnych przy użyciu 4 kolorów jest NP-zupełny, a także że problem L(p,q)-kolorowania grafów o maksymalnym stopniu 4 jest NP-zupełny...
-
Symulacje algorytmów rozsyłania i plotkowania dla sieci radiowych
PublikacjaAnalizowane były dwa podstawowe problemy komunikacji grupowej w sieciach radiowych - rozsyłanie i plotkowanie. W ramach symulacji zaimplementowanych zostało łącznie kilkanaście algorytmów dla tych problemów. Praca opisuje wyniki symulacji - ilościowe porównanie długości transmisji generowanych przez poszczególne algorytmy dla grafów losowych oraz dla kilku podstawowych klas grafów.
-
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.
-
Mode interaction in few-mode optical fibres with Kerr effect
PublikacjaUogólnioną metodę rzutowania do ortogonalnej bazy funkcji poprzecznej współrzędnej Bessela stosuje się do wyprowadzania układów równań nieliniowych Schrodingera. Teoria jest ważna dla paczek falowych w światłowodach i kilku modelach.
-
Moddeling urban processes based on requirements ofself-organization theory.
PublikacjaW artykule przedstawiono ogólne podstawy symulacji rozwoju urbanistycznego w oparciu o modele komórkowe. Nowa teoria, wykorzystująca aparat matematyczny stworzony do badań i modelowania dynamiki układów nieliniowych, rozszerza również możliwości poznawcze i wykorzystanie systemów GIS w szeroko pojmowanym planowaniu przestrzennym. Jej szybki rozwój w ostatnich latach i niezwykłe osiągnięcia w poznaniu procesów rządzących podstawową...
-
Koala graph coloring library: an open graph coloring library for real-world applications
PublikacjaPomimo intensywnej pracy naukowej na polu kolorowania grafów, nie jest znana kompletna i dedykowana biblioteka programistyczna. Celem artykułu jest zaproponowanie architektury takiej biblioteki. Celem jest spełnienie oczekiwań wypływających z rzeczywistych zastosowań, w szczególności spełnienie potrzeb wydajnościowych. Zaimplementowano szereg algorytmów cheurystycznego kolorowania grafów. Przyjętym językiem programowania jest C++....
-
NP-completeness of convex and weakly convex domiating set decision problems.
PublikacjaLiczby 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.
-
Zdzisław Kowalczuk prof. dr hab. inż.
OsobyW 1978 ukończył studia w zakresie automatyki i informatyki na Wydziale Elektroniki Politechniki Gdańskiej, następnie rozpoczął pracę na macierzystej uczelni. W 1986 obronił pracę doktorską, w 1993 habilitował się na Politechnice Śląskiej na podstawie pracy Dyskretne modele w projektowaniu układów sterowania. W 1996 mianowany profesorem nadzwyczajnym, w 2003 otrzymał tytuł profesora nauk technicznych. W 2006 założył i od tego czasu...
-
The complexity of the T-coloring problem for graphs with small degree.
PublikacjaW pracy ustalono złożoność obliczeniową problemu optymalnego kolorowania grafów o ustalonym stopniu.
-
Weakly connected domination critical graphs
PublikacjaPraca dotyczy niektórych klas grafów krytycznych ze względu na liczbę dominowania słabo spójnego.
-
Rank Coloring of Graphs.
PublikacjaRozdział jest poświęcony uporządkowanemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
Sum Coloring of Graphs.
PublikacjaRozdział jest poświęcony sumacyjnemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
Grafo-mania, czyli rzecz o grafach i algorytmach. Problem 8 hetmanów
PublikacjaW eseju spojrzano na problem 8 hetmanów na szachownicy z punktu widzenia teorii grafów
-
Feliks Koneczny o cywilizacjach
PublikacjaArtykuł przedstawia zarys teorii cywilizacji opracowanej przez Feliksa Konecznego (1862-1949). Teoria ta zakłada, że najdoskonalszą formą cywilizacji jest cywilizacja łacińska oparta na religii katolickiej. W artykule wskazano również na kontekst idologiczny teorii F. Koniecznego.
-
Lower bound on the domination number of a tree.
PublikacjaW pracy przedstawiono dolne ograniczenie na liczbę dominowania w drzewach oraz przedstawiono pełną charakterystykę grafów ekstremalnych.
-
Relacje w edukacyjnym kształtowaniu teorii i praktyki inżynierskiej
PublikacjaRozważono wzajemne zależności i współdziałanie pomiędzy teorią i praktyką w kształtowaniu zawodowej działalności inżynierów - zakładając, że teoria jest równoznaczna z kreatywnym myśleniem. Aby móc wykształcić intelektualnie dojrzałych ludzi techniki, niezbędna jest edukacja respektująca wysokie standardy wykształcenia ogólnego.
-
Wpływ teorii chaosu na niektóre tradycyjne stanowiska ontologiczne oraz na spór o redukcjonizm
PublikacjaTeoria chaosu stanowi nie tylko nowy paradygmat w nauce, ale także inspirację do badań filozoficznych nad rzeczywistością. W artykule podjęto próbę zarysowania głównych założeń teorii chaosu oraz określenia jej wpływu na niektóre tradycyjne stanowiska ontologiczne oraz spór o redukcjonizm. Z punktu widzenia ontologii, w dynamice nieliniowej szczególnie interesujący jest powrót do ciągłościowego monoizmu w opozycji do atomizmu....
-
Projektowanie środowiskowe - edukacja architektoniczna
PublikacjaPrzedstawiono krytykę obecnej edukacji architektonicznej oraz dyskusję nad kierunkami jej zmian. Omówiono dokumenty międzynarodowych organizacji zajmujących się teoria i praktyką edukacji architektonicznej ze szczególnym uwzględnieniem edukacji w zakresie projektowania środowiskowego oraz systemów samoksztalcenia (learning to learn) i kształcenia ustawicznego.
-
Acoustic radiation force and streaming caused by non periodic acousticsource.
PublikacjaTeoria i obliczenia numeryczne przepływu rotacyjnego (''streamingu'') towarzyszącemu fali akustycznej w przepływach lepkich nieliniowych. Fala wywołująca może być nieokresowa: impulsowa lub paczka falowa itd. Przykład pojedynczego pulsu rozpatrywany. Ilustracje delikatnej struktury czasowej powstania fal rotacyjnych przedstawione na rysunkach.
-
Acoustic streaming caused by modulated sound and wave packets.
PublikacjaRozpatruje się powstanie pola wirowego na skutek nieliniowej propagacji fali akustycznej w środowiskach z lepkością. Teoria odwołuje się do fal akustycznych nieokresowych, w odróżnieniuod teorii klasycznej. Obliczenia numeryczne na podstawie nowych wzorów są porównywane z wynikami teorii klasycznej.
-
Static and dynamic approach of social roles identification using PISNA and subgraphs matching
PublikacjaIdentyfikacja ról w sieci społecznej jest jednym z podstawowych zagadnień analiza takich sieci. W artykule przedstawiamy nowe podejście do tego zagadnienia. Pokazujemy w jaki sposób można dokonać identyfikacji ról poprzez tworzenie specjalnych struktur grafowych tzw. grafów wzorcowych. Przy definiowaniu tychże grafów wspieramy się metodą PISNA. Proponujemy statyczne i dynamiczne podejście do identyfikacji ról. Pokazujemy, w jaki...
-
Interaction of modes in nonlinear acoustics: theory and applications to pulse dynamics.
PublikacjaOgólna teoria oddziaływania modów hydrodynamicznych opiera się na wyprowadzeniu równań różniczkowych nieliniowych. Mody rozumiane są tu jako wektory własnych układów praw zachowań hydrodynamicznych. Rozpatrywano zjawiska towarzyszące fali akustycznej w przepływie lepkim nieliniowym. Uwzględniono płyny w każdym fizycznym równaniu stanu.
-
All graphs with restrained domination number three less than their order
PublikacjaW pracy opisana jest rodzina wszystkich grafów, dla których liczbadominowania zewnętrznego jest o trzy mniejsza od ich rzędu.
-
A note on fast approximate backbone coloring of split graphs with star--like backbones
PublikacjaDla grafu G = (V, E) z wyróżnionym podgrafem H, kolorowanie szkieletowe jest zdefiniowane jako odwzorowanie c spełniające |c(u) - c(v)| > 1 dla każdej krawędzi z E(H) oraz |c(u) - c(v)| > 0 dla każdej krawędzi z E(G). W pracy przedstawiono 1-przybliżony algorytm kolorowania szkieletowego split grafów ze skojarzeniem w szkielecie o złożoności O(|V|) oraz 1-przybliżony algorytm dla split grafów z rozłącznymi gwiazdami w szkielecie.
-
Chromatyczne szeregowanie zadań w cyklicznych systemach produkcyjnych.
PublikacjaGłównym celem pracy jest klasyfikacja złożoności obliczeniowej problemu szeregowania zadań w przypadku cyklicznej pracy systemu produkcyjnego. Rozważane są przy tym trzy modele szeregowania: system zadań dwuprocesorowych, system otwarty i system przepływowy. Kryterium optymalizacyjnym które jest analizowane jest długość cyklu wyrażająca częstość realizacji poszczególnych zestawów operacji. W pracy posługiwano się teorią grafów...
-
MORSE Teoria Morse'a w układach hamiltonowskich
ProjektyProjekt realizowany w Zakład Układów Dynamicznych zgodnie z porozumieniem UMO-2016/23/G/ST1/04081 z dnia 2018-01-03
-
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.
-
Antypodalna radiowa liczba chromatyczna grafu.
PublikacjaOpisane 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ń.
-
Some integral transforms and their applications
PublikacjaMotywacją napisania pracy były równania różniczkowe cząstkowe z odchyleniem przy pochodnych. Ponieważ w tym przypadku nie funkcjonuje teoria charakterystyk, więc badamy nowe przekształcenia całkowe w celu znalezienia odpowiedniej aproksymacji jednostajnej lub średniokwadratowej dla zagadnienia Cauchy`ego. Przedstawiamy również eksperymenty numeryczne oparte na zmodyfikowanej metodzie Galerkina.
-
Szeregowanie zadań metodami kolorowania grafów.Monografie 37.
PublikacjaNiniejsza 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.
-
T-coloring of graphs.
PublikacjaNiniejszy rozdział omawia kontrastowe kolorowanie grafów. Podana została jego definicja i podstawowe własności, zastosowania oraz złożoność obliczeniowa problemów rozważanych w ramach tej dziedziny.
-
DEM-FEM model of highly saturated soil motion due to seepage force
PublikacjaArtykuł poświęcono nowej propozycji rozwiązania problemu modelowania zjawiska transportu, które występuje wewnątrz wysoko-nawodnionego gruntu ziarnistego na skutek ciśnienia spływowego. Teoria oparta została na połączeniu metody elementów skończonych (FEM - Finite Element Method) - rozwiązania równań poro-elastycznych oraz metody poszczególnych elementów (DEM - Distinct Element Method), które dały podwójny model numeryczny. FEM...
-
Wybrane własności problemu routingu oraz kolorowania ścieżek w grafie.
PublikacjaReferat 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...
-
Wydajność jako czynnik sukcesu przedsiębiorstwa wykorzystującego metodologię TOC na przykładzie zakładu produkującego beton komórkowy
PublikacjaAutorka pragnie skupić się na problemie wydajności i wykazać znaczenie narzędzi służących poprawie efektywności procesu produkcyjnego na przykładzie zakładu wytwarzającego beton komórkowy. Tezą postawioną w niniejszym referacie jest możliwość usprawnienia organizacji i logistyki produkcji poprzez wykorzystanie metody zarządzania, jaką jest Teoria Ograniczeń (ang. Theory of Constraints - TOC).
-
Tribology of bone tissue culture in bioreactor.
PublikacjaOpracowano system tribologiczny powstających sił tarcia w bioreaktorze. Pomimo, że wartości sił tarcia osiągają wartości poniżej 0,1 N to mają one decydujący wpływ na wartość porostu tkanki. Mechanika opływu tkanki cieczą o właściwościach biologicznych nienewtonowskich oraz hydrodynamiczna teoria opływu warstwy przyściennej jest bazą wyznaczania parametrów trybologicznychniniejszej pracy.
-
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.
-
Piotr Bartłomiejczyk dr hab.
OsobyW roku 2014 zostałem zatrudniony w Katedrze Równań Różniczkowych i Zastosowań Matematyki na Wydziale Fizyki Technicznej i Matematyki Stosowanej Politechniki Gdańskiej. Zajmuję się badaniem niezmienników występujących w analizie nieliniowej. W roku 2000 uzyskałem stopień naukowy doktora w zakresie nauk matematycznych w Instytucie Matematycznym Polskiej Akademii Nauk w Warszawie. Uchwałą Rady Wydziału Matematyki, Fizyki i Informatyki...
-
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...
-
Minimalizacja krotności użycia kolorów przy uporządkowanym kolorowaniu krawędzi drzew
PublikacjaUporządkowane kolorowanie grafu polega na takim etykietowaniu jego wierzchołków liczbami naturalnymi, że każda ścieżka łącząca dwa wierzchołki o tym samym kolorze zawiera wierzchołek o kolorze wyższym. O uporządkowanym pokolorowaniu mówimy, że jest optymalne, jeśli liczba wykorzystanych kolorów jest minimalna. W referacie rozważano optymalne uporządkowane kolorowanie z dodatkowym warunkiem, aby krotność użycia koloru, który pojawił...
-
Nauczanie bioinżynierii z zastosowaniem narzędzi informatycznych i metod stosowanych w elektrotechnice oraz grafach wiązań
PublikacjaPrzedstawiono sposoby badań zjawisk zachodzących w krwiobiegu za pomocą obwodów elektrycznych oraz grafów wiązań. Symulacje zjawisk stanowią jeden z elementów nauczania bioinżynierii dla studentów uczelni technicznych.
-
Cztery algorytmy, które wstrząsnęły światem. Część III: Sprzęt czy oprogramowanie
PublikacjaW ostatniej części tryptyku poruszamy problem przyjaznego rysowania grafów oraz prezentujemy algorytmy dla szybkiego mnożenia macierzy. Nasze rozważania kończymy ilustracją postępu w dziedzinie sprzętu i oprogramowania
-
Kolorowanie końcówkowe multidrzew
PublikacjaW pracy przedstawiono nowy model kolorowania grafów, mianowicie kolorowanie końcówkowe. Naszkicowano związki łączące ten model z klasycznymi modelami kolorowania oraz przedstawiono wielomianowy algorytm optymalnie końcówkowo kolorujący multidrzewa.
-
Modelling of distributed-lumped parameter systems by application of modal bond graphs.
PublikacjaZastosowano metodę transmitancji układów o parametrach rozłożonych oraz dekompozycję modalną do modelowania wybranych układów dynamicznych. Zaproponowane podejście pozwala otrzymać dokładne modele niskiego rzędu w postaci grafów wiązań.
-
XXX Wieczór z Ekonomią
WydarzeniaJubileuszowe spotkanie Wieczoru z Ekonomią odbędzie się we wtorek 3.03.20 r. o godz. 18:00 w sali 318/319 na WZiE. Gościem będzie dr Paweł Umiński. Temat spotkania: „Nowoczesna Teoria Monetarna MMT".
-
Modelling of energy flow in electrical machines. A bond graph approach
PublikacjaPrzedstawiono w ujęcia grafów wiązań model przepływu energii/mocy w maszynach elektrycznych pracujących w hybrydowych systemach przetwarzania energii. Jako przykład do rozważań przyjęto system napędu trakcyjnego pojazdów hybrydowych.
-
Consensus models: Computational complexity aspects in modern approaches to the list coloring problem
PublikacjaArtykuł poświęcony jest nowym modelom konsensusowego kolorowania grafów. Artykuł zawiera omówienie trzech takich modeli, analizę ich złożoności obliczeniowej oraz wielomianowy algorytm dla częściowych k-drzew, dla tzw. modelu addytywnego.