Wyszukiwarka
Filtry
wszystkich: 52
wybranych: 44
Wyniki wyszukiwania dla: ALGORYTMY GRAFOWE
-
From Pathwidth to Connected Pathwidth
PublikacjaW pracy przedstawiono dowód faktu, że spójna szerokość ścieżkowa grafu wynosi co najwyżek 2k+1, gdzie k jest jego szerokością ścieżkową. Dowód jest konstruktywny, tzn., został skonstruowany algorytm, który dla podanej na wejściu dekompozycji grafu o szerekości k zwraca dekompozycję spóją o szerekości co najwyżej 2k+1.
-
On the size of identifying codes in triangle-free graphs
PublikacjaIn an undirected graph G, a subset C⊆V(G) such that C is a dominating set of G, and each vertex in V(G) is dominated by a distinct subset of vertices from C, is called an identifying code of G. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. For a given identifiable graph G, let gammaID(G) be the minimum cardinality of an identifying code in G. In this paper, we show that for any connected...
-
Polynomial triset metric for unrooted phylogenetic trees
Publikacjathe 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.
-
Labyrynths generators, their properties and practical application in computer games
Publikacjathis 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...
-
Ważone umieszczanie grafów jako model optymalizacji komunikacji w sieciach heterogenicznych
PublikacjaUmieszczenie grafu w grafie jest odwzorowaniem pomiędzy parą grafów. Graf umieszczany reprezentuje sieć komunikujących się ze sobą zadań, natomiast graf docelowy dostępną architekturę wykonania tych zadań. Problem polega na takim odwzorowaniu wierzchołków i krawędzi, aby zminimalizować koszty wynikające z potrzeby użycia zastępczych ścieżek w grafie docelowym. W klasycznym modelu przyjmuje się, że oba grafy są proste i ich krawędzie...
-
Exploiting Multi-Interface Networks: Connectivity and Cheapest Paths
PublikacjaRozważano zagadnienie minimalizacji energii w sieciach bezprzewodowych bez infrastruktury, w których niektóre węzły są wyposażone w więcej, niż jeden interfejs. W przyjętym modelu sieci podano nowe algorytmy przybliżone oraz wyniki dotyczące złożoności obliczeniowej dla dwóch problemów: aktywacji najtańszej spójnej podsieci spinającej oraz aktywacji ścieżki pomiędzy ustaloną parą węzłów.
-
On the complexity of distributed graph coloring with local minimality constraints
PublikacjaArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Omówiono algorytmy rozproszone, dające w wyniku pokolorowanie spełniające warunki dla pokolorowań sekwencyjnych typu S oraz Largest-First (LF). Udowodniono również, że każda rozproszona implementacja algorytmu S wymaga co najmniej Omega(log n / log log n) rund, a algorytmu LF co najmniej Omega (n^{1/2}) rund, gdzie n oznacza liczbę wierzchołków grafu.
-
Synchronization helps robots to detect black holes in directed graphs
PublikacjaPraca zawiera nowe wyniki dla problemu poszukiwania czarnej dziury w grafie skierowanym przez zbiór agentów. Czarna dziura jest węzłem niszczącym wszystkich wchodzącej do niej agentów. Pokazano, że w przypadku, gdy stopień wejściowy czarnej dziury wynosi D, do przeszukania grafu skierowanego w modelu synchronicznym wystarcza O(D 2^D) agentów. Wartość ta jest bliska znanemu z literatury oszacowaniu dolnemu Omega (2^D). W pracy pokazano...
-
Connectivity in Multi-Interface Networks
PublikacjaRozważano zagadnienie minimalizacji energii w sieciach bezprzewodowych bez infrastruktury, w których niektóre węzły są wyposażone w więcej, niż jeden interfejs. W przyjętym modelu sieci podano nowe algorytmy przybliżone oraz wyniki dotyczące złożoności obliczeniowej dla problemu najtańszej spójnej podsieci spinającej.
-
Universal Augmentation Schemes for Network Navigability
PublikacjaRozważano problem uzupełniania grafu (reprezentującego np. sieci społeczne) poprzez dodanie w każdym węźle jednego dodatkowego skierowanego połączenia (długodystansowego). Dokładniej, dla każdego węzła definiuje się listę prawdopodobieństw istnienia połączenia wychodzącego z danego węzła do wszystkich pozostałych węzłów; wartości tych prawdopodobieństw muszą sumować się do jedności. Routing zachłanny w takiej sieci polega na przekazywaniu...
-
Euler tour lock-in problem in the rotor-router model
PublikacjaW pracy rozważano model eksploracji grafu nieskierowanego przez pojedynczego agenta, w którym sterowanie agentem odbywa się zgodnie z zasadą ''rotor-router'' (inaczej: ''Propp machine''). Porównano czas stabilizacji agenta do trajektorii w postaci cyklu Eulera dla różnych klas grafów, prowadząc rozważania w kontekście teorii gier. Przydział początkowych portów i wskaźników w modelu jest traktowany jako rozgrywka pomiędzy graczem...
-
Constructing a map of an anonymous graph: applications of universal sequences
PublikacjaWe 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...
-
Exploiting multi-interface networks: Connectivity and Cheapest Paths
PublikacjaLet 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...
-
Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring
PublikacjaOne of the recently considered models of robot-based computing makes use of identical, memoryless mobile units placed in nodes of an anonymous graph. The robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of the nodes adjacent to its current position (Compute), and in the latter case makes an instantaneous...
-
Smartphone application supporting independent movement of the blind
PublikacjaImproving comfort of life of blind people is a problem of great importance. Neither a white canenor a guide dog, although both very useful, can be considered as a tool for achieving fullindependence in everyday movement around the city. On the market there are some navigation toolsinspired by car navigation systems, but they have many flaws, ranging from positioninginaccuracies to high prices. The authors present their own solution...
-
Matching Split Distance for Unrooted Binary Phylogenetic Trees
PublikacjaRekonstrukcja 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...
-
Drawing maps with advice
PublikacjaRozważamy następujący problem obliczeniowy. Agent zostaje umieszczony w wierzchołku nieznanego mu grafu. Wierzchołki grafu są nierozróżnialne, natomiast krawędzie posiadają numery portów. Zadaniem agenta jest wyznaczenie mapy, tzn. obliczenie izomorficznej kopii grafu, lub obliczenie dowolnego drzewa spinającego grafu. Bez dodatkowej informacji zadań tych nie można wykonać. W artykule wyznaczamy oszacowania na minimalną liczbę...
-
Routing equal-size messages on a slotted ring
PublikacjaAnalizujemy problem routingu wiadomości w sieci slotted ring, biorąc pod uwagę dwa kryteria optymalizacyjne: długość uszeregowania oraz liczbę 'cykli' pracy sieci. Optymalny routing dla wiadomości o rozmiarze k jest silnie NP-trudny, natomiast dla k=q, gdzie q jest rozmiarem sieci, można obliczyć w czsie O(n^2log n) dla pierwszego kryterium. Podajemy również algorytm o czasie działania O(nlog n) oraz o stałym współczynniku dobroci....
-
Cost minimisation in multi-interface networks
PublikacjaPraca 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.
-
Cooperative mobile guards in grids
PublikacjaPraca dotyczy problemu strzeżenia dwuwymiarowych krat ortogonalnych, przy założeniu, że obszar widoczności strażnika obejmuje jedną ulicę oraz wszystkie ulice ją przecinające. Rozważano wariant straży słabo współpracujących, w którym dodatkowo każdy strażnik musi widzieć przynajmniej jednego innego strażnika. Podano dowód NP-trudności problemu optymalizacyjnego w przypadku ogólnym, algorytm dokładny o złożoności O(n log n) dla...