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

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

来源：评论

学校读者我要写书评

暂无评论

A functional approach to external graph algorithms

引用

ALGORITHMICA 2002年第3期32卷 437-458页

作者： Abello, J Buchsbaum, AL Westbrook, JR AT&T Labs Res Shannon Lab Florham Pk NJ 07932 USA 20th Century Televis Los Angeles CA 90025 USA

We present a new approach for designing external graph algorithms and use it to design simple, deterministic and randomized external algorithms for computing connected components, minimum spanning forests, bottleneck minimum spanning forests, maximal independent sets (randomized only), and maximal matchings in undirected graphs. Our I/O bounds compete with those of previous approaches. We also introduce a semi-external model, in which the vertex set but not the edge set of a graph fits in main memory. In this model we give an improved connected components algorithm, using new results for external grouping and sorting with duplicates. Unlike previous approaches, ours is purely functional-without side effects-and is thus amenable to standard checkpointing and pro.-ramming language optimization techniques. This is an important practical consideration for applications that may take hours to run.

关键词： connected components external memory algorithms graph algorithms maximal matchings maximal independent sets minimum spanning trees functional programming

来源：评论

学校读者我要写书评

暂无评论

Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes

引用

INFORMATION PROCESSING LETTERS 2004年第4期89卷 165-173页

作者： Brandstädt, A Le, VB De Ridder, HN Univ Rostock Fachbereich Informat D-18051 Rostock Germany

Modular decomposition of graphs is a powerful tool for designing efficient algorithms for problems on graphs such as Maximum Weight Stable Set (MWS) and Maximum Weight Clique. Using this tool we obtain O(n (.) m) time algorithms for MWS on chair- and xbull-free graphs which considerably extend an earlier result on bull- and chair-free graphs by De Simone and Sassano (the chair is the graph with vertices a, b, c, d, e and edges ab, be, cd, be, and the xbull is the graph with vertices a, b, c, d, e, f and edges ab, be, cd, de, bf, cf). Moreover, our algorithm is robust in the sense that we do not have to check in advance whether the input graphs are indeed chair- and xbull-free. (C) 2003 Elsevier B.V. All rights reserved.

关键词： efficient graph algorithms robust graph algorithms modular decomposition maximum weight stable set problem on graphs graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Geometric containers for efficient shortest-path computation

引用

ACM Journal of Experimental Algorithmics 2005年 10卷 1.3–es页

作者： Wagner, Dorothea Willhalm, Thomas Zaroliagis, Christos Institut für Theoretische Informatik Universität Karlsruhe (TH) Postfach 6980 Karlsruhe 76128 Germany Computer Technology Institute P.O. Box 1122 Patras 26110 Greece Department of Computer Engineering and Informatics University of Patras Patras 26500 Greece

A fundamental approach in finding efficiently best routes or optimal itineraries in traffic information systems is to reduce the search space (part of graph visited) of the most commonly used shortest path routine (Dijkstra's algorithm) on a suitably defined graph. We investigate reduction of the search space while simultaneously retaining data structures, created during a preprocessing phase, of size linear (i.e., optimal) to the size of the graph. We show that the search space of Dijkstra's algorithm can be significantly reduced by extracting geometric information from a given layout of the graph and by encapsulating precomputed shortest-path information in resulted geometric objects (containers). We present an extensive experimental study comparing the impact of different types of geometric containers using test data from real-world traffic networks. We also present new algorithms as well as an empirical study for the dynamic case of this problem, where edge weights are subject to change and the geometric containers have to be updated and show that our new methods are two to three times faster than recomputing everything from scratch. Finally, in an appendix, we discuss the software framework that we developed to realize the implementations of all of our variants of Dijkstra's algorithm. Such a framework is not trivial to achieve as our goal was to maintain a common code base that is, at the same time, small, efficient, and flexible, as we wanted to enhance and combine several variants in any possible way. © 2005 ACM.

关键词： Data structures and algorithms Dijkstra's algorithm Geometric container graph algorithms Shortest path Traffic network

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：