Edge and pair queries-random graphs and complexity
From MaRDI portal
Publication:6162142
DOI10.37236/11159zbMath1516.05143arXiv2203.06006OpenAlexW4379231163MaRDI QIDQ6162142
Dariusz Dereniowski, Przemysław Gordinowicz, Paweł Prałat
Publication date: 15 June 2023
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2203.06006
Random graphs (graph-theoretic aspects) (05C80) Games involving graphs (91A43) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games on graphs (graph-theoretic aspects) (05C57)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the tree search problem with non-uniform costs
- Metric dimension for random graphs
- Centroidal localization game
- LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth
- Localization game on geometric and planar graphs
- A note on the localization number of random graphs: diameter two case
- The binary identification problem for weighted trees
- Locating a robber on a graph via distance queries
- Localization game for random graphs
- Localization game for random geometric graphs
- An efficient noisy binary search in graphs via Median approximation
- The localization capture time of a graph
- On the limiting distribution of the metric dimension for random forests
- Locating a backtracking robber on a tree
- Tree-depth, subgraph coloring and homomorphism bounds
- Edge ranking of weighted trees
- On Minimum Edge Ranking Spanning Trees
- On Binary Searching with Nonuniform Costs
- Introduction to Random Graphs
- The Role of Elimination Trees in Sparse Factorization
- The Diameter of Random Graphs
- Optimal Search in Trees
- Computing with Noisy Information
- Centroidal bases in graphs
- Twenty (simple) questions
- Bounds on the localization number
- Deterministic and probabilistic binary search in graphs
This page was built for publication: Edge and pair queries-random graphs and complexity
