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 条
  • [41] NONBACKTRACKING SPECTRUM OF RANDOM GRAPHS: COMMUNITY DETECTION AND NONREGULAR RAMANUJAN GRAPHS
    Bordenave, Charles
    Lelarge, Marc
    Massoulie, Laurent
    ANNALS OF PROBABILITY, 2018, 46 (01) : 1 - 71
  • [42] Cops and Robber Game with a Fast Robber on Expander Graphs and Random Graphs
    Abbas Mehrabian
    Annals of Combinatorics, 2012, 16 : 829 - 846
  • [43] Cross over of recurrence networks to random graphs and random geometric graphs
    RINKU JACOB
    K P HARIKRISHNAN
    R MISRA
    G AMBIKA
    Pramana, 2017, 88
  • [44] Reciprocal complementary Wiener numbers of trees, unicyclic graphs and bicyclic graphs
    Cai, Xiochun
    Zhou, Bo
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (14) : 3046 - 3054
  • [45] Strong Geodetic Number of Complete Bipartite Graphs and of Graphs with Specified Diameter
    Irsic, Vesna
    GRAPHS AND COMBINATORICS, 2018, 34 (03) : 443 - 456
  • [46] Cops and Robber Game with a Fast Robber on Expander Graphs and Random Graphs
    Mehrabian, Abbas
    ANNALS OF COMBINATORICS, 2012, 16 (04) : 829 - 846
  • [47] Strong Geodetic Number of Complete Bipartite Graphs and of Graphs with Specified Diameter
    Vesna Iršič
    Graphs and Combinatorics, 2018, 34 : 443 - 456
  • [48] On Some Parameters of the Central Graphs of the Identity Graphs of Finite Cyclic Groups
    Alib, Clarence T.
    Magpantay, Daryl M.
    EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2022, 15 (03): : 1098 - 1112
  • [49] Cross over of recurrence networks to random graphs and random geometric graphs
    Jacob, Rinku
    Harikrishnan, K. P.
    Misra, R.
    Ambika, G.
    PRAMANA-JOURNAL OF PHYSICS, 2017, 88 (02):
  • [50] ON THE LINE GRAPHS ASSOCIATED TO THE ZERO-DIVISOR GRAPHS OF COMMUTATIVE RINGS
    Chiang-Hsieh, Hung-Jen
    Lee, Pei-Feng
    Wang, Hsin-Ju
    HOUSTON JOURNAL OF MATHEMATICS, 2013, 39 (01): : 61 - 72
12345