Search
Department of Algorithms and Systems Modelling
Publications
Filters
total: 521
Catalog Publications
Year 2011
-
A note on fast approximate backbone coloring of split graphs with star--like backbones
PublicationDla 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.
-
A Note on Shannon Capacity for Invariant and Evolving Channels
PublicationIn the paper we discuss the notion of Shannon capacity for invariant and evolving channels. We show how this notion is involved in information theory, graph theory and Ramsey theory.
-
An upper bound on the 2-outer-independent domination number of a tree
PublicationA 2-outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)D has a at least two neighbors in D, and the set V(G)D is independent. The 2-outer-independent domination number of a graph G, denoted by gamma_2^{oi}(G), is the minimum cardinality of a 2-outer-independent dominating set of G. We prove that for every nontrivial tree T of order n with l leaves we have gamma_2^{oi}(T) <= (n+l)/2,...
-
Analysis of elementary cellular automata using the theory of conflict
PublicationThe 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.
-
Analyzing sets of phylogenetic trees using metrics
PublicationThe reconstruction of evolutionary trees is one of the primary objectives in phylogenetics. Such a tree represents historical evolutionary relationships between different species or organisms. Tree comparisons are used for multiple purposes, from unveiling the history of species to deciphering evolutionary associations among organisms and geographical areas. In this paper, we describe a general method for comparing phylogenetictrees...
-
Connected searching of weighted trees
PublicationW 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.
-
Consensus models: Computational complexity aspects in modern approaches to the list coloring problem
PublicationArtykuł 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.
-
Construction of phylogenetic trees with topological constraints
PublicationThis 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...
-
Cztery algorytmy które wstrząsnęły światem. Część I: Wprowadzenie
PublicationArtykuł przeglądowy jest pierwszym fragmentem 3-częściowego szkicu popularnonaukowego poświęconego najważniejszym osiągnięciom w dziedzinie algorytmiki. Wprowadzono w nim w arkana złożoności obliczeniowej i sztuki programowania komputerów.
-
Cztery algorytmy które wstrząsnęły światem. Część II: Od czasu wykładniczego do wielomianowego
PublicationDrugi odcinek cyklu poświęcono problemowi programowania liniowego, który wywarł ogromny wpływ na życie milionów ludzi oraz badaniu liczb pierwszych, a więc problemowi ściśle związanemu z bezpieczeństwem naszych pieniędzy zdeponowanych w bankach.
-
Cztery algorytmy które wstrząsnęły światem. Część III: Sprzęt czy oprogramowanie
PublicationW trzecim odcinku cyklu poruszono problem przyjaznego rysowania grafów oraz zaprezentowano algorytmy dla szybkiego mnożenia macierzy, a więc problemu, który pojawia się w każdej nauce inżynieryjnej. Rozważania ogólne zamknięto ilustracją postępu, jaki dokonał się w zakresie sprzętu liczącego i oprogramowania.
-
Ewolucja chemotaksji organizmów jednokomórkowych w dwuwymiarowym środowisku
PublicationOpracowany 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...
-
GreedyMAX-type Algorithms for the Maximum Independent Set Problem
PublicationA maximum independent set problem for a simple graph G = (V,E) is to find the largest subset of pairwise nonadjacent vertices. The problem is known to be NP-hard and it is also hard to approximate. Within this article we introduce a non-negative integer valued functionp defined on the vertex set V(G) and called a potential function of agraph G, while P(G) = max{vinV(G)| p(v)} is called a potential of G. For any graph P(G) <= D(G),...
-
Hat problem on odd cycles
PublicationThe topic is the hat problem in which each of n players is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of a win. In this version every player can...
-
How to meet when you forget: log-space rendezvous in arbitrary graphs
PublicationTwo identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. The rendezvous problem is known to be not easier than graph exploration. A well-known recent result...
-
Jak szybko gasić pożar, czyli przypadek szeregowania zadań czasowozależnych
Publicationartykuł poświęcony jest planowaniu pracy brygad strażackich walczących z pożarami lasu. model matematyczny, który tutaj zastosowano to szeregowanie zadań uwarunkowanych czasowo. przedyskutowano złożoność problemu w przypadku zastosowania dwóch kryteriów optymalizacji: długości harmonogramu i średniego czasu przepływu. pokazano, że w ogólności nie istnieją uszeregowania idealne, zapewniające minimalizację obu kryteriów jednocześnie
-
Labyrynths generators, their properties and practical application in computer games
Publicationthis paper presents three basic algorithms for generation of mazes, and many of their modifications and examples showing their practical application in creating random structures that resembles those from the real world. the paper highlights the difference in the labyrinths classes generated by listed algorithms and describes a specific and highly likely to occur shapes that occur in generated mazes. particular attention was paid...
-
Matching Split Distance for Unrooted Binary Phylogenetic Trees
PublicationRekonstrukcja drzew ewolucji jest jednym z głównych celów w bioinformatyce. Drzewa filogenetyczne reprezentuje historię ewolucji i związki pokrewieństwa między różnymi gatunkami. W pracy proponujemy nową ogólną metodę określania odległości między nieukorzenionymi drzewami filogenetycznymi, szczególnie użyteczną dla dużych zbiorów gatunków. Następnie podajemy szczegółowe własności jednej metryki określonej przy użyciu tej metody...
-
Million dollar algorithn?
PublicationArtykuł w sposób popularnonaukowy porusza następujące problemy:- 2300 lat algorytmiki- 7 problemów milenijnych- rodzaje problemów pod kątem złożoności obliczeniowej- planowanie optymalne- banki i grafy- czy P=NP?
-
Modeling and analysis of the effectiveness of the guard systemswith dynamic graphs
PublicationIn 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...
-
Ocena poprawności działania algorytmu proof-number search na strukturze digrafu acyklicznego
PublicationAlgorytm 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...
-
On trees with double domination number equal to total domination number plus one
PublicationA total dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D. A vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The total (double, respectively) domination number of a graph G is the minimum cardinality of a total (double,...
-
Parity vertex colouring of graphs
PublicationA parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let Xp(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds X(G) <= Xp(G) <=|V(G)|− a(G)+1, where X(G) and a(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for...
-
Phutball is PSPACE-hard
PublicationW pracy dowodzimy, że gra ''Phutball'' (Philosopher's Football) jest PSPACE-trudna.
-
Polyhedral Ramsey Numbers
PublicationGiven two polygons or polyhedrons P1 and P2, we can transform these figures to graphs G1 and G2, respectively. The polyhedral Ramsey number Rp(G1,G2) is the smallest integer n such that every graph, which represents polyhedron on n vertices either contains a copy of G1 or its complement contains a copy of G2. Using a computer search together with some theoretical results we have established some polyhedral Ramsey numbers, for example...
-
Polynomial triset metric for unrooted phylogenetic trees
Publicationthe following paper presents a polynomial triset metric for unrooted phylogenetic trees (based on weighted bipartite graphs and the method of determining a minimum edge cover) and its basic characteristics. also a list of further directions of research and examples of the wider use of this metric is presented.
-
Preface
PublicationThis special issue of Discussiones Mathematice Graph Theory (DMGT) is dedicated to selected papers presented at the 13th Workshop on Graph Theory: Colourings, Independence and Domination (CID) held on 18-23 September 2009 in Szklarska Poręba, Poland. It continues a series of international workshops: 1993-1997 in Lubiatów, 1998-2001 in Gronów, and 2003-2007 in Karpacz. The meeting was organized by the Faculty of Mathematics, Computer...
-
Shannon Capacity and Ramsey Numbers
PublicationRamsey-type theorems are strongly related to some results from information theory. In this paper we present these relations.
-
Synchronous black hole search in directed graphs
PublicationThe paper considers a team of robots which has to explore a graph G, where some nodes can be harmful. Robots are initially located at the so-called home base node. The dangerous nodes are the so-called black hole nodes, and once a robot enters in one of them, it is destroyed. The goal is to find a strategy in order to explore G in such a way that minimum number of robots is wasted. The exploration ends if there is at least one...
-
Szeregowanie zadań uwarunkowanych czasowo
Publicationw pracy przedstawiono wyniki badań nad problemami szeregowania zadań uwarunkowanych czasowo. dla problemu 1|pi=a+bisi|σci przedstawiono nowe heurystyki, przypadek wielomianowy oraz w pełni wielomianowy schemat. wprowadzono koncepcję eliminacji zdominowanych fragmentów harmonogramu, oraz pokazano jak wykorzysta¢ ją do konstrukcji algorytmu dokładnego dla tego problemu, a także jak przy jej pomocy przyspieszy¢ inne algorytmy. następnie...
-
The complexity of node blocking for dags
PublicationRozważamy następującą grę (pomiędzy dwoma graczami) kombinatoryczną o nazwie ''node blocking''. Dany jest graf skierowany. Każdy wierzchołek może być zajęty przez co najwyżej jeden token. Wyróżniamy dwa kolory tokenów, biały i czarny, każdy gracz może przemieszczać tylko własne tokeny. Gracze wykonują ruchy naprzemiennie. Ruch polega na wyborze dowolnego tokena własnego koloru i przesunięciu go na dowolnego niezajętego przez inny...
-
The hat problem on a union of disjoint graphs
PublicationThe topic is the hat problem in which each of n players is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of winning. In this version every player...
-
The hat problem on cycles on at least nine vertices
PublicationThe topic is the hat problem in which each of n players is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of winning. In this version every player...
Year 2010
-
A modified hat problem
PublicationThe topic of our paper is the hat problem in which each of n players is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of a win. There are known many...
-
An Alternative Proof of a Lower Bound on the 2-Domination Number of a Tree
PublicationA 2-dominating set of a graph G is a set D of vertices of G such that every vertex not in D has a at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. Fink and Jacobson [n-domination in graphs, Graph theory with applications to algorithms and computer science, Wiley, New York, 1985, 283-300] established the following lower bound on the 2-domination...
-
Application of Artificial Neural Networks in Investigations of Steam Turbine Cascades
PublicationZaprezentowano wyniki badań numerycznych zastosowania sieci neuronowych przy obliczeniach przepływów w palisadach turbin parowych. Na podstawie uzyskanych wyników wykazano, że sieci neuronowe mogą być używane do szacowania przestrzennego rozkładu parametrów przepływu, takich jak entalpia, entropia, ciśnienie czy prędkość czynnika w kanale przepływowym. Omówiono również zastosowania tego typu metod przy projektowaniu palisad, stopni...
-
Application of genetic algorithms in graph searching problem
PublicationGraph searching is a common approach to solving a problem of capturing a hostile intruder by a group of mobile agents. We assume that this task is performed in environment which we are able to model as a graph G. The question asked is how many agents are needed to capture an arbitrary fast, invisible and smart intruder. This number is called the (edge) search number of G. The strategy which must be performed by agents is called...
-
Comparing Arbitrary Unrooted Phylogenetic Trees Using Generalized Matching Split Distance
PublicationIn the paper, we describe a method for comparing arbitrary, not necessary fully resolved, unrooted phylogenetic trees. Proposed method is based on finding a minimum weight matching in bipartite graphs and can be regarded as a generalization of well-known Robinson-Foulds distance. We present some properties and advantages of the new distance. We also investigate some properties of presented distance in a common biological problem...
-
Comparison of reproduction strategies in genetic algorithm approach to graph searching
Publicationgenetic algorithms (ga) are a well-known tool used to obtain approximate solutions to optimization problems. successful application of genetic algorithm in solving given problem is largely dependant on selecting appropriate genetic operators. selection, mutation and crossover techniques play a fundamental role in both time needed to obtain results and their accuracy. in this paper we focus on applying genetic algorithms in calculating...
-
Connected searching of weighted trees
PublicationW 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...
-
Constructing a map of an anonymous graph: applications of universal sequences
PublicationWe study the problem of mapping an unknown environmentrepresented as an unlabelled undirected graph. A robot (or automaton)starting at a single vertex of the graph G has to traverse the graph and return to its starting point building a map of the graph in the process. We are interested in the cost of achieving this task (whenever possible) in terms of the number of edge traversal made by the robot. Another optimization criteria...
-
Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains
PublicationTwo mobile agents, modeled as points starting at differentlocations of an unknown terrain, have to meet. The terrain is a polygon with polygonal holes. We consider two versions of this rendezvous problem: exact RV, when the points representing the agents have to coincide at some time, and epsilon-RV, when these points have to get at distance less than epsilon in the terrain. In any terrain, each agent chooses its trajectory, but...
-
Drawing maps with advice
PublicationW 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ć...
-
Elimination of dominated partial schedules in scheduling deteriorating jobs
Publicationw artykule rozważany jest problem szeregowania zadań uwarunkowanych czasowo, w notacji trójpolowej opisywany przez 1 | pi = a + bisi | ?ci. wprowadzona jest koncepcja zdominowanych częściowych harmonogramów oraz przedstawiony jest niewielomianowy algorytm dla problemu, który bazuje na eliminacji zdominowanych częściowych harmonogramów. przedstawione są wyniki eksperymentów obliczeniowych, porównujących zaprezentowany algorytm oraz...
-
Exploiting multi-interface networks: Connectivity and Cheapest Paths
PublicationLet G = (V,E) be a graph which models a set of wireless devices (nodes V) that can communicate by means of multiple radio interfaces, according to proximity and common interfaces (edges E). The problem of switching on (activating) the minimum cost set of interfaces at the nodes in order to guarantee the coverage of G was recently studied. A connection is covered (activated) when the endpoints of the corresponding edge share at...
-
Generatory labiryntów: modyfikacje algorytmu komórkowego i analiza właściwości generowanej klasy
PublicationWyróżniamy trzy podstawowe algorytmy generujące labirynty, których grafowa reprezentacja ma postać drzew: błądzenia losowego, budowania ścian i komórkowy[1]. W pracy przedstawione zostaną modyfikacje algorytmu komórkowego, które potrafią wygenerować tę samą klasę labiryntów, co podstawowa wersja algorytmu, przy jednoczesnej zmianie parametrów opisujących ich wygląd (preferencja kierunku wyjścia, średnia liczba wyjść z pokoju, średnia...
-
Hat problem on a graph
PublicationThe topic of our paper is the hat problem. In that problem, each of n people is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color looking at the hat colors of the other people. The team wins if at least one person guesses his hat color correctly and no one guesses his hat color wrong, otherwise the team loses. The aim is to maximize the probability of win. In this version every...
-
Hat problem on the cycle C4
PublicationThe topic of our paper is the hat problem. In that problem, each of n people is randomly tted with a blue or red hat. Then everybody can try to guess simultanously his own hat color looking at the hat colors of the other people. The team wins if at least one person guesses his hat color correctly and no one guesses his hat color wrong, otherwise the team loses. The aim is to maximize the probability of win. In this version every...
-
Interval wavelength assignment in all-optical star networks
PublicationArtykuł omawia zwarte końcówkowe kolorowanie grafów, które jest matematycznym modelem dla problemu przydziału częstotliwości w sieciach optycznych. W artykule przedstawiono wielomianowe algorytmy wyznaczania zwartej końcówkowej liczby chromatycznej dla pełnych grafów k-dzielnych, drzew i podkubicznych grafów dwudzielnych.
-
Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines
PublicationArtykuł 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...