Wyszukiwarka
Filtry
wszystkich: 358
wybranych: 273
-
Katalog
Filtry wybranego katalogu
Wyniki wyszukiwania dla: IGRAFX
-
Szeregowanie identycznych zadań na czterech procesorach jednorodnych z dwudzielnymi grafami konfliktów
PublikacjaRozważono problem szeregowania n zadań jednostkowych na 4 procesorach jednorodnych o szybkościach s1>=s2>=s3>=s4. Celem szeregowania jest utworzenie najkrótszego możliwego harmonogramu. Zadania podlegają ograniczeniom zasobowym mówiącym, że niektóre pary zadań nie mogą być wykonane na tym samym procesorze. Podajemy algorytm dokładny, który rozwiązuje problem w czasie liniowym, o ile graf niezgodności jest kubiczny. Ponadto podajemy...
-
Periodic expansion in determining minimal sets of Lefschetz periods for Morse–Smale diffeomorphisms
PublikacjaWe apply the representation of Lefschetz numbers of iterates in the form of periodic expansion to determine the minimal sets of Lefschetz periods of Morse–Smale diffeomorphisms. Applying this approach we present an algorithmic method of finding the family of minimal sets of Lefschetz periods for Ng, a non-orientable compact surfaces without boundary of genus g. We also partially confirm the conjecture of Llibre and Sirvent (J Diff...
-
Generalized Dold sequences on partially-ordered sets
PublikacjaDold sequences constitute an important class of integer sequences that play an important role in combinatorics, number theory, topology and dynamical systems. We generalize the notion of Dold sequence for the case of partially ordered sets and describe their properties. In particular we give two alternative descriptions of generalized Dold sequences: by some class of elementary sequences as well as by different...
-
Computations of the least number of periodic points of smooth boundary-preserving self-maps of simply-connected manifolds
PublikacjaLet $r$ be an odd natural number, $M$ a compact simply-connected smooth manifold, $\dim M\geq 4$, such that its boundary $\partial M$ is also simply-connected. We consider $f$, a $C^1$ self-maps of $M$, preserving $\partial M$. In [G. Graff and J. Jezierski, Geom. Dedicata 187 (2017), 241-258] the smooth Nielsen type periodic number $D_r(f;M,\partial M)$ was defined and proved to be equal to the minimal number of $r$-periodic points...
-
Dold sequences, periodic points, and dynamics
PublikacjaIn this survey we describe how the so-called Dold congruence arises in topology, and how it relates to periodic point counting in dynamical systems.
-
Directed laplacian kernels for link analysis
PublikacjaPrzedstawiono zastosowanie algorytmów opartych o funkcje jądra do problemu analizy linków i cytowań. Zaproponowano nowe funkcje jądra zbudowane na operatorze Laplace'a dla grafów skierowanych. Odzwierciedlają one powiązanie pomiędzy węzłami grafu jako funkcję długości łączących je ścieżek oraz istotności odwiedzanych po drodze węzłów. Eksperymenty z nowymi funkcjami jądra przeprowadzono na zbiorze cytowań pobranych z publikacji...
-
Total restrained bondage in graphs
PublikacjaPodzbiór D zbioru wierzchołków grafu nazywamy zewnętrznie totalnym dominującym w grafie, jeśli każdy wierzchołek spoza D ma sąsiada zarówno w D jak i poza D. Moc najmniejszego zbioru o tej własności nazywamy liczbą dominowania zewnętrznie totalnego. W artykule badamy wpływ usuwania krawędzi na liczbę dominowania zewnętrznie totalnego, czyli liczbę zewnętrznego totalnego zniewolenie w grafach.
-
Ograniczone (p1, p2,...,pk) kolorowanie wierzchołków grafów.
PublikacjaProblem ograniczonego (p1,...,pk) kolorowania grafów polega na poszukiwaniu odpowiedzi na pytanie, czy istnieje takie pokolorowanie wierzchołków grafu , że krotności użycia poszczególnych barw są równe ustalonym progom p1,...,pk. W ogólnym przypadku problem ten, jako uogólnienie klasycznego kolorowania grafów pozostaje NP-zupełnym. W pracy przedstawiamy wyniki dotyczące ograniczonego kolorowania split grafów, kografów oraz...
-
Optimal and safe control planning with the use of discrete optimization
PublikacjaW opracowaniu zaproponowano metodę projektowania optymalnych i tolerujących uszkodzenia systemów sterowania opartych na wykorzystaniu algorytmów optymalizacji dyskretnej. Publikacja przedstawia potencjalne wady i zalety metody. Główna idea proponowanego algorytmu sprowadza się do wykorzystania struktury grafu przepływowego w celu stworzenia reprezentacji dynamiki własnej danego procesu. Poszukiwana trajektoria optymalna, jeśli...
-
Hipergrafowy model szeregowania w rozrzedzonych systemach zadań wieloprocesorowych
PublikacjaHipergrafem nazywamy pewne uogólnienie grafu, w którym krawędzie mogą zawierać dowolnie wiele wierzchołków. Model taki pozwala symulować rozmaite zjawiska praktyczne oraz teoretyczne. W tym artykule będziemy mówić o kolorowaniu krawędzi hiperdrzew. Pokażemy jaki jest indeks chromatyczny dla tej klasy hipergrafów oraz jaki jest sumacyjny indeks chromatyczny dla hiperdrzew prostych. Zademonstrujemy także wielomianowe algorytmy szukające...
-
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...
-
Entropy Measures in the Assessment of Heart Rate Variability in Patients with Cardiodepressive Vasovagal Syncope
PublikacjaSample entropy (SampEn) was reported to be useful in the assessment of the complexity of heart rate dynamics. Permutation entropy (PermEn) is a new measure based on the concept of order and was previously shown to be accurate for short, non-stationary datasets. The aim of the present study is to assess if SampEn and PermEn obtained from baseline recordings might differentiate patients with various outcomes of the head-up tilt test...
-
Applications of computational intelligence techqniues to acoustics
PublikacjaCelem artykułu jest przegląd wybranych zastosowań metod inteligentnych w akustyce, a w szczególności w szeroko rozumianej inżynierii dźwięku. Przedstawione badania i eksperymenty były prowadzone w oparciu o sztuczne sieci neuronowe, metodę zbiorów przybliżonych, logiką rozmytą, grafy przepływowe Pawlaka oraz algorytmy genetyczne. Rozwiązywane problemy dotyczyły klasyfikacji dźwięków muzycznych, rozpoznawania fraz muzycznych, przetwarzania...
-
Total outer-connected domination numbers of trees
PublikacjaNiech G=(V,E) będzie grafem bez wierzchołków izolowanych. Zbiór wierzchołków D nazywamy zbiorem dominującym totalnym zewnętrznie spójnym jeżli każdy wierzchołek grafu ma sąsiada w D oraz podgraf indukowany przez V-D jest grafem spójnym. Moc najmniejszego zbioru D o takich własnościach nazywamy liczbą dominowania totalnego zewnątrznie spójnego. Praca m.in. zawiera dolne ograniczenie na liczbę dominowania totalnego zewnętrznie spójnego...
-
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.
-
Metoda grafów wiązań w zastosowaniu do opracowania szczególnego obwodu elektrycznego
PublikacjaGrafy wiązań wykorzystano do odwzorowania krwiobiegu nerki. Zaproponowany model, uwzględnia również odcinek tętnicy głównejoraz, w uproszczeniu, dystrybucję krwi do pozostałych segmentów krwiobiegu. Opisanie zjawisk przepływu krwi w naczyniach krwionośnych za pomocą grafów wiązań pozwala w łatwy sposób przejść do modelu w postaci obwodu elektrycznego. Sprowadzenie problemu dystrybucji krwi do modelu elektrycznego umożliwia zastosowanie...
-
Cost minimization in wireless networks with a bounded and unbounded number of interfaces
PublikacjaPraca dotyczy problemu minimalizacji energii poprzez selektywne odłączanie urządzeń komunikacyjnych w wielointerfejsowych sieciach bezprzewodowych w taki sposób, by zapewnić realizację wymaganego grafu połączeń. Sformułowano problem optymalizacyjny, podano wyniki dotyczące jego trudności i zaproponowano algorytmy optymalizacyjne. Rozważono zarówno wariant, w którym liczba interfejsów komunikacyjnych jest parametrem stałym (narzuconym...
-
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.
-
Eksperymenty z zastosowanie algorytmów genetycznych do problemu kolorowania grafów
PublikacjaNiniejsza 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...
-
Shub’s conjecture for smooth longitudinal maps of S^m
PublikacjaLet f be a smooth map of the m-dimensional sphere Sm to itself, preserving the longitudinal foliation. We estimate from below the number of fixed points of the iterates of f , reduce Shub’s conjecture for longitudinal maps to a lower dimensional classical version, and prove the conjecture in case m = 2 and in a weak form for m = 3.
-
Generating sequences of Lefschetz numbers of iterates
PublikacjaDu, Huang and Li showed in 2003 that the class of Dold–Fermat sequences coincides with the class of Newton sequences, which are defined in terms of socalled generating sequences. The sequences of Lefschetz numbers of iterates form an important subclass of Dold–Fermat (thus also Newton) sequences. In this paper we characterize generating sequences of Lefschetz numbers of iterates.
-
Periodic Points for Sphere Maps Preserving MonopoleFoliations
PublikacjaLet S^2 be a two-dimensional sphere. We consider two types of its foliations with one singularity and maps f:S^2→S^2 preserving these foliations, more and less regular. We prove that in both cases f has at least |deg(f)| fixed points, where deg(f) is a topological degree of f. In particular, the lower growth rate of the number of fixed points of the iterations of f is at least log|deg(f)|. This confirms the Shub’s conjecture in...
-
Periodic points of latitudinal maps of the $m$-dimensional sphere
PublikacjaLet f be a smooth self-map of the m-dimensional sphere Sm. Under the assumption that f preserves latitudinal foliations with the fibres S1, we estimate from below the number of fixed points of the iterates of f. The paper generalizes the results obtained by Pugh and Shub and by Misiurewicz.
-
Topological-numerical analysis of a two-dimensional discrete neuron model
PublikacjaWe conduct computer-assisted analysis of a two-dimensional model of a neuron introduced by Chialvo in 1995 [Chaos, Solitons Fractals 5, 461–479]. We apply the method of rigorous analysis of global dynamics based on a set-oriented topological approach, introduced by Arai et al. in 2009 [SIAM J. Appl. Dyn. Syst. 8, 757–789] and improved and expanded afterward. Additionally, we introduce a new algorithm to analyze the return times...
-
Attractors of dissipative homeomorphisms of the infinite surface homeomorphic to a punctured sphere
PublikacjaA class of dissipative orientation preserving homeomorphisms of the infinite annulus,pairs of pants, or generally any infinite surface homeomorphic to a punctured sphere isconsidered. We prove that in some isotopy classes the local behavior of such homeomor-phisms at a fixed point, namely the existence of so-called inverse saddle, impacts thetopology of the attractor — it cannot be arcwise connected
-
Anonymous agreed order multicast: performance and free riding
PublikacjaPrzedstawiono protokół rozgłaszania wiadomości dla sieci lokalnych z usługą 1C, zapewniający całkowite uporządkowanie wiadomości przy zachowaniu anonimowości stacji. Wykorzystywane są raporty zawierające grafy częściowego uporządkowania wiadomości, otrzymywane na podstawie kolejności odbioru i wnioskowania o bezpośrednim następstwie par wiadomości. Wskazano, że kolektywna odpowiedzialność za utrzymanie stałego rytmu raportów sprzyja...
-
Metoda szybkiego wyznaczania par węzłowo rozłącznych tras dla ochrony transmisji unicast
PublikacjaW celu ochrony transmisji przed awarią węzłów/łączy wykorzystuje się alternatywne trasy transmisji. Jednakże, złożoność obliczeniowa dostępnych algorytmów doboru tras rozłącznych często istotnie wstrzymuje producentów sprzętu od implementacji tychże rozwiązań. W pracy prezentujemy nowe podejście wyznaczania par rozłącznych tras bazujące na transformacji grafu sieci w meta strukturę. Wyniki badań odnośnie czasu wyznaczania tras...
-
Programowanie dynamiczne w rozwiązywaniu problemów szeregowania zadań w systemach o acyklicznej strukturze
PublikacjaRozważono rozrzedzone systemy niepodzielnych zadań dwuprocesorowych o jednostkowych długościach operacji oraz systemy maszyn dedykowanych (open shop,flow shop, mixed shop) o operacjach zero-jedynkowych. Przedstawiono rodzinę wielomianowych algorytmów opartych na programowaniu dynamicznym, pozwalających na znalezienie optymalnego uszeregowania względem szerokiej rodziny funkcji kryterialnych. Stopień rozrzedzenia systemu zdefiniowano...
-
Network Approach to Increments of RR-intervals for Visualization of Dynamics of Cardiac Regulation
PublikacjaThe transition network for RR -increments is pre- sented in a directed and weighted graph, with vertices represent- ing RR -increments and edges corresponding to the order in a sequence of increments. The adjacency matrix and the transition matrix of this network provide a graphical tool which could be useful in the assessment of cardiac regulation. As an example, the method is applied in detecting differences between diurnal activity...
-
Temporal Changes in Complexity of Cardiovascular Regulation during Head-Up Tilt Test by Entropic Measures of Fluctuations of Heart Period Intervals and Systolic Blood Pressure
PublikacjaTemporal changes in complexity of cardiovascular regulation during head-up tilt test by entropic measures of fluctuations of heart period intervals and systolic blood pressure
-
Lefschetz periodic point free self-maps of compact manifolds
PublikacjaLet f be a self-map of a compact connected manifold M. We characterize Lefschetz periodic point free continuous self-maps of M for several classes of manifolds and generalize the results of Guirao and Llibre [J.L.G. Guirao, J. Llibre, On the Lefschetz periodic point free continuous self-maps on connected compact manifolds, Topology Appl. 158 (16) (2011) 2165-2169].
-
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.
-
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...
-
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...
-
Żywice epoksydowe i poliuretany - wzajemne oddziaływania modyfikujące. Cz. II. Przenikające się sieci polimerowe (IPN).
PublikacjaNa 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
PublikacjaW 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.
-
Optymalne pokolorowania średnicowe dla wybranych klas grafów
PublikacjaW pracy opisano wybrane właściwości szczególnego przypadku radiowego kolorowania grafów, zwanego kolorowaniem średnicowym. Podano zasadę działania algorytmu optymalnego kolorowania średnicowego i oszacowania liczby średnicowej grafu w przypadku ogólnym oraz dla ścieżek i cykli. Korzystając z podanego algorytmu, znaleziono dokładne wartości liczby średnicowej dla ścieżek i cykli niewielkiej długości, co pozwoliło na obalenie wcześniej...
-
ProSIL Software for functional saferty management in life cycle = Aplikacja ProSIL do zarządzania bezpieczeństwem funkcjonalnym w cyklu życia
PublikacjaIn the paper the ProSIL software to aid the functional safety management is presented. The software consists of three modules to aid: determination of the required SIL level (ProSILen), veryfication of the SIL level (ProSILver). In the aplication the method of the calibrated risk graph to determine the required safety integrity level SIL for defined safety instrumented functions is applied. The methods concerning functional safety...
-
Algebraic periods and minimal number of periodic points for smooth self-maps of 1-connected 4-manifolds with definite intersection forms
PublikacjaLet M be a closed 1-connected smooth 4-manifolds, and let r be a non-negative integer. We study the problem of finding minimal number of r-periodic points in the smooth homotopy class of a given map f: M-->M. This task is related to determining a topological invariant D^4_r[f], defined in Graff and Jezierski (Forum Math 21(3):491–509, 2009), expressed in terms of Lefschetz numbers of iterations and local fixed point indices of...
-
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ć...
-
An interactive system for mobile robot navigation
PublikacjaW pracy przedstawiono interaktywny system do zdalnego sterowania robotem mobilnym zbudowany przy użyciu języka VRML. System jest wspomagany przez algorytm wyznaczania optymalnej trajektorii ruchu robota mobilnego poruszającego się w obecności przeszkód statycznych. Otoczenie reprezentowane jest przez graf nieskierowany. W metodzie wykorzystano algorytm Dijkstry.
-
A self-stabilizing algorithm for finding a spanning tree in a polynomial number of moves
PublikacjaW 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 znajdowania drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm dla tego problemu z gwarantowaną wielomianową liczbą ruchów.
-
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...
-
Heurystyczne algorytmy szeregowania zadań wieloprocesorowych na procesorach dedykowanych
PublikacjaProblem szeregowania zadań wieloprocesorowych na procesorach dedykowanych można zaprezentować przy pomocy modelu kolorowania krawędzi hipergrafów. Hipergrafem nazywamy pewne uogólnienie grafu, w którym krawędzie mogą zawierać dowolnie wiele wierzchołków. Model taki pozwala symulować rozmaite zjawiska praktyczne oraz teoretyczne. Kolorowanie hiperkrawędzi hipergrafów jest uogólnieniem kolorowania krawędzi grafów, zatem jest problemem...
-
Metaheurystyki dla 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. 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...
-
Modelowanie, analiza i synteza układów dynamicznych z zastosowaniem grafów wiązań
PublikacjaWyprowadzono związek pomiędzy grafami wiązań i grafami Coatesa oraz wskazano obszar zastosowań tego sposobu interpretacji modelu w postaci grafu wiązań. Przedstawiono następujące zagadnienia:wyprowadzanie transmitancji, równań stanu i równań 2. rzędu;synteza układu o założonej impedancji;zastosowanie grafów wiązań i Coatesa w metodzie transmitancji układów ciągłych;konstruowanie modalnych grafów wiązań układów dyskretno-ciągłych.Zaprezentowane...
-
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
PublikacjaW pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.
-
Inferring perfect phylogenies with restrictions on character state transitions
PublikacjaZnana z klasycznej literatury metoda rekonstrukcji drzewa filogenetycznego zbioru gatunków na podstawie ich cech analizowanych w modelu doskonałej filogenezy często okazuje się niewystarczająca ze względu na założenia tego modelu, zmuszające do pominięcia znanych biologom informacji. W pracy definiujemy rozszerzenie umożliwiając wprowadzenie dla każdej cechy grafu skierowanego dopuszczalnych przejść ewolucyjnych pomiędzy jej stanami....
-
Synchronization helps robots to detect black holes in directed graphs
PublikacjaPraca zawiera nowe wyniki dla problemu poszukiwania czarnej dziury w grafie skierowanym przez zbiór agentów. Czarna dziura jest węzłem niszczącym wszystkich wchodzącej do niej agentów. Pokazano, że w przypadku, gdy stopień wejściowy czarnej dziury wynosi D, do przeszukania grafu skierowanego w modelu synchronicznym wystarcza O(D 2^D) agentów. Wartość ta jest bliska znanemu z literatury oszacowaniu dolnemu Omega (2^D). W pracy pokazano...
-
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ł...