检索结果-内蒙古大学图书馆

Throughput and delay analysis of an opportunistic tree algorithm

STOCHASTIC MODELS 2016年第1期32卷 20-51页

作者： Block, R. Van Houdt, B. Univ Antwerp iMinds Dept Math & Comp Sci Middelheimlaan 1 B-2020 Antwerp Belgium

tree algorithms are a well-known class of random access algorithms with a provable maximum stable throughput under the infinite population model (as opposed to ALOHA or the binary exponential backoff algorithm). In this article, we propose a tree algorithm for opportunistic spectrum usage in cognitive radio networks. A channel in such a network is shared among so-called primary and secondary users, where the secondary users are allowed to use the channel only if there is no primary user activity. The tree algorithm designed in this article can be used by the secondary users to share the channel capacity left by the primary users. We analyze the maximum stable throughput and mean packet delay of the secondary users by developing a tree structured Quasi-Birth Death Markov chain under the assumption that the primary user activity can be modeled by means of a finite state Markov chain and that packets lengths follow a discrete phase-type distribution. Numerical experiments provide insight on the effect of various system parameters and indicate that the proposed algorithm is able to make good use of the bandwidth left by the primary users.

关键词： Cognitive radio delay maximum stable throughput random access tree algorithms

来源：评论

学校读者我要写书评

暂无评论

On Optimal Solutions for the Optimal Communication Spanning tree Problem

引用

OPERATIONS RESEARCH 2009年第2期57卷 413-425页

作者： Rothlauf, Franz Johannes Gutenberg Univ Mainz Dept Informat Syst D-55099 Mainz Germany

This paper presents an experimental investigation into the properties of the optimal communication spanning tree (OCST) problem. The OCST problem seeks a spanning tree that connects all the nodes and satisfies their communication requirements at a minimum total cost. The paper compares the properties of random trees to the properties of the best solutions for the OCST problem that are found using an evolutionary algorithm. The results show, on average, that the optimal solution and the minimum spanning tree (MST) share a higher number of links than the optimal solution and a random tree. Furthermore, optimal solutions for OCST problems with randomly chosen distance weights share a higher number of links with an MST than OCST problems with Euclidean distance weights. This intuitive similarity between optimal solutions and MSTs suggests that some heuristic optimization methods for OCST problems might be improved by starting with an MST. Using an MST as a starting solution for a greedy search in the tested cases either improves median running time up to a factor of 10 while finding solutions of the same quality, or increases solution quality up to a factor of 100 while using the same number of search steps in comparison to starting the greedy search from a random tree. Starting a local search, a simulated annealing approach and a genetic algorithm from an MST increases solution quality up to a factor of three in comparison to starting from a random solution.

关键词： communications networks/graphs simulation statistical analysis topological network design tree algorithms

来源：评论

学校读者我要写书评

暂无评论

A Linear-Time Algorithm for Broadcast Domination in a tree

引用

NETWORKS 2009年第2期53卷 160-169页

作者： Dabney, John Dean, Brian C. Hedetniemi, Stephen T. Clemson Univ Sch Comp Clemson SC 29634 USA

The broadcast domination problem is a variant of the classical minimum dominating set problem in which a transmitter of power p at vertex v is capable of dominating (broadcasting to) all vertices within distance p from v. Our goal is to assign a broadcast power f(v) to every vertex v in a graph such that Sigma(v is an element of v) f(v) is minimized, and such that every vertex u with f(u) = 0 Is within distance f(v) of some vertex v with f(v) > 0. The problem is solvable in polynomial time on a general graph (Heggernes and Lokshtanov, Disc Math (2006), 3267-3280) and Blair et al. (Congr. Num. (2004), 55-77.) gave an O(n(2)) algorithm for trees. In this article, we provide an O(n) algorithm for trees. Our algorithm is notable due to the fact that it makes decisions for each vertex v based on "nonlocal" information from vertices far away from v, whereas almost all other linear-time algorithms for trees only make use of local information. (C) 2008 Wiley Periodicals, Inc. NETWORKS, Vol. 53(2), 160-169 2009

关键词： broadcasts domination tree algorithms linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A tree algorithm for isotropic finite elements on the sphere

引用

NUMERICAL FUNCTIONAL ANALYSIS AND OPTIMIZATION 2006年第1期27卷 1-24页

作者： Bauer, F Freeden, W Schreiner, M Univ Kaiserslautern Geomath Grp D-67653 Kaiserslautern Germany Univ Appl Sci Technol Lab Ind Math Buchs Switzerland

The earth's surface is an almost perfect sphere. Deviations from its spherical shape are less than 0.4% of its radius and essentially arise from its rotation. All equipotential surfaces are nearly spherical, too. In consequence, multiscale modeling of geoscientifically relevant data on the sphere plays an important role. In this paper, we deal with isotropic kernel functions showing a local support (briefly called isotropic finite elements) for reconstructing square-integrable functions on the sphere. An essential tool is the concept of multiresolution analysis by virtue of the spherical up function. Because the up function is built by an infinite convolution product, we do not know an explicit representation of it. However, the tree algorithm for the multiresolution analysis based on the up functions can be formulated by convolutions of isotropic kernels of low-order polynomial structure. For these kernels, we are able to find an explicit representation, so that the tree algorithm can be implemented efficiently.

关键词： locally supported radial basis functions multiresolution analysis spherical tree algorithms up functions

来源：评论

学校读者我要写书评

暂无评论

Detecting Population-Differentiation Copy Number Variants in Human Population tree by Sparse Group Selection

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2019年第2期16卷 538-549页

作者： Zhang, Huanan Roe, David Kuang, Rui Univ Minnesota Dept Comp Sci & Engn St Paul MN 55455 USA Natl Marrow Donor Program Bioinformat Res Minneapolis MN 55401 USA Univ Minnesota Biomed Informat & Computat Biol Minneapolis MN 55455 USA

Copy-number variants (CNVs) account for a substantial proportion of human genetic variations. Understanding the CNV diversities across populations is a computational challenge because CNV patterns are often present in several related populations and only occur in a subgroup of individuals within each of the population. This paper introduces a tree-guided sparse group selection algorithm (treeSGS) to detect population-differentiation CNV markers of subgroups across populations organized by a phylogenetic tree of human populations. The treeSGS algorithm detects CNV markers of populations associated with nodes from all levels of the tree such that the evolutionary relations among the populations are incorporated for more accurate detection of population-differentiation CNVs. We applied treeSGS algorithm to study the 1,179 samples from the 11 populations in Hapmap3 CNV data. The treeSGS algorithm accurately identifies CNV markers of each population and the collection of populations organized under the branches of the human population tree, validated by consistency among family trios and SNP characterizations of the CNVregions. Further comparison between the detected CNV markers and other population-differentiation CNVs reported in 1,000 genome data and other recent studies also shows that treeSGS can significantly improve the current annotations of population-differentiation CNV markers. treeSGS package is available at https://***/kuanglab/treeSGS.

关键词： Machine learning algorithms group LASSO DNA copy number variants population genetics tree algorithms computational biology bioinformatics

来源：评论

学校读者我要写书评

暂无评论

A DUAL ASCENT ALGORITHM FOR THE 1-tree RELAXATION OF THE SYMMETRIC TRAVELING SALESMAN PROBLEM

引用

OPERATIONS RESEARCH LETTERS 1990年第1期9卷 1-7页

作者： MALIK, K FISHER, ML UNIV PENN WHARTON SCHDEPT DECIS SCIPHILADELPHIAPA 19104

A dual ascent algorithm is described for the 1-tree relaxation of the symmetric traveling salesman problem. The ascent directions correspond to increasing (decreasing) the dual variables for the nodes of a set that is out of kilter high (low) for all 1-trees that are optimal at the current dual solution. This algorithm is shown to obtain near optimal bounds in about one-quarter of the time required by the subgradient method on a sample of well-known test cases.

关键词： traveling salesman tree algorithms dual ascent

来源：评论

学校读者我要写书评

暂无评论

INDIRECT COVERING tree PROBLEMS ON SPANNING tree NETWORKS

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1993年第1期65卷 20-32页

作者： HUTSON, VA REVELLE, C JOHNS HOPKINS UNIV PROGRAM SYST ANAL & ECON PUBL DECISIONMAKINGBALTIMOREMD 21218

This paper introduces two types of indirect covering tree problems using a spanning tree as a backbone network. The minimum cost covering subtree seeks the minimum cost collection of arcs that form a subtree and satisfy covering constraints for nodes of the network. Reduction techniques that have been used to solve the location set covering problem are extended to solve the Minimum Cost Covering Subtree (MCCS). The second problem, The Maximal Indirect Covering Subtree (MICS), chooses that subtree which maximizes the demand within a distance standard of nodes of the subtree. In addition, some variations of the maximal indirect covering subtree problem are proposed.

关键词： COVERING PROBLEMS FACILITY LOCATION tree algorithms

来源：评论

学校读者我要写书评

暂无评论

INFERRING A tree FROM LOWEST COMMON ANCESTORS WITH AN APPLICATION TO THE OPTIMIZATION OF RELATIONAL EXPRESSIONS

引用

SIAM JOURNAL ON COMPUTING 1981年第3期10卷 405-421页

作者： AHO, AV SAGIV, Y SZYMANSKI, TG ULLMAN, JD STANFORD UNIV DEPT COMP SCISTANFORDCA 94305 UNIV ILLINOIS DEPT COMP SCIURBANAIL 61801

We present an algorithm for constructing a tree to satisfy a set of lineage constraints on common ancestors. We then apply this algorithm to synthesize a relational algebra expression from a simple tableau, a problem ... 详细信息

关键词： tree algorithms lowest common ancestors relational databases relational algebra tableaux query optimization join minimization

来源：评论

学校读者我要写书评

暂无评论

Indexing Data Based on the CW-tree Algorithm Using Parallel Data Reading 9

Indexing Data Based on the CW-tree Algorithm Using Parallel ...

引用

9th Mediterranean Conference on Embedded Computing (MECO)

作者： Shevskiy, Vladislav S. St Petersburg Electrotech Univ LETI Dept Comp Sci & Engn St Petersburg Russia

ISBN: (纸本)9781728169491

The research objective is to develop indexing data algorithm to reduce database searching time by using multithreaded frameworks. In this article the indexing data algorithm in a tree form which is called CW-tree is supposed. Traversing through CW-tree occurs asynchronously with help additional start nodes. Compared to existing analogs of tree-based algorithms, the CW-tree has some advantages, the main of which is full parallelization both on the levels of branches and on the levels of leaves. To confirm benefits from using of CW-tree algorithm, comparison test between reading data with help B-tree and reading data with CW-tree was conducted. Result of test described in chapter 4 and shows that reading data time with CW-tree less than reading with B-tree.

关键词： DBMS tree algorithms multithreading database query optimization

来源：评论

学校读者我要写书评

暂无评论

Parallelization with tree skeletons

Parallelization with tree skeletons

引用

9th International Euro-Par Conference on Parallel Processing

作者： Matsuzaki, K Hu, ZJ Takeichi, M Univ Tokyo Grad Sch Informat Sci & Technol Tokyo Japan

ISBN: (纸本)354040788X

trees are useful data structures, but to design efficient parallel programs over trees is known to be more difficult than to do over lists. Although several important tree skeletons have been proposed to simplify parallel programming on trees, few studies have been reported on how to systematically use them in solving practical problems;it is neither clear how to make a good combination of skeletons to solve a given problem, nor obvious even how to find suitable operators used in a single skeleton. In this paper, we report our first attempt to resolve these problems, proposing. two important transformations, the tree diffusion transformation and the tree context preservation transformation. The tree diffusion transformation allows one to use familiar recursive definitions to develop his parallel programs, while the tree context preservation transformation shows how to derive associative operators that are required when using tree skeletons. We illustrate our approach by deriving an efficient parallel program for solving a nontrivial problem called the party planning problem, the tree version of the famous maximum-weight-sum problem.

关键词： parallel skeletons tree algorithms parallelization program transformation algorithm derivation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：