The trace reconstruction problem for spider graphs

DOI10.1016/J.DISC.2022.113115MaRDI QIDQ2092331zbMATH OpenOpenAlexFDO

Authors Alec Sun, William Yue

Publication date 2 November 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.08166

zbMATH Keywords

graph algorithmsLittlewood polynomialstrace reconstruction

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Theory of computing (68Qxx) Algorithms on strings (68W32)

Recommendations

• Reconstructing trees from traces
• Trace reconstruction revisited
• Trace reconstruction with \(\exp(O(n^{1/3}))\) samples
• Trace reconstruction with varying deletion probabilities
• Trace reconstruction: generalized and parameterized

Cites work

• Coded Trace Reconstruction
• Global alignment of molecular sequences via ancestral state reconstruction
• scientific article; zbMATH DE number 5764889 (Why is no real title available?)
• scientific article; zbMATH DE number 5764890 (Why is no real title available?)
• Lower bounds for trace reconstruction
• New lower bounds for trace reconstruction
• Optimal mean-based algorithms for trace reconstruction
• Reconstructing strings from random traces
• Reconstruction of objects from a minimum number of distorted patterns
• Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
• Trace Reconstruction Problems in Computational Biology
• Trace reconstruction revisited
• Trace reconstruction with \(\exp(O(n^{1/3}))\) samples
• Trace reconstruction with varying deletion probabilities
• Trace Reconstruction: Generalized and Parameterized

Cited in

(1)

• Near-optimal trace reconstruction for mildly separated strings

This page was built for publication: The trace reconstruction problem for spider graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2092331)