How large is your graph?
We consider the problem of estimating the graph size, where one is given only local access to the graph. We formally define a query model in which one starts with a seed node and is allowed to make queries about neighbours of nodes that have already been seen. In the case of undirected graphs, an es...
Main Authors: | Kanade, V, Mallmann-Trenn, F, Verdugo, V |
---|---|
Format: | Conference item |
Published: |
Schloss Dagstuhl
2017
|
Similar Items
-
Brief Announcement: How large is your graph?
by: Kanade, V, et al.
Published: (2017) -
On coalescence time in graphs: When is coalescing as fast as meeting?
by: Kanade, V, et al.
Published: (2019) -
On coalescence time in graphs–when is coalescing as fast as meeting?
by: Kanade, V, et al.
Published: (2023) -
Hierarchical clustering beyond the worst-case
by: Cohen-Addad, V, et al.
Published: (2018) -
Clustering redemption–beyond the impossibility of Kleinberg’s axioms
by: Cohen-Addad, V, et al.
Published: (2018)