Edge and Pair Queries – Random Graphs and Complexity

03/11/2022
by   Dariusz Dereniowski, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset