Search
Filters
total: 75
Search results for: teoria grafow
-
Joanna Raczek dr inż.
PeopleEmployment 2003 -- 2019: Faculty of Applied Physics and Mathematics, Gdańsk University of Technology. 2019 - present: Faculty of Electronic, Informatics and Telecominications, Gdańsk University of Technology. Education May 2007: Doctor of Philosophy in Mathematics, University of Gdańsk. Doctoral dissertation: "Paired domination and doubly domination in graphs". Supervisor: dr hab. Jerzy Topp. 2000 -- 2004 Bachelor of Science...
-
Kacper Wereszko mgr inż.
PeopleKacper Wereszko received the M.Sc. in 2016 (field of study: computer science, specialization: Internet technologies and algorithms). Since 2017 he is a Ph.D. student in the field of computer science. He works as assistant in Department of Algorithms and System Modelling. His research interests focus on security properties of graphs, domination problems in graphs and their practical applications.
-
Robert Lewoń dr inż.
People -
On efficient coloring of chordless graphs
PublicationArtykuł omawia zagadnienie optymalnego, wielomianowego rozpoznawania i kolorowania grafów bezcięciwowych. Zawiera dowód tego, że takie grafy są zawsze 4-kolorowalne oraz opis wielomianowego algorytmu, który koloruje je minimalną możliwą liczbą kolorów.
-
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...
-
Modele i algorytmy dla grafowych struktur defensywnych
PublicationW niniejszej pracy przeprowadzono analizę złożoności istnienia struktur defensywnych oraz równowag strategicznych w grafach. W przypadku struktur defensywnych badano modele koalicji defensywnych, zbiorów defensywnych i koalicji krawędziowych - każdy z nich w wersji globalnej, tj. z wymogiem dominacji całego grafu. W przypadku modeli równowagi strategicznej badano równowagę strategiczną koalicji defensywnych, równowagę strategiczną...
-
Model formalny dla problemu lokalizacji błędów w kodzie programu
PublicationIstnieje 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...
-
Total restrained domination numbers of trees
PublicationOpisane są wszystkie drzewa, w których liczby dominowania totalnego i totalno - powściągniętego są sobie równe, a także podano dolne ograniczenie na liczbę dominowania totalno - powściągniętego w drzewach.
-
Paired domination and doubly domination in graphs
PublicationW rozprawie poruszane są zagadnienia związane z dominowaniem parami w grafach oraz domiowaniem totalno - powściągniętym w grafach. Ponadto omawiane są zagadnienia związane ze złożonością obliczeniową różnych problemów dominowania w grafach.
-
Lower bound on the weakly connected domination number of a tree
PublicationPraca dotyczy dolnego ograniczenia liczby dominowania słabo spójnego w drzewach (ograniczenie ze względu na ilość wierzchołków i ilość wierzchołków końcowych w drzewie).
-
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.
-
Total outer-connected domination in trees
PublicationW pracy przedstawiono dolne ograniczenie na liczbę dominowania totalnego zewnętrznie spójnego w grafach oraz scharakteryzowano wszystkie drzewa osiągające to ograniczenie.
-
The outer-connected domination number of a graph
PublicationW pracy została zdefiniowana liczba dominowania zewnętrznie spójnego i przedstawiono jej podstawowe własności.
-
Packing Three-Vertex Paths in 2-Connected Cubic Graphs
PublicationW pracy rozważano problem rozmieszczanie ścieżek P3 w 2-spójnych grafach 3-regularnych. Pokazano, że w 2-spójnym grafie 3-regularnym o n wierzchołkach można zawsze pokryć 9/11 n wierzchołków przez ścieżki P3; podano także odpowiednie oszacowania górne.
-
Cost minimization in wireless networks with a bounded and unbounded number of interfaces
PublicationPraca 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...
-
Generowanie sąsiedztwa w algorytmach lokalnych poszukiwań uporządkowanego kolorowania grafów
PublicationPrzedstawienie 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...
-
On the total restrained domination number of a graph
PublicationW pracy przedstawione są ograniczenia i własności liczby dominowania podwójnie totalnego.
-
Identyfikacja terenu za pomocą autonomicznego robota
PublicationW 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,...
-
Wyszukiwanie cykli w grafach przy użyciu cykli Hopfielda
PublicationPrzedstawiono przykłady zastosowania sieci neuronowej Hopfielda do rozwiązywania trudnych obliczeniowo problemów kombinatorycznych.
-
Trees with equal restrained domination and total restrained domination numbers
PublicationW publikacji scharakteryzowano wszystkie drzewa, w których liczby dominowania powściągniętego oraz podwójnie totalnego są sobie równe.
-
Clearing directed subgraphs by mobile agents
PublicationWe study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H=(V,A) of D such that (a) S is a subset of V, (b) H is the union of k directed...
-
Forwarding and optical indices of a graph
PublicationW pracy rozstrzygnięto dwa problemy dotyczące komunikacji wszyscy-do-wszystkich w grafach. Stwierdzono, że dla wersji skierowanej problemu parametry ''pi'' (maksymalne obciążenie krawędzi) i ''w'' (parametr chromatyczny) nie muszą być w ogólności sobie równe. Dla wersji nieskierowanej problemu pokazano, że wyznaczenie wartości zarówno ''pi'', jak i ''w'', jest w ogólności problemem NP-trudnym.
-
Tighter bounds on the size of a maximum P3-matching in a cubic graph
PublicationW pracy pokazano, że największe P3-skojarzenie dla dowolnego grafu o n>16 wierzchołkach składa się z przynajmniej 117n/152 wierzchołków.
-
Cost minimisation in unbounded multi-interface networks
PublicationW pracy badano problem odłączania niektórych urządzeń komunikacyjnych w wielointerfejsowych sieciach bezprzewodowych w taki sposób, by zapewnić realizację wymaganego grafu połączeń przy jednoczesnej minimalizacji zużycia energii. Sformułowano problem optymalizacyjny, podano wyniki dotyczące jego trudności i zaproponowano algorytmy optymalizacyjne dla wariantu, w którym liczba interfejsów komunikacyjnych jest potencjalnie nieograniczona...
-
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
PublicationW 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)$.
-
The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree
PublicationW 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...
-
Maximum vertex occupation time and inert fugitive: recontamination does help [online]
PublicationRozważamy problem przeszukania danego grafu prostego G w celu przechwycenia niewidocznego i leniwego uciekiniera. Parametrem optymalizacyjnym, który minimalizujemy jest maksymalny czas (liczba tur strategii przeszukiwania), podczas których wierzchołek może być strzeżony (okupowany przez strażnika). Strategia monotoniczna to taka, która nie dopuszcza sytuacji, w której uciekinier dociera do wierzchołka, który wcześniej został oczyszczony....
-
Mixed graph edge coloring
PublicationW pracy rozważany jest problem kolorowania krawędzi grafu mieszanego, tj. grafu zawierającego zawiero skierowane, jak i nieskierowane krawędzie. Motywację do badań stanowią zagadnienia komunikacyjne z zakresu szeregowania zadań.
-
A note on the strength and minimum color sum of bipartite graphs
PublicationSiłą grafu G nazywamy najmniejszą liczbę całkowitą s, taką że istniej pokolorowanie grafu G, o minimalnej sumie przy użyciu kolorów {1,...,s}. W pracy pokazano, że w grafach dwudzielnych stopnia D zachodzi oszacowanie s <= ceil(D/2) + 1. Z obserwacji tej wynika algorytm wielomianowy do obliczania siły i sumy chromatycznej w grafach dwudzielnych stopnia co najwyżej 4.
-
Approximating the maximum 2- and 3-edge-colorable subgraph problems
PublicationDla ustalonej wartości parametru k>=2, problem maksymalnego podgrafu krawędziowo k-kolorowalnego polega na wskazaniu k rozłącznych skojarzeń w grafie prostym, a kryterium optymalizacji jest maksymalizacja całkowitej liczby użytych krawędzi. W pracy podano algorytmy 5/6- i 4/5-przybliżone odpowiednio dla przypadków k=2 i k=3, poprawiając wyniki znane z literatury.
-
The complexity of minimum-length path decompositions
PublicationWe consider a bi-criteria generalization of the pathwidth problem, where, for given integers k, l and a graph G, we ask whether there exists a path decomposition P of G such that the width of P is at most k and the number of bags in P, i.e., the length of P, is at most l. We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter...
-
Planarność i zewnętrzna planarność grafów
PublicationNiech G będzie niepustym grafem prostym. Graf, który można przedstawić na płaszczyźnie w taki sposób, że żadne dwie krawędzie nie przecinają się nazywamy grafem płaskim, natomiast graf nazywamy planarnym, gdy jest on izomorficzny do grafu płaskiego. Jeśli dodatkowo wszystkie jego wierzchołki leżą na obszarze zewnętrznym, graf nazywamy zewnętrznie planarnym. Indeksem krawędziowym grafu G nazywamy najmniejsze k takie, że k-ty iterowany...
-
A note on the weakly convex and convex domination numbers of a torus
PublicationW pracy określone są liczby liczby dominowania i dominowania wypukłego torusów, czyli iloczynów kartezjańskich dwóch cykli.
-
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...
-
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...
-
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.
-
Minimalizacja szerokości pasma w sieciach radiowych metodami szkieletowego kolorowania grafów
PublicationArtykuł 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.
-
LICZBA PODZIAŁOWA DLA DOMINOWANIA W GRAFACH
PublicationW PRACY ROZWAŻAMY 6 RODZAJÓW ZBIORÓW DOMINUJĄCYCH ORAZ LICZB ZWIĄZANYCH Z TYMI ZBIORAMI: KLASYCZNĄ LICZBĘ DOMINOWANIA, LICZBĘ DOMINOWANIA TOTALNEGO, PARAMI, SŁABO-SPÓJNEGO, 2-DOMINOWANIA I DOMINOWANIA WYPUKŁEGO. W PRACY ROZWAŻAMY WPŁYW TRZECH OPERACJI NA KRAWĘDZIE GRAFU: USUWANIE KRAWĘDZI Z GRAFU, JEDNOKROTNY PODZIAŁ PEWNEJ LICZBY KRAWĘDZI I PODZIAŁ WIELOKROTNY JEDNEJ KRAWĘDZI. BADAMY ZWIĄZKI TYCH OPERACJI Z ROZWAŻANYMI LICZBAMI...
-
The limit case of a domination property
PublicationPraca dotyczy dolnego ograniczenia liczby dominowania w grafach, ze względu na ilość wierzchołków oraz największą liczbę liści w drzewie spinającym.
-
Convex universal fixers
PublicationPraca dotyczy dominowania wypukłego w grafach pryzmowych.
-
Optimal edge-coloring with edge rate constraints
PublicationWe consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not [Grötschel et al., Combinatorica (1981), 169–197], we show that several questions about the length of the sequence are computationally intractable....
-
Leader election for anonymous asynchronous agents in arbitrary networks
PublicationWe consider the problem of leader election among mobile agents operating in an arbitrary network modeled as an undirected graph. Nodes of the network are unlabeled and all agents are identical. Hence the only way to elect a leader among agents is by exploiting asymmetries in their initial positions in the graph. Agents do not know the graph or their positions in it, hence they must gain this knowledge by navigating in the graph...
-
On minimum cost edge searching
PublicationWe consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to find a search strategy that minimizes both the cost and the number of searchers used to clear a given graph G. We call such a strategy ideal. We prove, by an example, that ideal search strategies do not...
-
Three-fast-searchable graphs
PublicationIn the edge searching problem, searchers move from vertex to vertex in a graph to capture an invisible, fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which, at every move, a new edge of the graph G must be guaranteed to be free of the intruder. That is, once all searchers are placed the graph G is cleared in exactly |E(G)| moves. Such a restriction obviously necessitates...
-
On-line ranking of split graphs
PublicationA vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm...
-
Modele i algorytmy dla grafowych struktur defensywnych
PublicationW niniejszej pracy przeprowadzono analizę złożoności istnienia struktur defensywnych oraz równowag strategicznych w grafach. W przypadku struktur defensywnych badano modele koalicji defensywnych, zbiorów defensywnych i koalicji krawędziowych – każdy z nich w wersji globalnej, tj. z wymogiem dominacji całego grafu. W przypadku modeli równowagi strategicznej badano równowagę strategiczną koalicji defensywnych, równowagę strategiczną...
-
Edge and Pair Queries-Random Graphs and Complexity
PublicationWe investigate two types of query games played on a graph, pair queries and edge queries. We concentrate on investigating the two associated graph parameters for binomial random graphs, and showing that determining any of the two parameters is NP-hard for bounded degree graphs.
-
Zero-visibility cops and robber and the pathwidth of a graph
PublicationWe examine the zero-visibility cops and robber graph searching model, which differs from the classical cops and robber game in one way: the robber is invisible. We show that this model is not monotonic. We show that the zero-visibility copnumber of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the...
-
The Complexity of Zero-Visibility Cops and Robber
PublicationIn this work we deal with the computational complexity aspects of the zero-visibility Cops and Robber game. We provide an algorithm that computes the zero-visibility copnumber of a tree in linear time and show that the corresponding decision problem is NP-complete even for the class of starlike graphs.
-
Bounds on the cover time of parallel rotor walks
PublicationThe rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider...