CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers))
Networks (1097-0037). Vol. 57 (2011), 4, p. 344-350.
[Artikel, refereegranskad vetenskaplig]

Suppose that we have (i) a graph with an unknown edge set, and (ii) access to an oracle that returns all neighbors of a probed vertex. We want to find the hubs, i.e., vertices with degree above a given threshold. An almost obvious two-stage randomized strategy is to query randomly sampled vertices and then their neighbors. We prove that this strategy achieves, in certain classes of sparse graphs, an asymptotically optimal query number among all possible querying strategies, including adaptive strategies. A detail of importance for an optimal constant factor is the number of probes in the neighborhood of a hub candidate. We show that 2 is in general the best choice in the graphs of interest. In a similar way we analyze, in the same model, the problem of finding small, almost dominating sets. The problems and graph classes are motivated mainly by the elucidation of interaction networks in molecular biology.

Nyckelord: learning by queries, degree sequence, sampling, sparse graph, dominating set

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2011-07-14. Senast ändrad 2015-02-11.
CPL Pubid: 143441


Läs direkt!

Länk till annan sajt (kan kräva inloggning)