Wyszukiwarka
Abstrakt
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.
Cytowania
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Autorzy (3)
-
Przemysław Gordinowicz
- Lodz University of Technology
-
Paweł Prałat
- Toronto Metropolitan University
Cytuj jako
Pełna treść
pobierz publikację
pobrano 31 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.37236/11159
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
ELECTRONIC JOURNAL OF COMBINATORICS
nr 30,
strony 1 - 25,
ISSN: 1077-8926 - Język:
- angielski
- Rok wydania:
- 2023
- Opis bibliograficzny:
- Dereniowski D., Gordinowicz P., Prałat P.: Edge and Pair Queries-Random Graphs and Complexity// ELECTRONIC JOURNAL OF COMBINATORICS -,iss. 2 (2023),
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.37236/11159
- Źródła finansowania:
-
- Partially supported by National Science Centre, Poland, grant number 2018/31/B/ST6/00820.
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 99 razy
Publikacje, które mogą cię zainteresować
An Efficient Noisy Binary Search in Graphs via Median Approximation
- D. Dereniowski,
- A. Łukasiewicz,
- P. Uznański
2021