Wyszukiwarka
Filtry
wszystkich: 76
wybranych: 72
-
Katalog
Filtry wybranego katalogu
Wyniki wyszukiwania dla: ZŁOŻONOŚĆ OBLICZENIOWA
-
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.
-
Optymalne pokolorowania średnicowe dla wybranych klas grafów
PublikacjaW pracy opisano wybrane właściwości szczególnego przypadku radiowego kolorowania grafów, zwanego kolorowaniem średnicowym. Podano zasadę działania algorytmu optymalnego kolorowania średnicowego i oszacowania liczby średnicowej grafu w przypadku ogólnym oraz dla ścieżek i cykli. Korzystając z podanego algorytmu, znaleziono dokładne wartości liczby średnicowej dla ścieżek i cykli niewielkiej długości, co pozwoliło na obalenie wcześniej...
-
Cztery algorytmy, które wstrząsnęły światem. Część II: Od czasu wykładniczego do wielomianowego
PublikacjaOdcinek ten poświęcony jest problemowi programowania liniowego oraz problemowi badania liczb pierwszych.
-
Cztery algorytmy które wstrząsnęły światem. Część I: Rys historyczny
PublikacjaOpracowanie jest pierwszym fragmentem 3-częściowego szkicu popularnonaukowego poświęconego najważniejszym osiągnięciom w dziedzinie algorytmiki teoretycznej. Wprowadzono w w arkana złożoności obliczeniowej i sztuki programowania komputerów.
-
On Tradeoffs Between Width- and Fill-like Graph Parameters
PublikacjaIn this work we consider two two-criteria optimization problems: given an input graph, the goal is to find its interval (or chordal) supergraph that minimizes the number of edges and its clique number simultaneously. For the interval supergraph, the problem can be restated as simultaneous minimization of the path width pw(G) and the profile p(G) of the input graph G. We prove that for an arbitrary graph G and an integer t ∈ {1,...
-
Clearing directed subgraphs by mobile agents
PublikacjaWe 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...
-
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...
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach
PublikacjaW kolejnym odcinku serii z Alicją i Bogdanem najpierw ilustrujemy problem dominowania w grafach (kratowych): klasyczny i rzymski. Następnie ilustrujemy znany fakt, że zachłanność nie zawsze się opłaca. Pokażemy mianowicie, że algorytmy zachłanne nie gwarantują uzyskania rozwiązania optymalnego, nawet wówczas gdy problem da się rozwiązać w czasie wielomianowym.
-
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.
-
Complexity of weak acceptonic conditions in tree automata
PublikacjaRozważano złożoność problemu pustości dla automatów na drzewach ze słabymi warunkami akceptowalności. Rozważano także translacje pomiędzy słabymi i silnymi warunkami akceptowalności.
-
Sumacyjne kolorowanie grafów
PublikacjaW tym rozdziale, oprócz szczegółowego zaprezentowania koncepcji sumy chroma-tycznej, jej własności oraz wyników z nią związanych, dokonano analizy zło-żoności problemu sumacyjnego kolorowania dla wybranych klas grafów, w szcze-gólności rozróżniono klasy grafów, dla których problem sumacyjnego kolorowa-nia można rozwiązać w czasie wielomianowym oraz przypadki NP-trudne.
-
Szeregowanie zadań sprzężonych metodą kolorowania grafów
PublikacjaRozważono problem szeregowania zadań sprzężonych na pojedynczym procesorze w obecności ograniczeń kolejnościowych. Zidentyfikowano przypadki wielomianowe dla tego zagadnienia NP-trudnego.
-
Metoda chromatyczna i jej zastosowania techniczne
PublikacjaArtykuł ma charakter przeglądowy. Przedstawiono w nim najważniejsze modele koloryzowania grafów i ich zastosowania w wybranych problemach technicznych. Ponieważ jest to wiodąca tematyka badawcza Katedry Podstaw Informatyki Wydziału ETI Politechniki Gdańskiej, praca służy również upowszechnianiu dorobku naukowego pracowników Katedry oraz osób z nią współpracujących w opisywanej dziedzinie.
-
Wybrane zastosowania niestandardowych modeli kolorowania w szeregowniu dwu-procesowych zadań jednostkowych
PublikacjaNiniejsza praca poświęcona jest wykorzystaniu teorii chromatycznej grafów wszeregowaniu. Koncepcja ta polega na przedstawieniu zbioru zadań w postaci krawędzi tzw. grafu konfliktów.
-
Szeregowanie zadań metodami kolorowania grafów.Monografie 37.
PublikacjaNiniejsza praca poświęcona jest wykorzystaniu teorii chromatycznej grafów w szeregowaniu. Koncepcja ta polega na przedstawieniu zbioru zadań w postaci krawędzi tzw. grafu konfliktów.
-
NP-completeness of convex and weakly convex domiating set decision problems.
PublikacjaLiczby dominowania wypukłego i słabo wypukłego są nowymi rodzajami liczb dominowania. W tym artykule pokazujemy, że problemy decyzyjne dominowania wypukłegi i słabo wypukłego są NP-zupełne w przypadku grafów dwudzielnych oraz split grafów. Posługując się zmodyfikowanym algorytmem Washalla możemy w czasie wielomianowym określić, czy dany podzbiór wierzchołków grafu jest spójny bądź słabo spójny.
-
Classical coloring of graphs.
PublikacjaRozdział obejmuje klasyczne kolorowanie krawędzi i wierzołków w grafach prostych. Oprócz podstawowych definicji podane zostały najczęściej stosowane metody przybliżone oraz ich właściwości. Dodatkowo rozdział zawiera przegląd znanych benczmarków dla podanych metod w kontekście klasycznego modelu kolorowania.
-
Chromatyczne szeregowanie zadań w cyklicznych systemach produkcyjnych.
PublikacjaGłównym celem pracy jest klasyfikacja złożoności obliczeniowej problemu szeregowania zadań w przypadku cyklicznej pracy systemu produkcyjnego. Rozważane są przy tym trzy modele szeregowania: system zadań dwuprocesorowych, system otwarty i system przepływowy. Kryterium optymalizacyjnym które jest analizowane jest długość cyklu wyrażająca częstość realizacji poszczególnych zestawów operacji. W pracy posługiwano się teorią grafów...
-
Cykliczny system otwarty z ograniczeniami obustronnych przestojów
PublikacjaW pracy badany jest system otwarty, który pracuje cyklicznie, tj. po ukończeniu jednego zestawu zadań przetwarzany jest kolejny zestaw identycznych zadań. Narzucone jest przy tym ograniczenie polegające na braku przestojów zarówno po stronie procesów jak i zadań. Wykazana jest NP-trudność problemu konstrukcji uszeregowania spełniającego te założenia jak i problemu minimalizacji długość i cyklu.
-
Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesorowych w oknach czasowych
PublikacjaSzeregowanie jednostkowych zadań 1- i 2-procesorowych z dodatkowym ograniczeniem w postaci zróżnicowanych okien czasowych, w których zadania te mogą być wykonywane zamodelowano przy pomocy listowego kolorowania i multikolorowania krawędzi grafów. Kryteria jakości harmonogramu: maksymalny koszt wykonania zadania w jednostce czasu oraz suma tychże kosztów po wszystkich zadaniach można przedstawić rozszerzając kolorowanie listowe...
-
Parallel scheduling by graph ranking
PublikacjaNr dokum.: 73017Praca dotyczy jednego z nieklasycznych modeli kolorowania grafów - uporządkowanego kolorowania. Celem było uzyskanie wyników, które mogo być wykorzystane w praktycznych zastosowaniach tego modelu, do których należą: równoległe przetwarzanie zapytań w relacyjnych bazach danych, równoległa faktoryzacja macierzy metodą Choleskiego, równoległa asemblacja produktu z jego części składowych. W pracy wskazano uogólnienia...