A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Solving the induced subgraph problem in the randomized multiparty simultaneous messages model
Tekijät: Kari J., Matamala M., Rapaport I., Salo V.
Toimittaja: Christian Scheideler
Konferenssin vakiintunut nimi: International Colloquium on Structural Information and Communication Complexity
Kustantaja: Springer Verlag
Kustannuspaikka: Berlin
Julkaisuvuosi: 2015
Kokoomateoksen nimi: 22nd International Colloquium on Structural Information and Communication Complexit
Tietokannassa oleva lehden nimi: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Sarjan nimi: Lecture Notes in Computer Science
Numero sarjassa: 9439
Vuosikerta: 9439
Aloitussivu: 370
Lopetussivu: 384
ISBN: 978-3-319-25257-5
DOI: https://doi.org/10.1007/978-3-319-25258-2_26
Verkko-osoite: http://api.elsevier.com/content/abstract/scopus_id/84950327338
We study the message size complexity of recognizing, under the broadcast congested clique model, whether a fixed graph H appears in a given graph G as a minor, as a subgraph or as an induced subgraph. The n nodes of the input graph G are the players, and each player only knows the identities of its immediate neighbors. We are mostly interested in the one-round, simultaneous setup where each player sends a message of size O(logn) to a referee that should be able then to determine whether H appears in G. We consider randomized protocols where the players have access to a common random sequence. We completely characterize which graphs H admit such a protocol. For the particular case where H is the path of 4 nodes, we present a new notion called twin ordering, which may be of independent interest.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
