Search
Filters
total: 74
Search results for: teoria grafow
-
Packing three-vertex paths in a subcubic graph
PublicationW 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.
-
Weakly cooperative guards in grids
PublicationW pracy autorzy zajmują się rozmieszczaniem strażników mobilnych w kratach ortogonalnych, podali wzór na minimalną liczbę strażników w kracie oraz przeanalizowali złożoność obliczeniową problemu.
-
On bounded load routings for modeling k-regular connection topologies
PublicationW 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.
-
Rozproszone kolorowanie grafów
PublicationW pracy zaprezentowano nowy rozproszony algorytm kolorowania grafów. Przeprowadzone eksperymenty pokazują, że daje on lepsze wyniki niż znany wcześniej algorytm trywialny.
-
Ramseyowskie pokolorowanie grafów pełnych
PublicationW rozdziale przedstawiono znane wartości, własności a także oszacowania kla-sycznych i nieklasycznych liczb Ramseya; przedstawiono także przykłady ichzastosowań.
-
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.
-
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ą...
-
Gossiping by energy-constrained mobile agents in tree networks
PublicationEvery node of an edge-weighted tree network contains a data packet. At some nodes are placed mobile agents, each one possessing an amount of energy (not necessarily the same for all agents). While walking along the network, the agents spend the energy proportionally to the distance traveled and collect copies of the data packets present at the visited network nodes. An agent visiting a node deposits there copies of all currently...
-
Grafo-mania, czyli rzecz o grafach i algorytmach. Problem 8 hetmanów
PublicationW eseju spojrzano na problem 8 hetmanów na szachownicy z punktu widzenia teorii grafów
-
The complexity of bicriteria tree-depth
PublicationThe tree-depth problem can be seen as finding an elimination tree of minimum height for a given input graph G. We introduce a bicriteria generalization in which additionally the width of the elimination tree needs to be bounded by some input integer b. We are interested in the case when G is the line graph of a tree, proving that the problem is NP-hard and obtaining a polynomial-time additive 2b-approximation algorithm. This particular...
-
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.
-
Graphs with convex domination number close to their order
PublicationW pracy opisane są grafy z liczbą dominowania wypukłego bliską ilości ich wierzchołków.
-
Dominowanie w grafach
PublicationW pracy rozważanych jest pięć liczb dominowania: klasyczna liczba dominowania, liczba dominowania spójnego, liczba dominowania słabo spójnego, liczba dominowania słabo wypukłego i liczba dominowania wypukłego. Rozważane są pewne ograniczenia na liczby dominowania, równości między poszczególnymi liczbami, wpływ usuwania krawędzi lub zbioru krawędzi na liczby dominowania i NP-zupełność problemów dominowania.
-
Lower bound on the distance k-domination number of a tree
PublicationW artykule przedstawiono dolne ograniczenie na liczbę k-dominowania w drzewach oraz scharakteryzowano wszystkie grafy ekstremalne.
-
On the doubly connected domination number of a graph
PublicationW pracy została zdefiniowana liczba dominowania podwójnie spójnego i przedstawiono jej podstawowe własności.
-
Domination numbers in graphs with removed edge or set of edges
PublicationW artykule przedstawiony jest wpływ usuwania krawędzi lub zbioru krawędzi na liczby dominowania spójnego i słabo spójnego.