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

An efficient distributed algorithm for finding all hinge vertices in networks

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2005年第7期82卷 821-827页

作者： Ho, TY Chang, JM Natl Taipei Coll Business Dept Informat Management Taipei 100 Taiwan Natl Taipei Coll Business Dept Publ Finance & Tax Adm Taipei 100 Taiwan

Let G = (V, E) be a graph with vertex set V of size n and edge set E of size m. A vertex v G V is called a hinge vertex if there exist two vertices in V \ {v} such that their distance becomes longer when v is removed. In this paper, we present a distributed algorithm that finds all hinge vertices on an arbitrary graph. The proposed algorithm works for named static asynchronous networks and achieves O(n(2)) time complexity and O(m) message complexity. In particular, the total messages exchanged during the algorithm are at most 2m(log n + n log n + 1) bits.

关键词： distributed systems distributed algorithms hinge vertices static asynchronous networks graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Algorithmic aspects of hardware/software partitioning

引用

ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS 2005年第1期10卷 136-156页

作者： Arató, P Mann, ZA Orbán, A Budapest Univ Technol & Econ Dept Control Engn & Informat Technol H-1117 Budapest Hungary

One of the most crucial steps in the design of embedded systems is hardware/software partitioning, is, deciding which components of the system should be implemented in hardware and which ones in software. Most formulations of the hardware/software partitioning problem are MP-hard, so the majority-of research efforts on hardware/software partitioning has focused on developing efficient heuristics. This article considers the combinatorial structure behind hardware/software partitioning. Two similar versions of the partitioning problem are defined, one of which turns out to be NP-hard, whereas the other one can be solved in polynomial time. This helps in understanding the real cause of complexity in hardware/software partitioning. Moreover, the polynomial-time algorithm serves as the basis for a highly efficient novel heuristic for the NP-hard version of the problem. Unlike general-purpose heuristics such as genetic algorithms or simulated annealing, this heuristic makes use of problem-specific knowledge, and can thus find high-quality solutions rapidly. Moreover, it has the unique characteristic that it also calculates lower bounds on the optimum solution. It is demonstrated on several benchmarks and also large random examples that the new algorithm clearly outperforms other heuristics that are generally applied to hardware/software partitioning.

关键词： algorithms design hardware/software partitioning hardware/software codesign graph bipartitioning graph algorithms optimization

来源：评论

学校读者我要写书评

暂无评论

Bioinformatics analysis of alternative splicing

引用

BRIEFINGS IN BIOINFORMATICS 2005年第1期6卷 23-33页

作者： Lee, C Wang, Q Univ Calif Los Angeles Dept Chem & Biochem Inst Mol Biol Ctr Genom & Proteom Los Angeles CA 90095 USA

Over the past few years, the analysis of alternative splicing using bioinformatics has emerged as an important new field, and has significantly changed our view of genome function. One exciting front has been the analysis of microarray data to measure alternative splicing genome-wide. Pioneering studies of both human and mouse data have produced algorithms for discerning evidence of alternative splicing and clustering genes and samples by their alternative splicing patterns. Moreover, these data indicate the presence of alternative splice forms in up to 80 per cent of human genes. Comparative genomics studies in both mammals and insects have demonstrated that alternative splicing can in some cases be predicted directly from comparisons of genome sequences, based on heightened sequence conservation and exon length. Such studies have also provided new insights into the connection between alternative splicing and a variety of evolutionary processes such as Alu-based exonisation, exon creation and loss. A number of groups have used a combination of bioinformatics, comparative genomics and experimental validation to identify new motifs for splice regulatory factors, analyse the balance of factors that regulate alternative splicing, and propose a new mechanism for regulation based on the interaction of alternative splicing and nonsense-mediated decay. Bioinformatics studies of the functional impact of alternative splicing have revealed a wide range of regulatory mechanisms, from NAGNAG sites that add a single amino acid;to short peptide segments that can play surprisingly complex roles in switching protein conformation and function (as in the Piccolo C2A domain);to events that entirely remove a specific protein interaction domain or membrane anchoring domain. Common to many bioinformatics studies is a new emphasis on graph representations of alternative splicing structures, which have many advantages for analysis.

关键词： alternative splicing microarrays comparative genomics graph algorithms regulation

来源：评论

学校读者我要写书评

暂无评论

Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs

引用

THEORETICAL COMPUTER SCIENCE 2005年第1-3期341卷 411-440页

作者： Hung, RW Chang, MS Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 621 Taiwan

A Hamiltonian path of a graph G is a simple path that contains each vertex of G exactly once. A Hamiltonian cycle of a graph is a simple cycle with the same property. The Hamiltonian path (resp. cycle) problem involves testing whether a Hamiltonian path (resp. cycle) exists in a graph. The 1HP (resp. 2HP) problem is to determine whether a graph has a Hamiltonian path starting from a specified vertex (resp. starting from a specified vertex and ending at the other specified vertex). The Hamiltonian problems include the Hamiltonian path, Hamiltonian cycle, 1HP, and 2HP problems. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. In this paper, we present a unified approach to solving the Hamiltonian problems on distance-hereditary graphs in linear time. (c) 2005 Elsevier B.V. All rights reserved.

关键词： graph algorithms linear-time algorithms Hamiltonian problems distance-hereditary graphs

来源：评论

学校读者我要写书评

暂无评论

Computing Almost Shortest Paths

引用

ACM TRANSACTIONS ON algorithms 2005年第2期1卷 283-323页

作者： Elkin, Michael Yale Univ Dept Comp Sci POB 2158 New Haven CT 06520 USA Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

We study the s-sources almost shortest paths (abbreviated s-ASP) problem. Given an unweighted graph G = (V, E), and a subset S subset of V of s nodes, the goal is to compute almost shortest paths between all the pairs of nodes S x V . We devise an algorithm with running time O (vertical bar E vertical bar n(rho) +s.n(1+zeta)) for this problem that computes the paths P-u.w for all pairs (u, w) is an element of S x V such that the length of P-u,P-w is at most (1 + epsilon)d(G) (u, w) + beta(zeta, rho, epsilon), and beta(zeta, rho, epsilon) is constant when zeta, rho, and epsilon are arbitrarily small constants. We also devise a distributed protocol for the s -ASP problem that computes the paths P-u,P-w as above, and has time and communication complexities of O(s . Diam(G) n(1+zeta/2)) (respectively, O(s . Diam(G) log(3) n + n(1+zeta/2) log n)) and O (vertical bar E vertical bar n(rho) + s . n(1+zeta)) (respectively, O(vertical bar E vertical bar n(rho) + s . n(1+zeta) + n(1+rho+zeta(rho-zeta/2/2))) in the synchronous (respectively asynchronous) setting. Our sequential algorithm, as well as the distributed protocol, is based on a novel algorithm for constructing (1 +epsilon, beta(zeta, rho, epsilon))-spanners of size O(n(1+zeta)), developed in this article. This algorithm has running time of O(vertical bar E vertical bar n(rho)), which is significantly faster than the previously known algorithm given in Elkin and Peleg [2001], whose running time is O (n(2 +rho)). We also develop the first distributed protocol for constructing (1 + epsilon, beta)-spanners. The communication complexity of this protocol is near optimal.

关键词： graph algorithms almost shortest paths spanners

来源：评论

学校读者我要写书评

暂无评论

Object-oriented algorithm analysis and design with Java

引用

SCIENCE OF COMPUTER PROGRAMMING 2005年第1期54卷 25-47页

作者： Rajsbaum, S Viso, E Univ Nacl Autonoma Mexico Inst Matemat Mexico City 04510 DF Mexico Univ Nacl Autonoma Mexico Fac Ciencias Mexico City 04510 DF Mexico

This paper presents a new approach to algorithm design and analysis that benefits from the OO characteristics of Java. It consists of first defining the inheritance structure of a collection of algorithms, at different levels of abstraction. Then, correctness proofs and complexity measures are designed for the various levels of abstraction. The goal is to prove as many properties as possible at each abstract level, assuming the implementations of the methods called upon will be correct. Thus, when a more specialized algorithm is derived from a more abstract one, proofs and complexity analysis can be reused, and simply need to be completed by proving that the properties assumed for the concrete methods indeed hold. The approach is illustrated with several inheritance trees: for sorting, graph algorithms, string matching, and network flow. Each tree, at the bottom of the hierarchy, yields well-known algorithms in the respective area. Instead of using pseudo-code to describe these trees, Java is used to make the process more precise and useful, encouraging the design and analysis of algorithms, and also experimentation with new variants. The implementation presented in this paper takes advantage of Java's organization to build the inheritance trees for the classes, and Java's interfaces, collections, comparators, and iterators. (C) 2004 Elsevier B.V. All rights reserved.

关键词： algorithms inheritance polymorphism teaching Java sorting graph algorithms string matching network flow

来源：评论

学校读者我要写书评

暂无评论

Single backup table schemes for shortest-path routing

引用

THEORETICAL COMPUTER SCIENCE 2005年第3期333卷 347-353页

作者： Ito, H Iwama, K Okabe, Y Yoshihiro, T Wakayama Univ Fac Syst Engn Wakayama 6408510 Japan Kyoto Univ Sch Informat Kyoto 6068501 Japan Kyoto Univ Acad Ctr Comp & Media Studies Kyoto 6068501 Japan

We introduce a new recovery scheme that needs only one extra backup routing table for networks employing shortest-path routing. By precomputing this backup table, the network recovers from any single link failure immediately after the failure occurs. To compute the backup routing table for this scheme, we use an almost linear time algorithm to solve the {r, v}-problem, which is a variation of the best swap problem presented by Nardelli et al. We further show that the same solution can be computed in exactly linear time if the underlying graph is unweighted. (c) 2004 Elsevier B.V. All rights reserved.

关键词： routing shortest paths fault tolerance backup tables graph algorithms swap edges

来源：评论

学校读者我要写书评

暂无评论

Object-oriented algorithm analysis and design with Java

Object-oriented algorithm analysis and design with Java

引用

Conference on the Principles and Practice of Programming in Java

作者： Rajsbaum, S Viso, E Univ Nacl Autonoma Mexico Inst Matemat Mexico City 04510 DF Mexico Univ Nacl Autonoma Mexico Fac Ciencias Mexico City 04510 DF Mexico

关键词： algorithms inheritance polymorphism teaching Java sorting graph algorithms string matching network flow

来源：评论

学校读者我要写书评

暂无评论

Single backup table schemes for shortest-path routing

Single backup table schemes for shortest-path routing

引用

10th Colloquium on Structural Information and Communication Complexity

关键词： routing shortest paths fault tolerance backup tables graph algorithms swap edges

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel graph algorithms for coarse-grained multicomputers and BSP

引用

ALGORITHMICA 2002年第2期33卷 183-200页

作者： Dehne, F Ferreira, A Cáceres, E Song, SW Roncato, A Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada INRIA CNRS I3S Sophia Antipolis France Univ Fed Mato Grosso do Sul Campo Grande Brazil Univ Sao Paulo Sao Paulo Brazil Fac Sci Mat Fis & Nat Venice Italy

In this paper we present deterministic parallel algorithms for the coarse-grained multicomputer (CGM) and bulk synchronous parallel (BSP) models for solving the following well-known graph problems: (1) list ranking, (2) Euler tour construction in a tree, (3) computing the connected components and spanning forest, (4) lowest common ancestor preprocessing, (5) tree contraction and expression tree evaluation, (6) computing an ear decomposition or open ear decomposition, and (7) 2-edge connectivity and biconnectivity (testing and component computation). The algorithms require 0 (log p) communication rounds with linear sequential work per round (p = no. processors, N = total input size). Each processor creates, during the entire algorithm, messages of total size O(log(p)(N/p)). The algorithms assume that the local memory per processor (i,e,, N/p) is larger than p(epsilon), for some fixed epsilon > 0. Our results imply BSP algorithms with O(log p) supersteps, O(g log(p)(N/p)) communication time, and O(log(p)(N/p)) local computation time. It is important to observe that the number of communication rounds/supersteps obtained in this paper is independent of the problem size, and grows only logarithmically with respect to p. With growing problem size, only the sizes of the messages grow but the total number of messages remains unchanged. Due to the considerable protocol overhead associated with each message transmission, this is an important property. The result for Problem (1) is a considerable improvement over those previously reported, The algorithms for Problems (2)-(7) are the first practically relevant parallel algorithms for these standard graph problems.

关键词： coarse grained parallel computing graph algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：