Edge and pair queries-random graphs and complexity (Q6162142): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 07:50, 10 July 2024
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
