Rok 2019

• On Tradeoffs Between Width- and Fill-like Graph Parameters

  Publikacja

  • D. Dereniowski
  • A. Stański

  - THEORY OF COMPUTING SYSTEMS - Rok 2019

  In 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,...

  Pełny tekst do pobrania w portalu

• On-line Search in Two-Dimensional Environment

  Publikacja

  • D. Dereniowski
  • D. Osula

  - THEORY OF COMPUTING SYSTEMS - Rok 2019

  We consider the following on-line pursuit-evasion problem. A team of mobile agents called searchers starts at an arbitrary node of an unknown network. Their goal is to execute a search strategy that guarantees capturing a fast and invisible intruder regardless of its movements using as few searchers as possible. We require that the strategy is connected and monotone, that is, at each point of the execution the part of the graph...

  Pełny tekst do pobrania w portalu

Rok 2018

• Collaborative Exploration of Trees by Energy-Constrained Mobile Robots

  Publikacja

  • S. Das
  • D. Dereniowski
  • C. Karousatou

  - THEORY OF COMPUTING SYSTEMS - Rok 2018

  We study the problem of exploration of a tree by mobile agents (robots) that have limited energy. The energy constraint bounds the number of edges that can be traversed by a single agent. We use a team of agents to collectively explore the tree and the objective is to minimize the size of this team. The agents start at a single node, the designated root of the tree and the height of the tree is assumed to be less than the energy...

  Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2013

• Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains

  Publikacja

  • J. Czyzowicz
  • A. Kosowski
  • A. Pelc

  - THEORY OF COMPUTING SYSTEMS - Rok 2013

  We consider two versions of the rendezvous problem: exact RV, when the points representing agents have to coincide at some time, and e-RV, when these points have to get at distance less than e in the terrain. In any terrain, each agent chooses its trajectory, but the movements of the agent on this trajectory are controlled by an adversary that may, e.g. speed up or slow down the agent.

  Pełny tekst do pobrania w serwisie zewnętrznym