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

A LINEAR algorithm TO DETERMINE MINIMAL SPANNING FORESTS IN CHAIN GRAPHS

INFORMATION PROCESSING LETTERS 1982年第1期15卷 1-4页

作者： LUCCIO, F PAGLI, L Istituto di Scienze dell'Informazione University of Pisa 56100 Pisa Italy

Given the graph G=(V,E), the concept of minimal spanning forest (msf) is an extension of the minimal spanning tree (mst) of G. However, an msf is not necessarily a subgraph of mst. Therefore, no immediate extension of the classical algorithms to determine mst applies to msf. The problem of determining an msf can be viewed as a special case of the degree constrained subgraph problem. This review discusses some properties of msf and presents a linear time algorithm to build an msf for a chain graph.

关键词： Minimal spanning forest minimal spanning tree cover chain algorithm design

来源：评论

学校读者我要写书评

暂无评论

MODELING HYPERGRAPHS BY GRAPHS WITH THE SAME MINCUT PROPERTIES

引用

INFORMATION PROCESSING LETTERS 1993年第4期45卷 171-175页

作者： IHLER, E WAGNER, D WAGNER, F TECH UNIV BERLIN FACHBEREICH MATHSTR 17 JUNI 136W-1000 BERLIN 12GERMANY SWISS FED INST TECHNOL CH-8092 ZURICHSWITZERLAND FREE UNIV BERLIN INST INFORMATFACHBEREICH MATHW-1000 BERLIN 33GERMANY

An elegant and general way to apply graph partitioning algorithms to hypergraphs would be to model hypergraphs by graphs and apply the graph algorithms to these models. Of course such models have to simulate the given hypergraphs with respect to their cut properties. An edge-weighted graph (V, E) is a cut-model for an edge-weighted hypergraph (V, H) if the weight of the edges cut by any bipartition of V in the graph is the same as the weight of the hyperedges cut by the same bipartition in the hypergraph. We show that there is no cut-model in general. Next we examine whether the addition of dummy vertices helps: An edge-weighted graph (V or D, E) is a mincut-model for an edge-weighted hypergraph (V, H) if the weight of the hyperedges cut by a bipartition of the hypergraphs vertices is the same as the weight of a minimum cut separating the two parts in the graph. We construct such models using positive and negative weights. On the other hand, we show that there is no mincut-model in general if only positive weights are allowed.

关键词： COMBINATORIAL PROBLEMS algorithm design VLSI LAYOUT

来源：评论

学校读者我要写书评

暂无评论

How Many Parameters Can Be Maximally Estimated From a Set of Measurements?

引用

IEEE GEOSCIENCE AND REMOTE SENSING LETTERS 2015年第5期12卷 1081-1085页

作者： Konings, Alexandra G. McColl, Kaighin A. Piles, Maria Entekhabi, Dara MIT Dept Civil & Environm Engn Cambridge MA 02139 USA Univ Politecn Cataluna Dept Teoria Senyal & Comunicac Remote Sensing Lab ES-08034 Barcelona Spain SMOS Barcelona Expert Ctr Barcelona 08003 Spain

Remote sensing algorithms often invert multiple measurements simultaneously to retrieve a group of geophysical parameters. In order to create a robust retrieval algorithm, it is necessary to ensure that there are more unique measurements than parameters to be retrieved. If this is not the case, the inversion might have multiple solutions and be sensitive to noise. In this letter, we introduce a methodology to calculate the number of (possibly fractional) "degrees of information" in a set of measurements, representing the number of parameters that can be retrieved robustly from that set. Since different measurements may not be mutually independent, the amount of duplicate information is calculated using the information-theoretic concept of total correlation (a generalization of mutual information). The total correlation is sensitive to the full distribution of each measurement and therefore accounts for duplicate information even if multiple measurements are related only partially and nonlinearly. The method is illustrated using several examples, and applications to a variety of sensor types are discussed.

关键词： algorithm design mutual information retrieval algorithms total correlation

来源：评论

学校读者我要写书评

暂无评论

Autonomous Onboard Point Source Detection by Small Exploration Spacecraft

引用

PUBLICATIONS OF THE ASTRONOMICAL SOCIETY OF THE PACIFIC 2015年第958期127卷 1279-1291页

作者： Huffman, W. Thompson, D. R. Bue, B. Castillo-Rogez, J. Boland, J. CALTECH Jet Prop Lab Pasadena CA 91109 USA

Small spacecraft platforms are a promising low-cost approach to accelerate exploration of small bodies, addressing the space community's interest in origin science, planetary resources, and planetary defense. However, they can be challenging platforms for detecting and imaging low brightness targets. Difficulties include constrained bandwidth, which limits the volume of data that can be downlinked;attitude instability, which limits exposure time;small instrument apertures, which reduce sensitivity;and cosmic ray contamination, which creates illusory sources. Mission designers can address all these problems simultaneously by shifting image analysis across the communications gap. Spacecraft can use onboard data analysis to detect sources directly, or downlink parsimonious summary products for detection on the ground. One promising approach is to acquire stacks of short consecutive exposures, and then coregister and coadd them onboard. This work analyzes a coaddition algorithm that is designed to be robust against small spacecraft challenges. We evaluate factors affecting performance, such as attitude control and camera noise systematics, in regimes typical of small spacecraft missions. We motivate the algorithm design by considering its application to NEAScout, a mission representing a new generation of small (sub-50kg) exploration spacecraft having very small instrument apertures and data rates below 1kbytes(-1). Here, onboard analysis allows detection and rendezvous with far smaller and fainter objects, dramatically reducing the cost and complexity of primitive bodies exploration.

关键词： Data transfer rates Exploration attitude control Syncope small spacecraft Spacecraft algorithm design exposure time apertures rendezvous chimneys image analysis

来源：评论

学校读者我要写书评

暂无评论

A COMPUTATIONALLY EFFICIENT APPROXIMATION TO THE NEAREST NEIGHBOR INTERCHANGE METRIC

引用

JOURNAL OF CLASSIFICATION 1984年第1期1卷 93-124页

作者： BROWN, EK DAY, WHE MEM UNIV NEWFOUNDLAND DEPT COMP SCIST JOHNS A1C 5S7NEWFOUNDLANDCANADA

The nearest neighbor interchange (nni) metric is a distance measure providing a quantitative measure of dissimilarity between two unrooted binary trees with labeled leaves. The metric has a transparent definition in terms of a simple transformation of binary trees, but its use in nontrivial problems is usually prevented by the absence of a computationally efficient algorithm. Since recent attempts to discover such an algorithm continue to be unsuccessful, we address the complementary problem of designing an approximation to the nni metric. Such an approximation should be well-defined, efficient to compute, comprehensible to users, relevant to applications, and a close fit to the nni metric; the challenge, of course, is to compromise these objectives in such a way that the final design is acceptable to users with practical and theoretical orientations. We describe an approximation algorithm that appears to satisfy adequately these objectives. The algorithm requires O(n) space to compute dissimilarity between binary trees withn labeled leaves; it requires O(n logn) time for rooted trees and O(n ² logn) time for unrooted trees. To help the user interpret the dissimilarity measures based on this algorithm, we describe empirical distributions of dissimilarities between pairs of randomly selected trees for both rooted and unrooted cases.

关键词： algorithm complexity algorithm design Binary tree Crossover metric Dissimilarity measure Distance measure Hierarchical classification nni metric

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL-algorithmS FOR COMPARING TREES WITH LABELED LEAVES

引用

JOURNAL OF CLASSIFICATION 1985年第1期2卷 7-28页

作者： DAY, WHE MEM UNIV NEWFOUNDLAND DEPT COMP SCI St John A1C 5S7 NEWFOUNDLAND CANADA

Let Rn denote the set of rooted trees with n leaves in which the leaves are labeled by the integers in { 1, . . . , n};and among interior vertices only the root may have degree 2. Associated with each interior vertex v in such a tree is the subset, or cluster, of leaf labels in the subtree rooted at v. Cluster {1, . . . , n} is called trivial. Clusters are used in quantitative measures of similarity, dissimilarity and consensus among trees. For any k trees in Rn, the strict consensus tree C(T1, . . . , Tk) is that tree in Rn containing exactly those clusters common to every one of the k trees. Similarity between trees T1 and T2 in Rn is measured by the number S(T1, T2) of nontrivial clusters in both T1 and T2;dissimilarity, by the number D(T1, T2) of clusters in T1 or T2 but not in both. algorithms are known to compute C(T1, . . . , Tk) in O(kn2) time, and S(T1, T2) and D(T1, T2) in O(N2) time. A special representation of the clusters of any tree T in Rn, is proposed that permits testing in constant time whether a given cluster exists in T. algorithms are described that exploit this representation to compute C(T1, . . . , Tk) in O(kn) time, and S(T1, T2) and D(T1, T2) in O(n) time. These algorithms are optimal in a technical sense. They enable well-known indices of consensus between 2 [phylogenetic] trees to be computed in O(n) time. All these results apply as well to comparable problems involving unrooted trees with labeled leaves.

关键词： algorithm complexity algorithm design Comparing hierarchical classifications Comparing phylogenetic trees Consensus index Strict consensus tree

来源：评论

学校读者我要写书评

暂无评论

Secure encryption algorithms for wireless sensor networks based on node trust value

引用

INTERNATIONAL JOURNAL OF INTERNET PROTOCOL TECHNOLOGY 2020年第3期13卷 117-123页

作者： Li, Li Beijing Polytech Commun Dept 9 Liangshuiheyijie St Beijing Peoples R China

The data transmission in the wireless sensor network is affected by the forwarding randomness of the relay node, resulting in poor security encryption performance. In order to improve the security encryption capability of wireless sensor network, a wireless sensor network security encryption algorithm based on node trust value is proposed. The linear coding design of sensor network transmission data is carried out according to the trust degree and the composite chaotic model is used for recursive analysis of vector quantisation in wireless sensor network encryption process and then the linear block code design of encryption key and decryption key is realised. The regression analysis results of node trust value are used to realise wireless sensor network security encryption. Simulation results show that the security of wireless sensor network encryption used proposed method is better, the distortion of encrypted transmission is lower and the performance is better.

关键词： node trust value wireless sensor network security encryption algorithm design

来源：评论

学校读者我要写书评

暂无评论

Consumer Acquisition for Recommender Systems: A Theoretical Framework and Empirical Evaluations

引用

INFORMATION SYSTEMS RESEARCH 2024年第1期35卷 339页

作者： Bi, Xuan Yang, Mochen Adomavicius, Gediminas Univ Minnesota Carlson Sch Management Informat & Decis Sci Minneapolis MN 55455 USA

We consider a marketplace where a recommender system provider (the firm) offers incentives to acquire prospective consumers by leveraging information that a market intermediary collects about these consumers. We investigate a model of consumer acquisition that incorporates several factors affecting acquisition decisions, including the value that a consumer contributes to the recommender system, the cost of participation to the consumer (e.g., privacy loss), and the value that a consumer can derive from the system due to network externality created by existing consumers. Our model is dynamic in nature, where the firm iteratively decides the next acquisition target based on previously realized acquisition outcomes. We propose flexible data-driven procedures to estimate some of the key parameters in the model using consumers' data collected by the market intermediary, for example their historical consumption data or the consumption data of other similar consumers. We also design an algorithm to compute the dynamic acquisition sequence and the corresponding incentives to offer. We conduct simulation-based empirical evaluations on two canonical recommendation tasks: movie recommendation based on numerical ratings and product offer recommendation based on browsing (clicking) behaviors and benchmark our acquisition model with random acquisition sequences with respect to (i) firm utility, (ii) recommender system performance, and (iii) consumer surplus. We find nuanced relationships between the firm's choice of incentive strategies and acquisition outcomes. Specifically, neither a constant strategy (setting the same incentive for all consumers) nor a fully greedy strategy (extracting all cumulative network externality) is optimal on all acquisition outcomes. Under a moderately greedy strategy, where the firm only partially extracts the cumulative network externality from consumers, the dynamic acquisition sequence can outperform random sequences on three acquisition outcomes

关键词： consumer acquisition recommender systems network externality personalization algorithm design

来源：评论

学校读者我要写书评

暂无评论

Line pool generation

引用

PUBLIC TRANSPORT 2017年第1-2期9卷 7-32页

作者： Gattermann, Philine Harbering, Jonas Schobel, Anita Univ Gottingen Lotzestr 16-18 D-37083 Gottingen Germany

Finding the lines and their frequencies in public transportation is the well-studied line planning problem. In this problem, it is common to assume that a line pool consisting of a set of potential lines is given. The goal is to choose a set of lines from the line pool that is convenient for the passengers and has low costs. The chosen lines then form the line plan to be established by the public transportation company. The line pool hence has a significant impact on the quality of the line plan. The more lines are in the line pool, the more flexible can we choose the resulting line plan and hence increase its quality. It hence would be preferable to allow all possible lines to choose from. However, the resulting instances of the line planning problem become intractable if all lines would be allowed. In this work, we study the effect of line pools for line planning models and propose an algorithm to generate 'good' line pools. To this end, we formally introduce the line pool generation problem and investigate its properties. The line pool generation problem asks for choosing a subset of paths (the line pool) of limited cardinality such that in a next step a good line concept can be constructed based on this subset. We show that this problem is NP-hard. We then discuss how reasonable line pools may be constructed. Our approach allows to construct line pools with different properties and even to engineer the properties of the pools to fit to the objective function of the line planning model to be used later on. Our numerical experiments on close-to real-world data show that the quality of a line plan significantly depends on the underlying line pool, and that it can be influenced by the parameters of our approach.

关键词： Line pool Line planning Public transport algorithm design

来源：评论

学校读者我要写书评

暂无评论

Intelligent recognition algorithm of connection relation of substation secondary wiring drawing based on D-LLE algorithm

引用

DISCOVER APPLIED SCIENCES 2024年第1期7卷 1-12页

作者： Liu, Hongzhi Yang, Bojie Kang, Fang Li, Qian Zhang, Hongyang State Grid Shandong Elect Power Co Econ & Technol Res Inst Jinan 250021 Shandong Peoples R China

The accurate recognition of the connection relationship of the substation secondary wiring drawings is a key link in the operation and maintenance of the power system, but the traditional manual recognition method has the problems of time-consuming, labor-intensive and error-prone. Therefore, this paper proposes an intelligent recognition algorithm for substation secondary wiring drawings based on D-LLE algorithm. The composition of the substation secondary layout diagram is analyzed, and the connection relationship feature image is preprocessed, including smoothing and contrast enhancement, to improve the image quality. D-LLE algorithm (Denoised Locally Linear Embedding) is used to effectively extract the connection features in the drawings, which improves the feature expression ability and recognition accuracy. The improved Canny operator is used to extract the feature edge of the connection relationship, and the feature recognition algorithm is used to realize the intelligent recognition of the connection relationship. The experimental results show that the completeness of connection information extraction of substation secondary wiring drawings obtained by the proposed algorithm is between 98.56% and 99.98%, and the mean absolute error of intelligent recognition drawings connection relationship is always lower than 0.01. It shows that the proposed algorithm can accurately and quickly identify the connection relationship in the substation secondary wiring drawings, significantly improve the recognition efficiency, and has strong robustness and versatility, which can provide strong support for the intelligent operation and maintenance of the power system.

关键词： D-LLE algorithm Substation Secondary wiring drawings Connection relation Intelligent recognition algorithm design

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：