Dorota Osula - Profil naukowy - MOST Wiedzy

Wyszukiwarka

Wybrane publikacje

  • Finding small-width connected path decompositions in polynomial time

    A 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...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • On the connected and weakly convex domination numbers

    In this paper we study relations between connected and weakly convex domination numbers. We show that in general the difference between these numbers can be arbitrarily large and we focus on the graphs for which a weakly convex domination number equals a connected domination number. We also study the influence of the edge removing on the weakly convex domination number, in particular we show that a weakly convex domination number...

    Pełny tekst do pobrania w portalu

  • Multi-agent graph searching and exploration algorithms

    - Rok 2020

    A team of mobile entities, which we refer to as agents or searchers interchangeably, starting from homebases needs to complete a given task in a graph.The goal is to build a strategy, which allows agents to accomplish their task. We analyze strategies for their effectiveness (e.g., the number of used agents, the total number of performed moves by the agents or the completion time).Currently, the fields of on-line (i.e., agents...

    Pełny tekst do pobrania w portalu

wyświetlono 175 razy