Search
Abstract
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.
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Authors (3)
-
Przemysław Gordinowicz
- Lodz University of Technology
-
Paweł Prałat
- Toronto Metropolitan University
Cite as
Full text
download paper
downloaded 32 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.37236/11159
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
ELECTRONIC JOURNAL OF COMBINATORICS
no. 30,
pages 1 - 25,
ISSN: 1077-8926 - Language:
- English
- Publication year:
- 2023
- Bibliographic description:
- Dereniowski D., Gordinowicz P., Prałat P.: Edge and Pair Queries-Random Graphs and Complexity// ELECTRONIC JOURNAL OF COMBINATORICS -,iss. 2 (2023),
- DOI:
- Digital Object Identifier (open in new tab) 10.37236/11159
- Sources of funding:
-
- Partially supported by National Science Centre, Poland, grant number 2018/31/B/ST6/00820.
- Verified by:
- Gdańsk University of Technology
seen 100 times
Recommended for you
An Efficient Noisy Binary Search in Graphs via Median Approximation
- D. Dereniowski,
- A. Łukasiewicz,
- P. Uznański
2021