3 papers
cs.DS2021
The Complexity of Bicriteria Tree-Depth
Piotr Borowiecki, Dariusz Dereniowski, Dorota Osula
The tree-depth problem can be seen as finding an elimination tree of minimum height for a given input graph . We introduce a bicriteria generalization in which additionally the…
math.CO2019
On the connected and weakly convex domination numbers
Magda Dettlaff, Magdalena Lemańska, Dorota Osula +1
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 w…
cs.DS2018
Finding small-width connected path decompositions in polynomial time
Dariusz Dereniowski, Dorota Osula, Paweł Rzążewski
A connected path decomposition of a simple graph is a path decomposition such that the subgraph of induced by is connected for ea…