Shotgun Assembly of Labeled Graphs

被引：16

作者：

Mossel, Elchanan ^{[1
,2
]}

Ross, Nathan ^{[3
]}

机构：

[1] Univ Calif Berkeley, Berkeley, CA 94720 USA

[2] Univ Penn, Philadelphia, PA 19104 USA

[3] Univ Melbourne, Sch Math & Stat, Parkville, Vic 3010, Australia

来源：

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING | 2019年 / 6卷 / 02期

基金：

美国国家科学基金会;

关键词：

Random graphs; statistical identifiability; probabilistic algorithms; shotgun assembly; random jigsaw puzzles; DIAMETER;

D O I：

10.1109/TNSE.2017.2776913

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

We consider the problem of reconstructing graphs or labeled graphs from neighborhoods of a given radius r. Special instances of this problem include the well-known: DNA shotgun assembly; the lesser-known: neural network reconstruction; and a new problem: assembling random jigsaw puzzles. We provide some necessary and some sufficient conditions for correct recovery both in combinatorial terms and for some generative models including random labelings of lattices, Erdos-Renyi random graphs, and a random jigsaw puzzle model. Many open problems and conjectures are provided.

引用

页码：145 / 157

页数：13

共 50 条

[21] MIXING TIME OF NEAR-CRITICAL RANDOM GRAPHS
Ding, Jian
Lubetzky, Eyal
Peres, Yuval
ANNALS OF PROBABILITY, 2012, 40 (03) : 979 - 1008
[22] SCALING LIMITS OF RANDOM GRAPHS FROM SUBCRITICAL CLASSES
Panagiotou, Konstantinos
Stufler, Benedikt
Weller, Kerstin
ANNALS OF PROBABILITY, 2016, 44 (05) : 3291 - 3334
[23] On the line graphs of zero-divisor graphs of posets
Khorsandi, Mahdi Reza
Shekofteh, Atefeh
JOURNAL OF ALGEBRA AND ITS APPLICATIONS, 2017, 16 (07)
[24] Chasing a Fast Robber on Planar Graphs and Random Graphs
Alon, Noga
Mehrabian, Abbas
JOURNAL OF GRAPH THEORY, 2015, 78 (02) : 81 - 96
[25] UNIVERSALITY OF RANDOM GRAPHS FOR GRAPHS OF MAXIMUM DEGREE TWO
Kim, Jeong Han
Lee, Sang June
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2014, 28 (03) : 1467 - 1478
[26] The oriented diameter of graphs derived from other graphs
Dankelmann, P.
Guo, Y.
Rivett-Carnac, E. J.
Volkmann, L.
DISCRETE MATHEMATICS, 2025, 348 (06)
[27] Sparse partition universal graphs for graphs of bounded degree
Kohayakawa, Yoshiharu
Roedl, Vojtech
Schacht, Mathias
Szemeredi, Endre
ADVANCES IN MATHEMATICS, 2011, 226 (06) : 5041 - 5065
[28] Models of Random Graphs and Their Applications to the Web-Graph Analysis
Raigorodskii, Andrei
INFORMATION RETRIEVAL, (RUSSIR 2015), 2016, 573 : 101 - 118
[29] On the differential in graphs
Bermudo, S.
Rodriguez, Jose M.
Sigarreta, Jose M.
UTILITAS MATHEMATICA, 2015, 97 : 257 - 270
[30] Cyclic graphs
Göbel, F
Neutel, EA
DISCRETE APPLIED MATHEMATICS, 2000, 99 (1-3) : 3 - 12

← 1 2 3 4 5 →