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

L(2,1)-labeling of strong products of cycles

INFORMATION PROCESSING LETTERS 2005年第4期94卷 183-190页

作者： Korze, D Vesel, A Univ Maribor PEF Dept Math & Comp Sci SI-2000 Maribor Slovenia Univ Maribor FERI Dept Comp Sci SI-2000 Maribor Slovenia

In a wireless network, different devices are fitted with radio transmittersand receivers. The task of channel assignment problem is to assign radio frequencies to transmittersat different locations, without interference. The problem is closely related to graph labelingwhere the vertices of a graph represent the transmitters and the adjacencies show possibleinterference. However, the interference phenomena may be so powerful that even the differentchannels used at close stations may interfere, if the channels are too near. Thus, in many cases,channels assigned to stations must be separated according to the distance between two transmitters.L(2, 1)-labeling, a variation of the channel assignment problem, distinguishes between closetransmitters which must receive different channels and very close transmitters which must receivechannels that are at least two channels apart. This topic has been the object of extensive research,see, for example, and the references therein. Strong product graphs provide a setting in which toanalyse many existing networks as well as to construct new and interesting networks. A particularapplication may be seen in the area of a memoryless channels (Shannon capacity). A strong producthas high fault tolerance with respect to node failure and edge failure, also when compared to othertypes of graph products.

关键词： channel assignment L(2,1)-labeling strong product dynamic algorithm graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A SEMIdynamic CONSTRUCTION OF HIGHER-ORDER VORONOI DIAGRAMS AND ITS RANDOMIZED ANALYSIS

引用

algorithmICA 1993年第4期9卷 329-356页

作者： BOISSONNAT, JD DEVILLERS, O TEILLAUD, M 1. Institut National de Recherche en Informatique et Automatique B.P. 93 06902 Sophia-Antipolis cedex France

The k-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite set of n points in any dimension. In this paper we prove that a randomized construction of the k-Delaunay tree, and thus of all the order less-than-or-equal-to k Voronoi diagrams, can be done in O(n log n + k3n) expected time and O(k2n) expected storage in the plane, which is asymptotically optimal for fixed k. Our algorithm extends to d-dimensional space with expected time complexity O(k[(d+1/2]+1n[(d+1)/2]) and space complexity O(k[(d+1)/2]n[d+1)2]). The algorithm is simple and experimental results are given.

关键词： COMPUTATIONAL GEOMETRY dynamic algorithm RANDOMIZED COMPLEXITY ANALYSIS ORDER K-VORONOI DIAGRAM

来源：评论

学校读者我要写书评

暂无评论

An energy and delay aware routing protocol for wireless sensor network assisted IoT to maximise network lifetime

引用

INTERNATIONAL JOURNAL OF AD HOC AND UBIQUITOUS COMPUTING 2022年第1-3期40卷 148-158页

作者： Vinmathi, M. S. Josephine, M. S. Jeyabalaraja, V Dr MGR Educ & Res Inst Chennai Tamil Nadu India Dr MGR Educ & Res Inst Dept Comp Applicat Chennai Tamil Nadu India Vellammal Engn Coll CSE Dept Chennai Tamil Nadu India

IoT is a technology where different devices are connected and integrated to provide solutions. The ultimate source of gathering and processing a large data are obtained through sensor devices. In this research work, a protocol for routing is proposed which is aware of the delay and energy is a WSN (EDAR-WIoT) for lifetime maximisation in network. The proposed EDAR-WIoT protocol enhances and compromises the energy and delay without affecting network lifetime. The chaotic spiral dynamic (CSD) algorithm reduces the chaotic in nature of energy utilisation. Then, a queue based swarm optimisation (QSO) algorithm is utilised to next optimal node for inter cluster routing. The EDAR-WIoT protocol preserves the energy efficiency and network lifetime in wireless sensor networks. The proposed protocol is experimented using NS-2 simulator. It is observed from the experiments that the proposed protocol outperformed the other existing protocols in terms of network performance parameters.

关键词： routing protocol internet of things dynamic algorithm optimisation algorithm network security

来源：评论

学校读者我要写书评

暂无评论

Unrestricted dynamic Gröbner Basis algorithms

Unrestricted dynamic Gröbner Basis algorithms

引用

作者： Langeloh, Gabriel Mattos

Gröbner bases are a necessary tool to solve many problems involving polynomial ideals, including applications such as nonlinear polynomial system solving, integer programming and cryptography. Traditional Gröbner Basis algorithms are static, in the sense that they receive a monomial order as input and it is fixed during the entire execution of the algorithm. dynamic algorithms, in contrast, allow this monomial ordering to change to generate smaller output bases and, hopefully, fewer polynomial reductions. All but one of the previously proposed dynamic algorithms are restricted, meaning that once they choose a leading monomial for a certain polynomial, that choice cannot be unmade. In this work, we focus on exploring unrestricted dynamic algorithms, studying the relation of monomial orderings to Newton polyhedra and proposing four new unrestricted algorithms that avoid evaluating too many monomial orderings by using a neighborhood construction for monomial orders. We also propose a new heuristic, called the Mixed heuristic, for monomial order evaluation in dynamic algorithms. Our experiments show that although the restricted algorithms perform better with respect to running time, our unrestricted algorithms find orders that lead to smaller Gröbner Bases for many instances and significantly lower degree polynomials in average. Additionally, we provide a comparison between the previously defined Hilbert and Betti heuristics and our Mixed heuristic, showing it performs better than the Betti heuristic in most aspects and is competitive with the Hilbert heuristic overall. ...

关键词： Algoritmos Gröbner bases Algoritmo dinâmico dynamic algorithm Monomial ordering Dissertação

来源：评论

学校读者我要写书评

暂无评论

Metadata mapping and reuse in caBIG™

引用

BMC BIOINFORMATICS 2009年第s2期10卷 1-11页

作者： Kunz, Isaac Lin, Ming-Chin Frey, Lewis Univ Utah Sch Med Dept Biomed Informat Salt Lake City UT 84112 USA Univ Utah Huntsman Canc Inst Salt Lake City UT USA

Background: This paper proposes that interoperability across biomedical databases can be improved by utilizing a repository of Common Data Elements (CDEs), UML model class-attributes and simple lexical algorithms to facilitate the building domain models. This is examined in the context of an existing system, the National Cancer Institute (NCI)'s cancer Biomedical Informatics Grid (caBIG (TM)). The goal is to demonstrate the deployment of open source tools that can be used to effectively map models and enable the reuse of existing information objects and CDEs in the development of new models for translational research applications. This effort is intended to help developers reuse appropriate CDEs to enable interoperability of their systems when developing within the caBIG (TM) framework or other frameworks that use metadata repositories. Results: The Dice (di-grams) and dynamic algorithms are compared and both algorithms have similar performance matching UML model class-attributes to CDE class object-property pairs. With algorithms used, the baselines for automatically finding the matches are reasonable for the data models examined. It suggests that automatic mapping of UML models and CDEs is feasible within the caBIG (TM) framework and potentially any framework that uses a metadata repository. Conclusion: This work opens up the possibility of using mapping algorithms to reduce cost and time required to map local data models to a reference data model such as those used within caBIG (TM). This effort contributes to facilitating the development of interoperable systems within caBIG (TM) as well as other metadata frameworks. Such efforts are critical to address the need to develop systems to handle enormous amounts of diverse data that can be leveraged from new biomedical methodologies.

关键词： Unify Modelling Language Application Program Interface dynamic algorithm Unify Modelling Language Model Common Data Element

来源：评论

学校读者我要写书评

暂无评论

Shortest paths in digraphs of small treewidth. Part I: Sequential algorithms

引用

algorithmICA 2000年第3-4期27卷 212-226页

作者： Chaudhuri, S Zaroliagis, CD Max Planck Inst Informat D-66123 Saarbrucken Germany

We consider the problem of preprocessing an n-vertex digraph with real edge weights so that subsequent queries for the shortest path or distance between any two vertices can be efficiently answered. We give algorithms that depend on the treewidth of the input graph. When the treewidth is a constant, our algorithms can answer distance queries in O(alpha(n)) time after O(n) preprocessing. This improves upon previously known results for the same problem. We also give a dyna the data structure in time O(n(beta)), for any constant 0 < beta < 1. Furthermore, an algorithm of independent interest is given: computing a shortest path tree, or finding a negative cycle in linear time.

关键词： shortest path graph theory treewidth dynamic algorithm

来源：评论

学校读者我要写书评

暂无评论

Parametric identification of nonlinear model for managed pressure drilling

引用

IFAC-PapersOnLine 2016年第12期49卷 1916-1921页

作者： Alexandrov, Albert G. Alexandrov, Vadim A. Shatov, Dmitriy V. V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences Russia ADAPLAB LLC Russia

Managed pressure drilling process is descried by nonlinear model. Nonlinear controller is proposed for this process. Model parameter is identified which is required to synthesize controller. dynamic algorithm of frequ... 详细信息

关键词： Parameter estimation Adaptive control systems Controllers Frequency domain analysis Identification (control systems) Nonlinear systems Adaptive Control dynamic algorithm Frequency domain identification Managed Pressure Drilling Model parameters Non linear control Non linear controllers Parametric identification

来源：评论

学校读者我要写书评

暂无评论

Maintaining the classes of 4-edge-connectivity in a graph on-line

引用

algorithmICA 1998年第3期20卷 242-276页

作者： Dinitz, Y Westbrook, J Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel AT&T Bell Labs Res Florham Pk NJ 07932 USA Yale Univ Dept Comp Sci New Haven CT 06520 USA

Two vertices of an undirected graph are called k-edge-connected if there exist k edge-disjoint paths between them (equivalently, they cannot be disconnected by the removal of less than k edges from the graph). Equivalence classes of this relation are called classes of k-edge-connectivity or k-edge-connected components. This paper describes graph structures relevant to classes of 4-edge-connectivity and traces their transformations as new edges are inserted into the graph. Data structures and an algorithm to maintain these classes incrementally are given. Starting with the empty graph, any sequence of q Same-4-Class? queries and it Insert-Vertex and lit Insert-Edge updates can be performed in O(q + m + ii log n total time. Each individual query requires O(1) time in the worst-case. In addition, an algorithm for maintaining the classes of k-edge-connectivity (k arbitrary) in a (k-1)-edge-connected graph is presented. Its complexity is O(q + m + n). with O(M + k(2)n log(n/k)) preprocessing, where M is the number of edges initially in the graph and n is the number of its vertices.

关键词： dynamic algorithm dynamic data structure graph algorithm edge-connectivity connectivity class component analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

On update algorithms for quickest paths

引用

COMPUTER COMMUNICATIONS 2000年第11期23卷 1064-1068页

作者： Bang, YC Radhakrishnan, S Rao, NSV Batsell, SG Univ Oklahoma Sch Comp Sci Norman OK 73019 USA Oak Ridge Natl Lab Oak Ridge TN 37831 USA

The quickest path problem deals with the transmission of a message of size cr from a source to a destination with the minimum end-to-end delay over a network with bandwidth and delay constraints on the links. The path-table that maps all intervals for sigma to the corresponding quickest paths can be computed in O(m(2) + mn log n) time, where n and rn are the number of nodes and links of the network, respectively. We propose linear-time algorithms that update the path-table after a increase or decrease bandwidth of a link or a path, respectively. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： quickest path dynamic algorithm network bandwidth delay

来源：评论

学校读者我要写书评

暂无评论

On-line planarity testing

引用

SIAM JOURNAL ON COMPUTING 1996年第5期25卷 956-997页

作者： DiBattista, G Tamassia, R BROWN UNIV DEPT COMP SCI PROVIDENCE RI 02912 USA

The on-line planarity-testing problem consists of performing the following operations on a planar graph G: (i) testing if a new edge can be added to G so that the resulting graph is itself planar;(ii) adding vertices and edges such that planarity is preserved. An efficient technique for online planarity testing of a graph is presented that uses O(n) space and supports tests and insertions of vertices and edges in O(log n) time, where n is the current number of vertices of G. The bounds for tests and vertex insertions are worst-case and the bound for edge insertions is amortized. We also present other applications of this technique to dynamic algorithms for planar graphs.

关键词： planar graph on-line algorithm dynamic algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：