Filtry
wszystkich: 73
wybranych: 70
Filtry wybranego katalogu
Wyniki wyszukiwania dla: teoria grafow
-
Maximum vertex occupation time and inert fugitive: recontamination does help [online]
PublikacjaRozważ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
PublikacjaW 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
PublikacjaSiłą 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
PublikacjaDla 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
PublikacjaWe 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...
-
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.
-
The limit case of a domination property
PublikacjaPraca 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
PublikacjaPraca dotyczy dominowania wypukłego w grafach pryzmowych.
-
Optimal edge-coloring with edge rate constraints
PublikacjaWe 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....
-
On-line ranking of split graphs
PublikacjaA 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...
-
Leader election for anonymous asynchronous agents in arbitrary networks
PublikacjaWe 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
PublikacjaWe 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
PublikacjaIn 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...
-
Total outer-connected domination in trees
PublikacjaW pracy przedstawiono dolne ograniczenie na liczbę dominowania totalnego zewnętrznie spójnego w grafach oraz scharakteryzowano wszystkie drzewa osiągające to ograniczenie.
-
Consensus models: Computational complexity aspects in modern approaches to the list coloring problem
PublikacjaArtykuł 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.
-
Zero-visibility cops and robber and the pathwidth of a graph
PublikacjaWe 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
PublikacjaIn 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.
-
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,...
-
Wyszukiwanie cykli w grafach przy użyciu cykli Hopfielda
PublikacjaPrzedstawiono przykłady zastosowania sieci neuronowej Hopfielda do rozwiązywania trudnych obliczeniowo problemów kombinatorycznych.
-
Trees with equal restrained domination and total restrained domination numbers
PublikacjaW publikacji scharakteryzowano wszystkie drzewa, w których liczby dominowania powściągniętego oraz podwójnie totalnego są sobie równe.