Details
- Financial Program Name:
- OPUS
- Organization:
- Narodowe Centrum Nauki (NCN) (National Science Centre)
- Agreement:
- UMO-2018/31/B/ST6/00820 z dnia 2019-06-28
- Realisation period:
- 2019-06-28 - 2024-06-27
- Project manager:
- prof. dr hab. inż. Dariusz Dereniowski
- Realised in:
- Department of Algorithms and Systems Modelling
- Project's value:
- 480 200.00 PLN
- Request type:
- National Research Programmes
- Domestic:
- Domestic project
- Verified by:
- Gdańsk University of Technology
Papers associated with that project
Filters
total: 3
Catalog Projects
Year 2023
-
The complexity of bicriteria tree-depth
PublicationThe 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...
Year 2022
-
Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times
PublicationWe 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...
Year 2021
-
An Efficient Noisy Binary Search in Graphs via Median Approximation
PublicationConsider 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...
seen 301 times