The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.
Network Discovery and Verification
Open accessAbstract
Consider the problem of discovering (or verifying) the edges and non-edges of a network, modeled as a connected undirected graph, using a minimum number of queries. A query at a vertex v discovers (or verifies) all edges and non-edges whose endpoints have different distance from v. In the network discovery problem, the edges and non-edges are initially unknown, and the algorithm must select the next query based only on the results of previous queries. We study the problem using competitive analysis and give a randomized on-line algorithm with competitive ratio $O(\sqrt{nlogn})$ for graphs with n vertices. We also show that no deterministic algorithm can have competitive ratio better than 3. In the network verification problem, the graph is known in advance and the goal is to compute a minimum number of queries that verify all edges and non-edges. This problem has previously been studied as the problem of placing landmarks in a graph or determining the metric dimension of a graph. We show that there is no approximation algorithm for this problem with ratio o(log n) unless $\mathcal{P} = \mathcal{NP}$ .
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
Erdős, P., & Rényi, A. (2022) · Publicationes Mathematicae Debrecen · doi:10.5486/pmd.1959.6.3-4.12 · Cited by 5,337
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
On inferring autonomous system relationships in the Internet
Gao, L. (2001) · IEEE/ACM Transactions on Networking · doi:10.1109/90.974527 · Cited by 1,070
Probabilistic computations: Toward a unified measure of complexity
Yao, A. C.-C. (1977) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1977.24 · Cited by 982
Heuristics for Internet map discovery
Govindan, R., & Tangmunarunkit, H. (2002) · Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064) · doi:10.1109/infcom.2000.832534 · Cited by 687
On Metric Generators of Graphs
Sebö, A., & Tannier, É. (2004) · Mathematics of Operations Research · doi:10.1287/moor.1030.0070 · Cited by 499
Size-dependent degree distribution of a scale-free growing network
Dorogovtsev, S. N., Mendes, J. F. F., & Samukhin, A. N. (2001) · Physical Review E · doi:10.1103/physreve.63.062101 · Cited by 311
The power of team exploration: two robots can learn unlabeled directed graphs
Bender, M. A., & Slonim, D. K. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365703 · Cited by 184
On the bias of traceroute sampling: or, power-law degree distributions in regular graphs
Achlioptas, D., Clauset, A., Kempe, D., & Moore, C. (2005) · Proceedings of the thirty-seventh annual ACM symposium on Theory of computing · doi:10.1145/1060590.1060693 · Cited by 163
Exploring networks with traceroute-like probes: Theory and simulations
Dall’Asta, L., Alvarez-Hamelin, J. I., Barrat, A., Vázquez, A., & Vespignani, A. (2006) · Theoretical Computer Science · doi:10.1016/j.tcs.2005.12.009 · Cited by 156
Improved low-degree testing and its applications
Arora, S., & Sudan, M. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258642 · Cited by 150
Computing the Types of the Relationships Between Autonomous Systems
Battista, G. D., Erlebach, T., Hall, A., Patrignani, M., Pizzonia, M., & Schank, T. (2007) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2007.892878 · Cited by 103
Self-citationStatistical theory of Internet exploration
Dall’Asta, L., Alvarez-Hamelin, J. I., Barrat, A., Vázquez, A., & Vespignani, A. (2005) · Physical Review E · doi:10.1103/physreve.71.036135 · Cited by 30
Cited by
Proposed Security Model and Threat Taxonomy for the Internet of Things (IoT)
Babar, S., Mahalle, P., Stango, A., Prasad, N., & Prasad, R. (2010) · Communications in Computer and Information Science · doi:10.1007/978-3-642-14478-3_42 · Cited by 278
Metadata
- Authors
- Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Mihaľák, M., & Ram, L. S.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2005
- Volume
- 24
- Issue
- 12
- Pages
- 127-138
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W1958462902
- Cited by
- 351
- References
- 14
- FWCI
- 1.92
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.