Edge and pair queries-random graphs and complexity (Q6162142)
From MaRDI portal
scientific article; zbMATH DE number 7696239
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Edge and pair queries-random graphs and complexity |
scientific article; zbMATH DE number 7696239 |
Statements
Edge and pair queries-random graphs and complexity (English)
0 references
15 June 2023
0 references
Summary: 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.
0 references
query games
0 references
binomial random graphs
0 references
bounded degree graphs
0 references
