Filtry
wszystkich: 622
-
Katalog
Wyniki wyszukiwania dla: ALGORYTMICZNA TEORIA GRAFÓW
-
On the theory and numerical simulation of acoustic and heat modes interaction in a liquid with bubbles: acoustic quasi-solitons
PublikacjaTeoria rzutowania zaburzenia ogólnego na mody. Zastosowanie metody do badań układu równań typu Korteweg`a-de Vries`a. Rozwiązania analityczne i simulacje numeryczne.
-
Adama Smitha filozofia moralności (cz. 1)
PublikacjaOmówiono filozofię moralności Adama Smitha (1723-1790) wyłożoną w jego dziele "Teoria uczuć moralnych", w tym koncepcję sympatii i bezstronnego obserwatora.
-
Kolorowanie ścieżek w grafach
PublikacjaZdefiniowano podstawowe pojęcia niezbędne do analizy problemu wyboru i kolo-rowania ścieżek w grafach. Dokonano przeglądu wyników dla grafów ogólnych idla klasycznych rodzin grafów. Omówiono zastosowania praktyczne problemu,zwłaszcza związane ze wspomnianymi już sieciami optycznymi.
-
Path Coloring and Routing in Graphs.
PublikacjaW rozdziale omówione zostały problemy kolorowania ścieżek i routingu w grafach. Podano podstawowe definicje związane z tymi problemami, znane wyniki wraz z dyskusją złożoności obliczeniowej dla grafów ogólnych i dla kilku podstawowych klas grafów oraz zastosowania.
-
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.
-
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...
-
Packing three-vertex paths in a subcubic graph
PublikacjaW pracy rozważany jest problem pakowania scieżek P3 w grafach podkubicznych, pokazano oszacowania dolne na ilość ścieżek w zależności od stopnia spójności grafu oraz minimalnego stopnia.
-
On bounded load routings for modeling k-regular connection topologies
PublikacjaW pracy analizowane są problemy modelowania k-regularnych topologii sieci komputerowych z punktu widzenia routingu typu point-to-point. Zaprezentowane są algorytmy oraz przeprowadzona jest analiza złożoności obliczeniowej.
-
From Pathwidth to Connected Pathwidth
PublikacjaW pracy przedstawiono dowód faktu, że spójna szerokość ścieżkowa grafu wynosi co najwyżek 2k+1, gdzie k jest jego szerokością ścieżkową. Dowód jest konstruktywny, tzn., został skonstruowany algorytm, który dla podanej na wejściu dekompozycji grafu o szerekości k zwraca dekompozycję spóją o szerekości co najwyżej 2k+1.
-
Approximate search strategies for weighted trees
PublikacjaW pracy podajemy 3-przybliżony algorytm dla problemu spójnego przeszukiwania drzew ważonych.
-
Finding small-width connected path decompositions in polynomial time
PublikacjaA connected path decomposition of a simple graph $G$ is a path decomposition $(X_1,\ldots,X_l)$ such that the subgraph of $G$ induced by $X_1\cup\cdots\cup X_i$ is connected for each $i\in\{1,\ldots,l\}$. The connected pathwidth of $G$ is then the minimum width over all connected path decompositions of $G$. We prove that for each fixed $k$, the connected pathwidth of any input graph can be computed in polynomial-time. This answers...
-
Cops, a fast robber and defensive domination on interval graphs
PublikacjaThe game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”,...
-
Building a Nest by an Automaton
PublikacjaA robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid $Z x Z$. Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the {\em field}, is initially connected. The (Manhattan) distance between the farthest cells of the field is called its {\em span}. The robot...
-
Connected searching of weighted trees
PublikacjaW pracy pokazano, że problem spójnego przeszukiwania drzew ważonych jest silnie NP-zupełny. Problem pozostaje trudnym dla drzew z jednym wierzchołkiem o stopniu większym niż 2. Ponadto, przedstawiony został wielomianowy optymalny algorytm dla klasy drzew z ograniczonym stopniem.
-
Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines
PublikacjaArtykuł podejmuje problem szeregowania zadań przy założeniu podziału czasu na sloty jednakowej długości, gdzie każde z zadań ma ustaloną długość oraz czas jego zakończenia, który jest relatywny do końca slotu. Problem znalezienia uszeregowania polega na dokonaniu przydziału zadań do poszczególnych slotów, przy czym w ogólności długość zadania może wymuszać sytuację, w której zadańie jest realizowane nie tylko w slocie, w którym...
-
Drawing maps with advice
PublikacjaW pracy podejmujemy temat konstrukcji algorytmu dla agenta, który zostaje umieszczony w dowolnym wierzchołku grafu (wierzchołki są nierozróżnialne, krawędzie mają etykiety portów), po czym realizuje algorytm zmierzający do znalezienia drzewa spinającego grafu lub izomorficznej kopii grafu. Dla obu problemów podajemy asymptotycznie dokładne lub prawie dokładne oszacowania na ilość bitów dodatkowej informacji, którą agent musi otrzymać...
-
Connected searching of weighted trees
PublikacjaW artykule rozważamy problem spójnego przeszukiwania drzew obciążonych. Autorzy w [L. Barriere i inni, Capture of an intruder by mobile agents, SPAA'02 (2002) 200-209] twierdzą, że istnieje wielomianowy algorytm dla problemu obliczania optymalnej strategii przeszukiwania obciążonego drzewa. W niniejszej pracy pokazano, że problem ten jest obliczeniowo trudny nawet dla wierzchołkowo-obciążonych drzew (wagi krawędzi równe 1) oraz...
-
Kolorowanie hipergrafów
PublikacjaHipergraf 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.
-
Przechwytywanie obiektów poruszających się z ograniczoną prędkością
PublikacjaKrawędziowa liczba przeszukiwawcza grafu informuje nas ilu mobilnych agentów, przykładowo jednostek policji, jest niezbędnych do przechwycenia poruszającego się z dowolnie dużą prędkością uciekiniera w danym grafie. Podczas praktycznych zastosowań modelu w systemach bezpieczeństwa rzadko jednak spotyka się jednostki poruszające się z nieograniczoną prędkością. W pracy tej pokazujemy, że agenci mogą wykorzystać fakt ograniczonej...
-
Scanning networks with cactus topology
PublikacjaThe family of Pursuit and Evasion problems is widelystudied because of its numerous practical applications,ranging from communication protocols to cybernetic andphysical security. Calculating the search number of a graphis one of most commonly analyzed members of this problemfamily. The search number is the smallest number of mobileagents required to capture an invisible and arbitrarily fastfugitive, for instance piece of malicious...
-
An experimental study of distributed algorithms for graph coloring.
PublikacjaW pracy podano algorytm rozproszonego kolorowania grafówi porównano ze znanym wcześniej algorytmem.
-
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.
-
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ą...
-
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...
-
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.
-
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.
-
Sum Coloring of Graphs.
PublikacjaRozdział jest poświęcony sumacyjnemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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
-
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...