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

AN EFFICIENT ALGORITHM TO SOLVE CONNECTIVITY PROBLEM ON TRAPEZOID GRAPHS

JOURNAL OF APPLIED MATHEMATICS AND COMPUTING 2007年第1-2期24卷 141-154页

作者： Ghosh, Prabir K. Pal, Madhumangal Vidyasagar Univ Dept Appl Math Oceanol & Comp Programming Midnapore 721102 India

The connectivity problem is a fundamental problem in graph theory. The best known algorithm to solve the connectivity problem on general graphs with n vertices and m edges takes O( K(G) mn(1.5)) time, where K(G) is the vertex connectivity of G. In this paper, an efficient algorithm is designed to solve vertex connectivity problem, which takes O(n(2)) time and O(n) space for a trapezoid graph.

关键词： design and analysis of algorithms trapezoid graph connected components vertex connectivity

来源：评论

学校读者我要写书评

暂无评论

Approximating the selected-internal Steiner tree

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-3期381卷 288-291页

作者： Hsieh, Sun-Yuan Yang, Shih-Cheng Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 70101 Taiwan

In this paper, we consider a variant of the well-known Steiner tree problem. Given a complete graph G = (V, E) with a cost function c : E -> R+ and two subsets R and R' satisfying R' subset of R subset of V, a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in R such that each vertex in R' cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we present a 2 rho-approximation algorithm for the problem, where p is the best-known approximation ratio for the Steiner tree problem. (c) 2007 Elsevier B.V. All rights reserved.

关键词： design and analysis of algorithms approximation algorithms steiner tree the selected-internal steiner tree problem MAX SNP-hard

来源：评论

学校读者我要写书评

暂无评论

Routing of single-source and multiple-source queries in static sensor networks

引用

JOURNAL OF DISCRETE algorithms 2007年第1期5卷 1-11页

作者： Gasieniec, Leszek Su, Chang Wong, Prudence W. H. Xin, Qin Univ Liverpool Dept Comp Sci Liverpool Merseyside England Univ Bergen Dept Informat Bergen Norway

In this paper, we introduce new geometric ad-hoc routing algorithms to route queries in static sensor networks. For singlesource-queries routing, we utilise a centralised mechanism to accomplish a query using an asymptotically optimal number of transmissions O(c), where c is the length of the shortest path between the source and the destination. For multiple-source-queries routing, the number of transmissions for each query is bounded by O(c log n), where n is the number of nodes in the network. For both single-source and multiple-source queries, the routing stage is preceded by preprocessing stages requiring O(nD) and O(n(2)D) transmissions, respectively, where D is the diameter of the network. Our algorithm improves the complexity of the currently best known algorithms in terms of the number of transmissions for each query. The preprocessing is worthwhile if it is followed by frequent queries. We could also imagine that there is an extra initial power (say, batteries) available during the preprocessing stage or alternatively the positions of the sensors are known in advance and the preprocessing can be done before the sensors are deployed in the field. It is also worth mentioning that a lower bound of Omega(c(2)) transmissions has been proved if preprocessing is not allowed [***, ***, ***, Asymptotically optimal geometric mobile ad-hoc routing, in: Proceedings of the Sixth International Workshop on Discrete Algorithm and Methods for Mobility, Atlanta, GA, September 2002, pp. 24-33]. (C) 2006 Elsevier B.V. All rights reserved.

关键词： Wireless sensor network Geometric routing Communication design and analysis of algorithms Memory constraint

来源：评论

学校读者我要写书评

暂无评论

Optimal offline extraction of irredundant motif bases

引用

13th Annual International Conference on Computing and Combinatorics (COCOON 2007)

作者： Apostolico, Alberto Tagliacollo, Claudia Georgia Inst Technol Atlanta GA 30332 USA

ISBN: (纸本)9783540735441

The problem of extracting a basis of irredundant motifs from a sequence is considered. In previous work such bases were built incrementally for all suffixes of the input string s in O(n(3)), where n is the length of s. Faster, non-incremental algorithms have been based on the landmark approach to string searching due to Fischer and Paterson, and exhibit respective time bounds of O(n(2) logn log|Sigma|) and O(|Sigma|n(2) log(2) n log log n), with Z denoting the alphabet. The algorithm by Fischer and Paterson makes crucial use of the FFT, which is impractical with long sequences. The algorithm presented in the present paper does not need to resort to the FFT and yet is asymptotically faster than previously available ones. Specifically, an off-line algorithm is presented taking time O(|Sigma|n(2)), which is optimal for finite Z.

关键词： design and analysis of algorithms pattern matching motif discovery irredundant motif basis

来源：评论

学校读者我要写书评

暂无评论

Faster treasure hunt and better strongly universal exploration sequences

引用

18th International Symposium on algorithms and Computations (ISAAC 2007)

作者： Xin, Qin Univ Bergen Dept Informat N-5008 Bergen Norway

ISBN: (纸本)9783540771180

We study the explicit deterministic treasure hunt problem in an n-vertex network. This problem was firstly introduced by Ta-Shma, and Zwick in [9] [SODA'07]. It is the variant of the well known rendezvous problem in which one of the robot (the treasure) is always stationary. We obtain an O(n(c (1+1/lambda)))-time solution for this problem, which significantly improves the currently best known result of running time O(n(2c)) in [9], where c is a fixed constant from the construction of an universal exploration sequence in [8,9], lambda is a constant integer and lambda >> 1. The treasure hunt problem motivates the study of strongly universal exploration sequences. We give a better explicit construction of strongly universal exploration sequences than the one in [9].

关键词： design and analysis of algorithms distributed computing networks rendezvous strongly universal exploration sequences

来源：评论

学校读者我要写书评

暂无评论

Efficient enumeration of phylogenetically informative substrings

引用

10th Annual International Conference on Research in Computational Molecular Biology

作者： Angelov, Stanislav Harb, Boulos Kannan, Sampath Khanna, Sanjeev Kim, Junhyong Univ Penn Dept Comp & Informat Sci Philadelphia PA 19104 USA Univ Penn Dept Biol Philadelphia PA 19104 USA

ISBN: (纸本)3540332952

We study the problem of enumerating substrings that are common amongst genomes that share evolutionary descent. For example, one might want to enumerate all identical (therefore conserved) substrings that are shared between all mammals and not found in nonmammals. Such collection of substrings may be used to identify conserved subsequences or to construct sets of identifying substrings for branches of a phylogmetic tree. For two disjoint sets of genomes on a phylogenetic tree, a substring is called a tag if it is found in all of the genomes of one set and none of the genomes of the other set. We present a near-linear time algorithm that finds all tags in a given phylogeny;and a sublinear space algorithm (at the expense of running time) that is more suited for very large data sets. Under a stochastic model of evolution, we show that a simple process of tag-generation essentially captures all possible ways of generating tags. We use this insight to develop a faster tag discovery algorithm with a small chance of error. However, since tags are not guaranteed to exist in a given data set, we generalize the notion of a tag from a single substring to a set of substrings. We present a linear programming-based approach for finding approximate generalized tag sets. Finally, we use our tag enumeration algorithm to analyze a phylogeny containing 57 whole microbial genomes. We find tags for all nodes in the phylogeny except the root for which we find generalized tag sets.

关键词： design and analysis of algorithms phylogenetically informative substring phylogeny stochastic analysis suffix tree

来源：评论

学校读者我要写书评

暂无评论

Faster two-dimensional pattern matching with rotations

引用

THEORETICAL COMPUTER SCIENCE 2006年第3期368卷 196-204页

作者： Amir, Amihood Kapah, Oren Tsur, Dekel Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of O(n(2)m(3)), where the size of the text is n x n and the size of the pattern is m x m. In this paper we present a new algorithm for the problem whose running time is 0(n(2),m(2)). (c) 2006 Published by Elsevier B.V.

关键词： design and analysis of algorithms two-dimensional pattern matching rotation

来源：评论

学校读者我要写书评

暂无评论

MAXIMUM WEIGHT INDEPENDENT SET OF CIRCULAR-ARC GRAPH AND ITS APPLICATION

引用

JOURNAL OF APPLIED MATHEMATICS AND COMPUTING 2006年第3期22卷 161-174页

作者： Mandal, Swagata G Pal, Madhumangal Vidyasagar Univ Midnapore W Bengal India Vidyasagar Univ Dept Appl Math Oceanol & Comp Programming Midnapore 721302 W Bengal India

In this paper, an algorithm is designed to find a maximum weight independent set of a circular-arc graph with n vertices. The weights considered here are all non-negative real numbers and associated with each of the vertex of the graph. The proposed algorithm runs in time O(n(2)). Here we shown that the program slots of television channels during 24 hours can be modeled as a circular-arc graph. Each program represents a vertex and number of viewers of that program represents the weight of the corresponding vertex. Two vertices are connected by an edge iff the corresponding program slots have a common program time, i.e., if I-i and I-j are the program slots of two programs i and j then the corresponding vertices i and j are connected by an edge iff I-i boolean AND I-j not equal phi. We also shown that the non-overlapping program slots with maximum number of viewers can be selected by computing maximum weight independent set on the corresponding circular-arc graph.

关键词： design and analysis of algorithms maximum weight independent set circular-arc graph interval graph modeling

来源：评论

学校读者我要写书评

暂无评论

Faster two-dimensional pattern matching with rotations

Faster two-dimensional pattern matching with rotations

引用

15th Annual Symposium on Combinatorial Pattern Matching

ISBN: (纸本)354022341X

关键词： design and analysis of algorithms two-dimensional pattern matching rotation

来源：评论

学校读者我要写书评

暂无评论

Determining approximate shortest paths on weighted polyhedral surfaces

引用

JOURNAL OF THE ACM 2005年第1期52卷 25-53页

作者： Aleksandrov, L Maheshwari, A Sack, JR Bulgarian Acad Sci IPOI BU-1113 Sofia Bulgaria Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

In this article, we present an approximation algorithm for solving the single source shortest paths problem on weighted polyhedral surfaces. We consider a polyhedral surface P as consisting of n triangular faces, where each face has an associated positive weight. The cost of travel through a face is the Euclidean distance traveled, multiplied by the face's weight. For a given parameter E, 0 < epsilon < 1, the cost of the computed paths is at most 1 + epsilon times the cost of corresponding shortest paths. Our algorithm is based on a novel way of discretizing polyhedral surfaces and utilizes a generic greedy approach for computing shortest paths in geometric graphs obtained by such discretization. Its running time is O(C(P)(n)/(rootepsilon) log (n)/(epsilon) log (1)/(epsilon)) time, where C(P) captures geometric parameters and the weights of the faces of P.

关键词： algorithms design performance design and analysis of algorithms computational geometry approximation algorithms shortest path problems polyhedral surfaces weighted paths

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：