Edge and pair queries-random graphs and complexity (Q6162142)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Edge and pair queries-random graphs and complexity |
scientific article; zbMATH DE number 7696239
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.7857024073600769
0 references
0.7598983645439148
0 references
0.7409875392913818
0 references
0.7382027506828308
0 references
