Source author record

Dorota Osula

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics Computational Complexity Data Structures and Algorithms

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2018arXiv

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 an open question raised by Fedor V. Fomin during the GRASTA 2017 workshop, since connected pathwidth is equivalent to the connected (monotone) node search game.

preprint2017arXiv

The Snow Team Problem (Clearing Directed Subgraphs by Mobile Agents)

We 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~ $\mathcal{S}$ of vertices of a digraph $D$ and a positive integer $k$ , the objective is to determine whether there is a subgraph $H=(\mathcal{V}_H,\mathcal{A}_H)$ of $D$ such that (a) $\mathcal{S} \subseteq \mathcal{V}_H$ , (b) $H$ is the union of $k$ directed walks in $D$ , and (c) the underlying graph of $H$ includes a Steiner tree for $\mathcal{S}$ in $D$ . We provide several results on the polynomial time tractability, hardness, and parameterized complexity of the problem.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.