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.
Autorzy
- prof. dr hab. inż. Dariusz Dereniowski link otwiera się w nowej karcie ,
- Przemysław Gordinowicz,
- Paweł Prałat
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.37236/11159
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuły w czasopismach
- Język
- angielski
- Rok wydania
- 2023
Źródło danych: MOSTWiedzy.pl - publikacja "Edge and Pair Queries-Random Graphs and Complexity" link otwiera się w nowej karcie
