Geodesic
Edge and pair queries-random graphs and complexity
Dariusz Dereniowski1 ; Przemysław Gordinowicz2 ; Paweł Prałat3
1Faculty of Electronics, Telecommunications and Informatics, Gda\'{n}sk University of Technology, Poland
2Institute of Mathematics, Lodz University of Technology Lódź, Poland
3Department of Mathematics Ryerson University
The electronic journal of combinatorics, Tome 30 (2023) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/11159
Classification : 05C57, 91A43, 05C80, 05C12, 68Q17
Mots-clés : query games, binomial random graphs, bounded degree graphs

Dariusz Dereniowski  1   ; Przemysław Gordinowicz  2   ; Paweł Prałat  3

1 Faculty of Electronics, Telecommunications and Informatics, Gda\'{n}sk University of Technology, Poland
2 Institute of Mathematics, Lodz University of Technology Lódź, Poland
3 Department of Mathematics Ryerson University 
@article{10_37236_11159,
     author = {Dariusz Dereniowski and Przemys{\l}aw Gordinowicz and Pawe{\l} Pra{\l}at},
     title = {Edge and pair queries-random graphs and complexity},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {2},
     doi = {10.37236/11159},
     zbl = {1516.05143},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11159/}
}
TY  - JOUR
AU  - Dariusz Dereniowski
AU  - Przemysław Gordinowicz
AU  - Paweł Prałat
TI  - Edge and pair queries-random graphs and complexity
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11159/
DO  - 10.37236/11159
ID  - 10_37236_11159
ER  - 
%0 Journal Article
%A Dariusz Dereniowski
%A Przemysław Gordinowicz
%A Paweł Prałat
%T Edge and pair queries-random graphs and complexity
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/11159/
%R 10.37236/11159
%F 10_37236_11159
Dariusz Dereniowski; Przemysław Gordinowicz; Paweł Prałat. Edge and pair queries-random graphs and complexity. The electronic journal of combinatorics, Tome 30 (2023) no. 2. doi: 10.37236/11159

Cité par Sources :