Year 2023

• The complexity of bicriteria tree-depth

  Publication

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

  - THEORETICAL COMPUTER SCIENCE - Year 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...

  Full text to download in external service

Year 2022

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

  Publication

  • D. Dereniowski
  • I. Wrosz

  - Year 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...

  Full text to download in external service

Year 2021

• An Efficient Noisy Binary Search in Graphs via Median Approximation

  Publication

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

  - LECTURE NOTES IN COMPUTER SCIENCE - Year 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...

  Full text to download in external service