Publikacje
Filtry
wszystkich: 518
Katalog Publikacji
-
Non-isolating bondage in graphs
PublikacjaA dominating set of a graph $G = (V,E)$ is a set $D$ of vertices of $G$ such that every vertex of $V(G) \setminus D$ has a neighbor in $D$. The domination number of a graph $G$, denoted by $\gamma(G)$, is the minimum cardinality of a dominating set of $G$. The non-isolating bondage number of $G$, denoted by $b'(G)$, is the minimum cardinality among all sets of edges $E' \subseteq E$ such that $\delta(G-E') \ge 1$ and $\gamma(G-E')...
-
Minimum order of graphs with given coloring parameters
PublikacjaA complete k-coloring of a graph G=(V,E) is an assignment F: V -> {1,...,k} of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number χ(G) and achromatic number ψ(G), respectively),...
-
Construction of phylogenetic trees with topological constraints
PublikacjaThis paper proposes a method of reconstruction of phylogenetic trees based on heuristic search with topological constraints. Using topological constraints it is possible to reduce the set of solutions as well as to enforce that the result is consistent with a given hypothesis about the evolution process within some group of species. Along with this work a number of algorithms used for phylogenetic analysis were implemented. Those...
-
Analysis of elementary cellular automata using the theory of conflict
PublikacjaThe paper contains decomposition of elementary cellular automata (ECA in short) to subsystems that are defined according to a new theory called theory of conflict (ToC in short). The decomposition is a completely new approach to analysis of ECA and complex systems in general.
-
Porównanie wydajności modyfikacji algorytmu Proof-number search uwzględniających wartości remisowe
PublikacjaProof-number search to znana rodzina algorytmów służących do wyznaczania wartości pozycji w nielosowych grach dwóch graczy z pełną informacją. W wersji podstawowej pn-search doskonale radzi sobie z wyszukiwaniem strategii wygrywającej jednego z graczy. Jednak istnieje wiele znanych gier, w których obydwaj gracze posiadają jedynie strategię remisującą (Młynek, Awari, Warcaby). W niniejszej pracy porównano wydajność dwóch modyfikacji...
-
Ocena poprawności działania algorytmu proof-number search na strukturze digrafu acyklicznego
PublikacjaAlgorytm proof-number search jest znanym algorytmem służącym do rozwiązywania gier logicznych. Rozwiązanie gry jest jednoznaczne ze znalezieniem optymalnej strategii i pozwala przeprowadzić rozgrywkę w sposób pozwalający na osiągnięcie najlepszego możliwego wyniku. Jedną z największych wad tego algorytmu, naturalnie pracującego na strukturze drzewa, jest wielokrotne rozwijanie identycznych poddrzew gry co prowadzi do nadmiarowego...
-
Ewolucja chemotaksji organizmów jednokomórkowych w dwuwymiarowym środowisku
PublikacjaOpracowany przez nas model środowiska oparty jest na fizyce dyfuzji płynów i umożliwia symulację dyfuzji morfogenów. Sztuczne organizmy w tym środowisku wykazują chemotaksję: poruszają się reagując na zmianę stężenia substancji chemicznych. Organizm sterowany jest za pomocą sieci genowej kodowanej w liniowym genomie. Organizmy rozmnażają się przez podział. Przeprowadziliśmy szereg doświadczeń pozwalających na obserwację zachowania...
-
Properties of the triset metric for phylogenetic trees
Publikacjathe following paper presents a new polynomial time metric for unrootedphylogenetic trees (based on weighted bipartite graphs and the method ofdetermining a minimum perfect matching) and its properties. also many its properties are presented.
-
Minimal 2-dominating sets in Trees
PublikacjaWe provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time O(1.3247^n). This leads to that every tree has at most 1.3247^n minimal 2-dominating sets. We also show that thisbound is tight.
-
Colorings of the Strong Product of Circulant Graphs
PublikacjaGraph coloring is one of the famous problems in graph theory and it has many applications to information theory. In the paper we present colorings of the strong product of several circulant graphs.
-
Igrzyska Akademii ETI : Konkurs dla młodych talentów informatycznych, potencjalnych studentów WETI
PublikacjaSprawozdanie z pierwszych Igrzysk Akademii ETI, które odbyły się 21 stycznia 2012 r.
-
Katedra Algorytmów i Modelowania Systemów
PublikacjaPrzedstawiono podstawowe informacje nt. Katedry Algorytmów i Modelowania Systemów Wydziału Elektroniki, Telekomunikacji i Informatyki PG. W szczególności przedstawiono rys historyczny, działalność dydaktyczną, badania podstawowe, nagrody i wyróżnienia oraz ofertę dla przemysłu.
-
On trees with equal domination and total outer-independent domination numbers
PublikacjaFor a graph G=(V,E), a subset D subseteq V(G) is a dominating set if every vertex of V(G)D has a neighbor in D, while it is a total outer-independent dominating set if every vertex of G has a neighbor in D, and the set V(G)D is independent. The domination (total outer-independent domination, respectively) number of G is the minimum cardinality of a dominating (total outer-independent dominating, respectively) set of G. We characterize...
-
Greedy algorithms for backbone graph coloring in KOALA library
Publikacja -
On Optimal Backbone Coloring of Split and Threshold Graphs with Pairwise Disjoint Stars
Publikacja -
Product Graph Invariants with Applications in the Theory of Information
PublikacjaThere are a large number of graph invariants. In the paper, we consider some of them, e.g. the independence and chromatic numbers. It is well know that we cannot efficiently calculate these numbers for arbitrary graphs. In the paper we present relations between these invariants and concepts from the theory of information. Concepts such as source coding and transmission over a noisy channel with zero probability of error are modeled...
-
Double bondage in graphs
PublikacjaA vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The double domination number of a graph G, denoted by gamma_d(G), is the minimum cardinality of a double dominating set of G. The double bondage number of G, denoted by b_d(G), is the minimum cardinality among all sets...
-
Modele i metody kolorowania grafów. Część II
PublikacjaNiniejszy artykuł jest drugą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano różne kryteria i ograniczenia modyfikujące kolorowanie klasyczne. Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podano oszacowania na liczbę chromatyczną (indeks chromatyczny)...
-
A Point Set Connection Problem for Autonomous Mobile Robots in a Grid
PublikacjaConsider an orthogonal grid of streets and avenues in a Manhattan-like city populated by stationary sensor modules at some intersections and mobile robots that can serve as relays of information that the modules exchange, where both module-module and module-robot communication is limited to a straight line of sight within the grid. The robots are oblivious and move asynchronously. We present a distributed algorithm that, given...
-
Kodowanie niedostarczonej do odbiorców informacji w systemach satelitarnych z wolnym kanałem zwrotnym
PublikacjaW poniższym artykule przedstawiono problem kodowania źródła satelitarnego opisany przez Birka i Kola. Przytoczono również nieoptymalne kodowanie dla postawionego problemu oraz miarę określającą możliwości takiego kodowania oraz kilka przykładów, w których wcześniej wspomniane kodowanie staje się optymalne.
-
Modeling and analysis of the effectiveness of the guard systemswith dynamic graphs
PublikacjaIn the following paper it will be presented a new model for analysis (in polynomial time) of the effectiveness of the guard systems. Therewill be presented its practical applications in problems such as searching for the weakest points of the system, planning guards' paths or cameras deployment, switching image from multiple cameras on several monitors, or interception of the intruder. This model is based on describing the guarded...
-
Some Exact Values of Shannon Capacity for Evolving Systems
PublikacjaWe describe the notion of Shannon Capacity for evolving channels. Furthermore, using a computer search together with some theoretical results we establish some exact values of the measure.
-
Metody optymalizacji dyskretnej w analizie podobieństwa drzew filognetycznych
Publikacja -
Kolorowanie grafów z ograniczeniami na liczbę wierzchołków w określonym kolorze = Graph coloring model with restrictions on cardinalities of vertexes in particular color
PublikacjaW artykule rozważamy problem takiego kolorowania grafów, w którym klasy kolorów mają ograniczoną z góry moc. Zagadnie to znajduje ciekawe zastosowania praktyczne i jest naturalnym uogólnieniem problemu kolorowania grafów. W artykule ustalamy złożoność obliczeniową dla grafów pełnych $r$-dzielnych i dla kilku innych prostych klas grafów oraz dla problemu dwukolorowania.
-
Minimalizacja szerokości pasma w sieciach radiowych metodami szkieletowego kolorowania grafów
PublikacjaArtykuł poświęcony jest szkieletowemu kolorowaniu grafów, które jest matematycznym modelem dla problemu minimalizacji szerokości pasma w sieciach radiowych. Badamy w nim zależność szkieletowej liczby chromatycznej od parametrów zagadnienia. Dowodzimy, że dla dużych wartości parametrów ta zależność jest liniowa.
-
Parallel query processing and edge ranking of graphs
PublikacjaArtykuł poświęcony jest problemowi szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym. Jednym z zastosowań jest poszukiwanie optymalnych harmonogramów w równoległym przetwarzaniu zapytań w relacyjnych bazach danych. Podajemy nowe oszacowanie funkcji dobroci przybliżonego algorytmu autorstwa Makino, Uno i Ibaraki wraz z rezultatami testów komputerowych przeprowadzonych dla grafów losowych.
-
Złożoność obliczeniowa problemu szeregowania zadań w cylindrycznym systemie przepływowym
PublikacjaW pracy rozważano złożoność obliczeniową problemu szeregowania w cylindrycznym systemie przepływowym. Skonstruowano algorytm wielomianowy dla problemu dwumaszynowego oraz wykazano, iż zagadnienie staje się NP-trudne przy szeregowaniu na trzech procesorach, bądź na dwóch, przy dodatkowym wymuszeniu braku obustronnych przestojów.
-
Generowanie sąsiedztwa w algorytmach lokalnych poszukiwań uporządkowanego kolorowania grafów
PublikacjaPrzedstawienie rozwiązań problemów kombinatorycznych w postacipermutacji daje podstawy do konstrukcji algorytmów lokalnychposzukiwań. Uporządkowane pokolorowanie grafu można zapisać w postaci permutacji wierzchołków grafu. Podstawowe operacje prowadzącedo generowania sąsiedztwa rozwiązania to zamiana dwóch elementówlub przesunięcie elementu permutacji. W artykule wskazujemy metodępozwalającą na wykonanie takich operacji w czasie...
-
Approximation strategies for routing edge disjoint paths in complete graphs
PublikacjaPraca dotyczy problemu ścieżek krawędziowo rozłącznych w nieskierowanych grafach pełnych, dla którego podano nowe algorytmy przybliżone: 3.75-przybliżony (model off-line) i 6.47-przybliżony (model on-line). Stosując podobną metodologię, uzyskano algorytm 4.5-przybliżony (off-line) i 6-przybliżony (on-line) dla problemu routingu i kolorowania ścieżek w grafach pełnych.
-
The complexity of equitable vertex coloring graphs
PublikacjaW artykule podajemy wzory na sprawiedliwą liczbę chromatyczną niektórych produktów grafowych. Ponadto przedstawiamy dwa algorytmy wielomianowe dla sprawiedliwego kolorowania grafów suboptymalną liczba kolorów.
-
Komputerowe wspomaganie przeprowadzania i oceniania testów
PublikacjaW artykule przedstawiono podstawowe funkcje sieciowego systemu komputerowego wspomagającego przeprowadzenie i ocenianie testów. Szczególną uwagę zwrócono na funkcję modułu obsługi nauczyciela.
-
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...
-
Zastosowanie algorytmów rojowych do kolorowania grafów
PublikacjaPrzedstawiamy sposób adaptacji heurystycznej metody przeszukiwania PSO (ang. Particle Swarm Optimization) do znajdowania suboptymalnych pokolorowań wierzchołkowych grafów prostych. Prezentujemy sposób przeprowadzenia eksperymentów obliczeniowych oraz ich wyniki.
-
Chromatic scheduling of 1- and 2-processor uet tasks on dedicated machines with availability constraints.
PublikacjaRozważono uogólnienie klasycznego szeregowania jednostkowych zadań jedno- i dwuprocesorowych na maszynach dedykowanych. Przyjęty model pozwala na naturalne wprowadzenie wszystkich klasycznych kryteriów optymalizacyjnych dla harmonogramów. Zaproponowano algorytmy wielomianowe dla systemów rzadkich.
-
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.
-
Equitable 4-coloring of cacti and edge-cacti in polynomial time
PublikacjaRozważono problem wyznaczania sprawiedliwej liczby chromatycznej kaktusów i drzew wielokątowych bez trójkątów i krawędzi wiszących. Podano wielomianowy algorytm wyznaczający pokolorowanie optymalne, oparty na paradygmacie programowania dynamicznego. Tym samym znaleziona została kolejna klasa grafów planarnych, dla której kolorowanie sprawiedliwe jawi się jako zagadnienie obliczeniowo łatwe.
-
Formalizm i metody szeregowania zadań dla potrzeb redukcji poboru mocy cyfrowych układów CMOS
PublikacjaW pracy przedstawiono związki pomiędzy modelami formalnymi stosowanymi w klasycznym szeregowaniu zadań a metodami wykorzystywanymi w syntezie wysokiego poziomu układów cyfrowych CMOS. Zagadnienia optymalizacyjne pojawiające się w obu tych problemach mogą być w pewnym sensie transformowalne. Pozwala to na przenoszenie wybranych metod rozwiązań z jednego problemu do drugiego.
-
Parallel tabu search for graph coloring problem
PublikacjaTabu search is a simple, yet powerful meta-heuristic based on local search that has been often used to solve combinatorial optimization problems like the graph coloring problem. This paper presents current taxonomy of patallel tabu search algorithms and compares three parallelization techniques applied to Tabucol, a sequential TS algorithm for graph coloring. The experimental results are based on graphs available from the DIMACS...
-
Aplikacja wspomagająca przetwarzanie sekwencji dna: moduł edycji chromatogramu
PublikacjaModuł edycji chromatogramu jest częścią większej aplikacji, służącej do wspomagania przetwarzania danych pochodzących z sekwencjonowania DNA. Aplikacja skonstruowana jest z odrębnych, samodzielnych programów, które współpracują dwiema drogami - poprzez popularne formaty plików, co umożliwia wprowadzenie do modułów danych opracowanych częściowo w aplikacjach zewnętrznych, oraz poprzez przesyłanie danych pomiędzy modułami, co usprawnia...
-
Identyfikacja terenu za pomocą autonomicznego robota
PublikacjaW pracy rozważane jest zagadnienie identyfikacji nieznanego terenuprzy pomocy autonomicznego robota o ograniczonym zasięguwidzialności. Przyjęty model matematyczny zakłada, że teren mapostać ograniczonej dwuwymiarowej mapy podzielonej na identycznekwadratowe obszary (pola) przylegające do siebie bokami. Zadaniemautonomicznego robota, którego zasięg widzialności ogranicza siedo pól przylegających do miejsca, w którym się znajduje,...
-
Aplikacja wspomagająca przetwarzanie sekwencji dna: moduł dopasowań
PublikacjaBiologia molekularna jest obecnie bardzo dynamicznie rozwijającą się dziedziną nauki. Wzrost mocy obliczeniowej komputerów pozwala na coraz szybszą i dokładniejszą analizę wielocząsteczkowych biologicznych polimerów. Poniższy artykuł przedstawia jeden z modułów programu AlignGator - modułowego systemu przeznaczonego do analizy DNA. Omawiany moduł pozwala na tworzenie, oraz edycję wielodopasowań. W początkowej części artykułu opisane...
-
Grafowy model macierzy ultrametrycznej i jego zastosowania w filogenezie i t-kolorowaniu
PublikacjaW pracy podano definicję macierzy ultrametrycznej i jej reprezentację grafową. Macierz ta jest wykorzystywana głównie w filogenezie, do budowy drzew ultrametrycznych. W pracy opisano jeden z algorytmów słuzący do konstrukcji takich drzew. Ponadto, omówiono inne możliwe zastosowania modelu grafowego macierzy, tym razem dla problemu przydziału częstotliwości dla nadajników. Zaproponowano również rozwiązanie tego problemu w szczególnym...
-
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...
-
On some ramsey and turan-type numbers for paths and cycles
PublikacjaUdowodniono, że R(P_3,C_k,C_k)= R(C_k,C_k)= 2k - 1, dla nieparzystych k. Udowodniono, że R(P_4,P_4,C_k) = k + 2 oraz R(P_3,P_5,C_k) = k + 1 dla k > 2.
-
Wyszukiwanie cykli w grafach przy użyciu cykli Hopfielda
PublikacjaPrzedstawiono przykłady zastosowania sieci neuronowej Hopfielda do rozwiązywania trudnych obliczeniowo problemów kombinatorycznych.
-
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...
-
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...
-
Porównanie heurystyk dla problemu szeregowania zadań czasowo-zależnych o wspólnym podstawowym czasie wykonywania
PublikacjaW pracy rozważany jest następujący, jednoprocesorowy problem szeregowania zadań czasowo-zależnych. danych jest n+1 zadań o czasach wykonywania postaci pi = a + bisi, gdzie si oznacza czas rozpoczęcia wykonywania i-tego zadania, a > 0, bi > 0, i = 0, 1, ..., n. wszystkie zadania są niepodzielne i dostępne w chwili t0 = 0. należy znaleźć harmonogram minimalizujący łączny czas zakończenia. w pracy przedstawiono algorytm, który, o...
-
The circular chromatic index of some class 2 graphs
PublikacjaW artykule został wyznaczony cyrkularny indeks chromatyczny dla dwóch rodzin grafów klasy 2. Co więcej, podano nie trywialne oszacowania tego parametru dla snarków Isaacsa i Goldberga. Na koniec artykułu rozważana jest złożoność obliczeniowa problemów związanych z cyrkularnym kolorowaniem krawędzi.
-
Witryna inrenetowa w funkcjonowaniu szkoły
PublikacjaW artykule przedstawiono problematykę funkcjonowania witryn internetowych w środowisku edukacyjnym. Przeanalizowano aspekty zarówno natury technologicznej jak i informacyjnej. Zaprezentowano technologie informatyczne i internetowe zorientowane na tworzenie witryn www. Przeanalizowano potrzeby funkcjonalne dla witryn szkolnych i edukacyjnych. Zwrócono uwagę na ich ukierunkowanie na grupy odbiorcze. Pokazano reprezentatywne przykłady...