文章基本信息

标题：Reconstruction of Trees from Jumbled and Weighted Subtrees
本地全文：下载
作者：D{\'e}nes Bartha ; Peter Burcsi ; Zsuzsanna Lipt{\'a}k 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：54
页码：10:1-10:13
DOI：10.4230/LIPIcs.CPM.2016.10
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Let T be an edge-labeled graph, where the labels are from a finite alphabet Sigma. For a subtree U of T the Parikh vector of U is a vector of length |Sigma| which specifies the multiplicity of each label in U. We ask when T can be reconstructed from the multiset of Parikh vectors of all its subtrees, or all of its paths, or all of its maximal paths. We consider the analogous problems for weighted trees. We show how several well-known reconstruction problems on labeled strings, weighted strings and point sets on a line can be included in this framework. We present reconstruction algorithms and non-reconstructibility results, and extend the polynomial method, previously applied to jumbled strings [Acharya et al., SIAM J. on Discr. Math, 2015] and weighted strings [Bansal et al., CPM 2004], to deal with general trees and special tree classes.
关键词：trees; paths; Parikh vectors; reconstruction problems; homometric sets; polynomial method; jumbled strings; weighted strings