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 条
  • [31] On the nullity of graphs
    Cheng, Bo
    Liu, Bolian
    ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2007, 16 : 60 - 67
  • [32] FLIPS IN GRAPHS
    Bohman, Tom
    Dudek, Andrzej
    Frieze, Alan
    Pikhurko, Oleg
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (03) : 1046 - 1055
  • [33] Lazy Cops and Robbers played on random graphs and graphs on surfaces
    Bal, Deepak
    Bonato, Anthony
    Kinnersley, William B.
    Pralat, Pawel
    JOURNAL OF COMBINATORICS, 2016, 7 (04) : 627 - 642
  • [34] Synthesis of function-described graphs and clustering of attributed graphs
    Serratosa, F
    Alquézar, R
    Sanfeliu, A
    INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 2002, 16 (06) : 621 - 655
  • [35] Treewidth of Erdos-Renyi random graphs, random intersection graphs, and scale-free random graphs
    Gao, Yong
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (4-5) : 566 - 578
  • [36] Scale-free network clustering in hyperbolic and other random graphs
    Stegehuis, Clara
    van Der Hofstad, Remco
    van Leeuwaarden, Johan S. H.
    JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2019, 52 (29)
  • [37] Diameter in ultra-small scale-free random graphs
    Caravenna, Francesco
    Garavaglia, Alessandro
    van der Hofstad, Remco
    RANDOM STRUCTURES & ALGORITHMS, 2019, 54 (03) : 444 - 498
  • [38] Distance problems within Helly graphs and k-Helly graphs
    Ducoffe, Guillaume
    THEORETICAL COMPUTER SCIENCE, 2023, 946
  • [39] Phase transitions on fixed connected graphs and random graphs in the presence of noise
    Liu, Jialing
    Yadav, Vikas
    Sehgal, Hullas
    Olson, Joshua M.
    Liu, Haifeng
    Elia, Nicola
    IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2008, 53 (08) : 1817 - 1825
  • [40] Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
    Benjamini, Itai
    Chan, Siu-On
    O'Donnell, Ryan
    Tamuz, Omer
    Tan, Li-Yang
    STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2016, 126 (09) : 2719 - 2733
12345