25 citations · 119 across the 29 of their papers we have counts for
18 papers · 1 filter
Graph Partitioning with Demands: Generalized Conductance and its Applications
Michał Szyfelbein, Dariusz Dereniowski
We study various graph partitioning tasks subject to general demands. In Graph Partitioning with Demands (GPD), the goal is to delete minimum cost supply edge set so that each rema…
Hierarchical -Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs
Michał Szyfelbein, Dariusz Dereniowski
Consider the following variation on the Hierarchical Clustering problem: Usually, while building a hierarchical clustering, one recursively partitions the data until each cluster b…
Precedence-Constrained Decision Trees and Coverings
Michał Szyfelbein, Dariusz Dereniowski
This work considers a number of optimization problems and reductive relations between them. The two main problems we are interested in are the Optimal Decision Tree and Set Cover.…
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{°…
On multidimensional generalization of binary search
Dariusz Dereniowski, Przemysław Gordinowicz, Karolina Wróbel
This work generalizes the binary search problem to a -dimensional domain , where and , in the following way. Giv…
Searching in trees with monotonic query times
Dariusz Dereniowski, Izajasz Wrosz
We consider the following generalization of binary search in sorted arrays to tree domains. In each step of the search, an algorithm is querying a vertex , and as a reply, it re…
Noisy (Binary) Searching: Simple, Fast and Correct
Dariusz Dereniowski, Aleksander Łukasiewicz, Przemysław Uznański
This work considers the problem of the noisy binary search in a sorted array. The noise is modeled by a parameter that dictates that a comparison can be incorrect with probabil…
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…
Building a Nest by an Automaton
Jurek Czyzowicz, Dariusz Dereniowski, Andrzej Pelc
A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid $\mathbb{Z} \times \ma…
A Framework for Searching in Graphs in the Presence of Errors
Dariusz Dereniowski, Stefan Tiegel, Przemysław Uznański +1
We consider the problem of searching for an unknown target vertex in a (possibly edge-weighted) graph. Each \emph{vertex-query} points to a vertex and the response either 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…
Energy Constrained Depth First Search
Shantanu Das, Dariusz Dereniowski, Przemysław Uznański
Depth first search is a natural algorithmic technique for constructing a closed route that visits all vertices of a graph. The length of such route equals, in an edge-weighted tree…
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…
Rendezvous of Distance-aware Mobile Agents in Unknown Graphs
Shantanu Das, Dariusz Dereniowski, Adrian Kosowski +1
We study the problem of rendezvous of two mobile agents starting at distinct locations in an unknown graph. The agents have distinct labels and walk in synchronous steps. However t…
Rendezvous of Heterogeneous Mobile Agents in Edge-weighted Networks
Dariusz Dereniowski, Ralf Klasing, Adrian Kosowski +1
We introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to travers…
Minimum length path decompositions
Dariusz Dereniowski, Wieslaw Kubiak, Yori Zwols
We consider a bi-criteria generalization of the pathwidth problem, where, for given integers and a graph , we ask whether there exists a path decomposition $\cP$ of su…
Connected searching of weighted trees
Dariusz Dereniowski
In this paper we consider the problem of connected edge searching of weighted trees. It is shown that there exists a polynomial-time algorithm for finding optimal connected search…