Search results for: query complexity - Bridge of Knowledge

Search

Search results for: query complexity

Search results for: query complexity

  • An Efficient Noisy Binary Search in Graphs via Median Approximation

    Publication

    - 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

  • Interactive Query Expansion with the Use of Clustering by Directions Algorithm

    This paper concerns Clustering by Directions algorithm. The algorithm introduces a novel approach to interactive query expansion. It is designed to support users of search engines in forming web search queries. When a user executes a query, the algorithm shows potential directions in which the search can be continued. This paper describes the algorithm and it presents an enhancement which reduces the computational complexity of...

  • A Framework for Searching in Graphs in the Presence of Errors

    Publication

    - Year 2019

    We consider a problem of searching for an unknown target vertex t in a (possibly edge-weighted) graph. Each vertex-query points to a vertex v and the response either admits that v is the target or provides any neighbor s of v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh-Zadeh et al. [STOC 2016]. In the latter, the authors provide...

    Full text to download in external service

  • The complexity of bicriteria tree-depth

    Publication

    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

  • Nowe wyzwania, nowe rozwiązania. Jak przedsiębiorstwo branży IT odnajduje się w erze VUCA?

    Publication

    - e-mentor - Year 2023

    Zmienność, niepewność, złożoność i niejednoznaczność, określane akronimem VUCA (volatility, uncertainty, complexity, ambiguity) towarzyszą funkcjonowaniu każdego przedsiębiorstwa. Jak wykorzystać te nieodłączne cechy otoczenia przedsiębiorstw jako szanse dla ich rozwoju to wy-zwania stojące przed nimi, a zarazem pytanie badawcze artykułu. Celem artykułu jest wykazanie, na przykładzie przedsiębiorstwa branży IT, że analiza zmienności,...

    Full text available to download

  • Edge and Pair Queries-Random Graphs and Complexity

    Publication

    - ELECTRONIC JOURNAL OF COMBINATORICS - Year 2023

    We investigate two types of query games played on a graph, pair queries and edge queries. We concentrate on investigating the two associated graph parameters for binomial random graphs, and showing that determining any of the two parameters is NP-hard for bounded degree graphs.

    Full text available to download

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

    Publication

    - 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