论文标题
边缘和配对查询 - 随机图和复杂性
Edge and Pair Queries -- Random Graphs and Complexity
论文作者
论文摘要
我们研究了在图，配对查询和边缘查询上玩过的两种类型的查询游戏。我们集中于研究二项式随机图的两个相关图参数，并表明确定两个参数中的任何一个都是有界度图的NP- hard。
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.
