Edge and Pair Queries-Random Graphs and Complexity

  • Dariusz Dereniowski
  • Przemysław Gordinowicz
  • Paweł Prałat
DOI: https://doi.org/10.37236/11159

Abstract

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.

Published
2023-06-02
Issue
Volume 30, Issue 2 (2023)
Article Number
P2.34