10 citations · 10 across the 1 of their papers we have counts for
5 papers · 1 filter
Low-degree spanning trees of -edge-connected graphs in linear time
Dariusz Dereniowski, Janusz Dybizbański, Przemysław Karpiński +2
We present a simple linear-time algorithm that finds a spanning tree of a given -edge-connected graph such that each vertex of has degree at most $\lceil \frac{°…
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…
An Efficient Noisy Binary Search in Graphs via Median Approximation
Dariusz Dereniowski, Aleksander Łukasiewicz, Przemysław Uznański
Consider a generalization of the classical binary search problem in linearly sorted data to the graph-theoretic setting. The goal is to design an adaptive query algorithm, called a…
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…
Approximation Strategies for Generalized Binary Search in Weighted Trees
Dariusz Dereniowski, Adrian Kosowski, Przemyslaw Uznanski +1
We consider the following generalization of the binary search problem. A search strategy is required to locate an unknown target node in a given tree . Upon querying a node…