Wyniki wyszukiwania dla: teoria grafów
-
LICZBA PODZIAŁOWA DLA DOMINOWANIA W GRAFACH
PublikacjaW 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...
-
Grafo-mania, czyli rzecz o grafach i algorytmach. Problem 8 hetmanów
PublikacjaW eseju spojrzano na problem 8 hetmanów na szachownicy z punktu widzenia teorii grafów
-
The complexity of bicriteria tree-depth
PublikacjaThe 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...
-
Gossiping by energy-constrained mobile agents in tree networks
PublikacjaEvery 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...
-
On the Characteristic Graph of a Discrete Symmetric Channel
PublikacjaWe present some characterizations of characteristic graphs of row and/or column symmetric channels. We also give a polynomial-time algorithm that decides whether there exists a discrete symmetric channel whose characteristic graph is equal to a given input graph. In addition, we show several applications of our results.
-
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....
-
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...
-
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...
-
Modele i algorytmy dla grafowych struktur defensywnych
PublikacjaW 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ą...
-
Packing three-vertex paths in a subcubic graph
PublikacjaW 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
PublikacjaW 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
PublikacjaW 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.
-
Graphs with convex domination number close to their order
PublikacjaW pracy opisane są grafy z liczbą dominowania wypukłego bliską ilości ich wierzchołków.
-
Dominowanie w grafach
PublikacjaW 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
PublikacjaW artykule przedstawiono dolne ograniczenie na liczbę k-dominowania w drzewach oraz scharakteryzowano wszystkie grafy ekstremalne.
-
On the doubly connected domination number of a graph
PublikacjaW 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
PublikacjaW artykule przedstawiony jest wpływ usuwania krawędzi lub zbioru krawędzi na liczby dominowania spójnego i słabo spójnego.
-
Edge and Pair Queries-Random Graphs and Complexity
PublikacjaWe 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.
-
Rozproszone kolorowanie grafów
PublikacjaW 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
PublikacjaW rozdziale przedstawiono znane wartości, własności a także oszacowania kla-sycznych i nieklasycznych liczb Ramseya; przedstawiono także przykłady ichzastosowań.
-
An experimental study of distributed algorithms for graph coloring.
PublikacjaW pracy podano algorytm rozproszonego kolorowania grafówi porównano ze znanym wcześniej algorytmem.
-
Lower bound on the domination number of a tree.
PublikacjaW pracy przedstawiono dolne ograniczenie na liczbę dominowania w drzewach oraz przedstawiono pełną charakterystykę grafów ekstremalnych.
-
Weakly convex and convex domination numbers.
PublikacjaW artykule przedstawione są nowo zdefiniowane liczby dominowania wypukłego i słabo wypukłego oraz ich porównanie z innymi liczbami dominowania. W szczególności, rozważana jest równość liczby dominowania spójnego i wypukłego dla grafów kubicznych.
-
Production structures and strategies supporting lean parts manufacturing: an industrial case study.
PublikacjaPrzedstawiono model sformalizowanego opisu wzorców możliwości wytwarzania zróżnicowanego spektrum przedmiotów oraz analizy podobieństwa ich procesów technologicznych, dla kształtowania struktur przestrzennych systemów typu gniazdowego, z uwzględnieniem paradygmatu oszczędnej produkcji. Zaproponowano algorytm grupowania przedmiotów wg określonych, w postaci ciągów znakowych, sekwencji operacji procesu technologicznego oraz kryterium...