Low-Port Tree Representations

机译：低端口树表示

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

Consider an n-node undirected graph G(V, E) with a pre-assigned port numbering for the outgoing edges of each node. The port numbers assigned to a node u of degree deg(u) are {0,1,..., deg(u) — 1}. In certain contexts it is necessary to maintain a directed spanning tree of G, in which case each node needs to remember the port number leading to its parent. Hence the cost of a spanning tree T is the total number of bits the nodes need to store in order to remember T. This paper addresses the question of asymptotically bounding the cost of the optimal tree, as a function of the graph size. A tight upper bound of O(n) is established on this cost, thus improving on the best previously known bound of O(n log log n) [6] and proving the conjecture raised therein. This is achieved by presenting a polynomial time algorithm for constructing a spanning tree T of cost O(n) for a given general graph G with an arbitrary port labeling.

机译：考虑一个n节点无向图G（V，E），其中每个节点的出局边都有一个预先分配的端口号。分配给度数为deg（u）的节点u的端口号为{0,1，...，deg（u）_1}。在某些情况下，必须维护G的定向生成树，在这种情况下，每个节点都需要记住通向其父节点的端口号。因此，生成树的代价T是节点为了记住T所需存储的总位数。本文讨论了渐近地界定最优树代价的问题，该问题取决于图的大小。 O（n）的严格上限以此成本为基础，从而改善了O（n log log n）的最佳已知界限[6]，并证明了其中的猜想。这是通过提出一种多项式时间算法来实现的，该算法用于为具有任意端口标记的给定一般图G构造成本为O（n）的生成树T。

著录项

来源
《Graph-theoretic concepts in computer science》|2009年|p.66-76|共11页
会议地点 Montpellier(FR);Montpellier(FR)
作者
Shiri Chechik; David Peleg;
展开▼
作者单位

Department of Computer Science and Applied Mathematics,The Weizmann Institute of Science, Rehovot, 76100 Israel;

Department of Computer Science and Applied Mathematics,The Weizmann Institute of Science, Rehovot, 76100 Israel;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类计算机网络;
关键词

相似文献

外文文献
中文文献
专利

1. Five-port Ethernet Switch Targets Cost-sensitive Low-port Apps [J] . LOUIS E. FRENZEL Electronic Design . 2008,第15期

机译：五端口以太网交换机面向成本敏感的低端口应用
2. COSMO-BEP-Tree v1.0: a coupled urban climate model with explicit representation of street trees [J] . Mussetti Gianluca, Brunner Dominik, Henne Stephan, Geoscientific Model Development Discussions . 2020,第3期

机译：cosmo-bep树v1.0：耦合城市气候模型，具有明确代表街道树木
3. COSMO-BEP-Tree v1.0: a coupled urban climate model with explicit representation of street trees [J] . Gianluca Mussetti, Dominik Brunner, Stephan Henne, Geoscientific Model Development . 2020,第3期

机译：cosmo-bep树v1.0：耦合城市气候模型，具有明确代表街道树木
4. Low-Port Tree Representation [C] . Shiri Chechik, David Peleg International Workshop on Graph-Theoretic Concepts in Computer Science . 2010

机译：低端口树表示
5. Three-dimensional binary space partitioning tree and constructive solid geometry tree construction from algebraic boundary representations. [D] . Buchele, Suzanne Fox. 1999

机译：利用代数边界表示法构建三维二元空间划分树和构造实体几何树。
6. A Representation and Classification Scheme for Tree-Like Structures in Medical Images: Analyzing the Branching Pattern of Ductal Trees in X-ray Galactograms [O] . Vasileios Megalooikonomou, Michael Barnathan, Despina Kontos, -1

机译：一种医学图像中类似树状结构的表示和分类方案：在X射线半乳糖图中分析导管树的分支模式
7. Figure 6: (A) Tree resulted the standard MP analysis of the 98-loci supermatrix of the Great Apes (Hominidae, Primates, Mammalia) constructed using the modified summary of Lehtonen et al. (2011) (see “Materials and Methods” for the details) and a posteriori rooted relatively Papio (length = 12,092, CI = 0.7877, RI = 0.5597); 34,022 characters are constant, and the number of the parsimony-informative characters is equal to 4,311. MP BS values are provided below branches. The only characters with non-ambiguous value of the outgroup (Papio) have been saved within concatenated alignment; (B) the average consensus tree of the score 0.00084 resulted the analysis of the Hennigian forest of the 5,507 trees derived from the binary representation of the 98-loci supermatrix of the Great Apes (Hominidae, Primates, Mammalia) (see “Materials and Methods” for the details); Papio is assumed to be the best all-plesiomorphic group. “Additional…” FORESTER’s output tree file (see “Materials and Methods” for the details) selected for future analyses; (C) the average consensus tree of the score 0.00090 resulted the analysis of the Hennigian forest of the 5,339 trees derived from the modified binary representation of the 98-loci supermatrix of the Great Apes (Hominidae, Primates, Mammalia) (see 6.I. and “Materials and Methods” for the details), but with all 168 trees, which contain the clade (Homo plus Pan) have been removed from the input forest. “Additional…” FORESTER’s output tree file (see “Materials and Methods”) selected for future analyses. [O] . -1

机译：图6：（A）树导致的标准MP分析的98-基因座的类人猿（人科，灵长类动物，哺乳动物），使用莱赫托宁等人的修改的摘要构成的超级矩阵。（2011）（参见细节“材料和方法”）以及相对植根狒狒后验概率（长度= 12092，CI = 0.7877，RI = 0.5597）; 34022个字符是恒定的，并且简约信息的字符数等于4311。下面提供分支MP BS值。与外类群（狒狒）的非模糊值的唯一的字符已被保存的级联对准内; （B）的得分0.00084的平均一致树导致从巨猿（原始人类，灵长类动物，哺乳动物）的98座超级矩阵的二进制表示获得的5507棵的Hennigian森林的分析（见“材料和方法”为细节）;狒狒被认为是最好的全祖征群。 “其他...” FORESTER的输出树文件（请参阅详细信息“材料和方法”），用于进一步的分析; （C）的分数0.00090的平均一致树导致从98个位点的类人猿（人科，灵长类动物，哺乳动物）的超级矩阵（见6.I的改性二进制表示导出的5339种树木的Hennigian森林的分析以及“材料和方法”的详细说明），但所有168棵，其中包含的分支（智人加PAN）已经从输入林中删除。 “其他...” FORESTER的输出树文件（参见“材料和方法”），用于进一步的分析。

Low-Port Tree Representations

摘要

著录项

相似文献

相关主题

期刊订阅