Search
Filters
total: 60
filtered: 57
-
Catalog
Chosen catalog filters
Search results for: ZŁOŻONOŚĆ OBLICZĘNIOWA
-
Clearing directed subgraphs by mobile agents
PublicationWe 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...
-
Shared processor scheduling of multiprocessor jobs
PublicationWe study a problem of shared processor scheduling of multiprocessor weighted jobs. Each job can be executed on its private processor and simultaneously on possibly many processors shared by all jobs. This simultaneous execution reduces their completion times due to the processing time overlap. Each of the m shared processors may charge a different fee but otherwise the processors are identical. The goal is to maximize the total...
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w różnych sytuacjach. Alicja i Bogdan wśród ludożerców
PublicationWprowadzono do zagadnień złożoności czasowej i pamięciowej
-
Building a Nest by an Automaton
PublicationA robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid $Z x Z$. Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the {\em field}, is initially connected. The (Manhattan) distance between the farthest cells of the field is called its {\em span}. The robot...
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w różnych sytuacjach. Alicja i Bogdan w krainie czarów
PublicationWprowadzono w zagadnienia NP-zupełności na przykładzie problemu Suma Podzbioru
-
Finding small-width connected path decompositions in polynomial time
PublicationA connected path decomposition of a simple graph $G$ is a path decomposition $(X_1,\ldots,X_l)$ such that the subgraph of $G$ induced by $X_1\cup\cdots\cup X_i$ is connected for each $i\in\{1,\ldots,l\}$. The connected pathwidth of $G$ is then the minimum width over all connected path decompositions of $G$. We prove that for each fixed $k$, the connected pathwidth of any input graph can be computed in polynomial-time. This answers...
-
Cops, a fast robber and defensive domination on interval graphs
PublicationThe game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”,...