Informacje szczegółowe
- Program finansujący:
- OPUS
- Instytucja:
- Narodowe Centrum Nauki (NCN) (National Science Centre)
- Porozumienie:
- UMO-2018/31/B/ST6/00820 z dnia 2019-06-28
- Okres realizacji:
- 2019-06-28 - 2024-06-27
- Kierownik projektu:
- prof. dr hab. inż. Dariusz Dereniowski
- Realizowany w:
- Katedra Algorytmów i Modelowania Systemów
- Wartość projektu:
- 480 200.00 PLN
- Typ zgłoszenia:
- Krajowy Program Badawczy
- Pochodzenie:
- Projekt krajowy
- Weryfikacja:
- Politechnika Gdańska
Publikacje powiązane z tym projektem
Filtry
wszystkich: 3
Katalog Projektów
Rok 2023
-
The complexity of bicriteria tree-depth
PublikacjaThe 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...
Rok 2022
-
Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times
PublikacjaWe 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...
Rok 2021
-
An Efficient Noisy Binary Search in Graphs via Median Approximation
PublikacjaConsider 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...
wyświetlono 301 razy