Rok 2023

• The complexity of bicriteria tree-depth

  Publikacja

  • P. Borowiecki
  • D. Dereniowski
  • D. Osula

  - THEORETICAL COMPUTER SCIENCE - Rok 2023

  The tree-depth problem can be seen as finding an elimination tree of minimum height for a given input graph G. We introduce a bicriteria generalization in which additionally the width of the elimination tree needs to be bounded by some input integer b. We are interested in the case when G is the line graph of a tree, proving that the problem is NP-hard and obtaining a polynomial-time additive 2b-approximation algorithm. This particular...

  Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2022

• Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times

  Publikacja

  • D. Dereniowski
  • I. Wrosz

  - Rok 2022

  We consider a generalization of binary search in linear orders to the domain of weighted trees. The goal is to design an adaptive search strategy whose aim is to locate an unknown target vertex of a given tree. Each query to a vertex v incurs a non-negative cost ω(v) (that can be interpreted as the duration of the query) and returns a feedback that either v is the target or the edge incident to v is given that is on the path towards...

  Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2021

• An Efficient Noisy Binary Search in Graphs via Median Approximation

  Publikacja

  • D. Dereniowski
  • A. Łukasiewicz
  • P. Uznański

  - LECTURE NOTES IN COMPUTER SCIENCE - Rok 2021

  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 strategy, that identifies an initially unknown target vertex in a graph by asking queries. Each query is conducted as follows: the strategy selects a vertex q and receives a reply v: if q is the target, then =, and if q is not the target, then v is a...

  Pełny tekst do pobrania w serwisie zewnętrznym