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

All-pairs shortest-paths computation in the presence of negative cycles

INFORMATION PROCESSING LETTERS 2002年第6期81卷 341-343页

作者： Mehlhorn, K Priebe, V Schäfer, G Sivadasan, N Max Planck Inst Informat D-66123 Saarbrucken Germany

We present an algorithm that solves the all-pairs shortest-paths problem on a directed graph with n vertices and m arcs in time O(nm + n(2) logn), where the arcs are assigned real, possibly negative costs. Our algorithm is new in the following respect. It computes the distance mu(v, w) between each pair v, w of vertices even in the presence of negative cycles, where mu(v, w) is defined as the infimum of the costs of all directed paths from v to w. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： graph algorithms shortest-paths algorithms

来源：评论

学校读者我要写书评

暂无评论

GENERIC ∊-REMOVAL AND INPUT ∊-NORMALIZATION algorithms FOR WEIGHTED TRANSDUCERS

引用

International Journal of Foundations of Computer Science 2002年第1期13卷 129-143页

作者： MEHRYAR MOHRI AT&T Labs - Research 180 Park Avenue Room E135 Florham Park NJ 07932 USA

We present a new generic ∊-removal algorithm for weighted automata and transducers defined over a semiring. The algorithm can be used with any semiring covered by our framework and works with any queue discipline adopted. It can be used in particular in the case of unweighted automata and transducers and weighted automata and transducers defined over the tropical semiring. It is based on a general shortest-distance algorithm that we briefly describe. We give a full description of the algorithm including its pseudocode and its running time complexity, discuss the more efficient case of acyclic automata, an on-the-fly implementation of the algorithm and an approximation algorithm in the case of the semirings not covered by our framework. We illustrate the use of the algorithm with several semirings. We also describe an input ∊-normalization algorithm for weighted transducers based on the general shortest-distance algorithm. The algorithm, which works with all semirings covered by our framework, admits an on-the-fly implementation.

关键词： finite automata finite-state transducers rational power series semirings ∊-removal shortest-paths algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimization algorithms for sequential transducers

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期234卷 177-201页

作者： Mohri, M AT&T Labs Res Florham Park NJ 07932 USA

We present general algorithms for minimizing sequential finite-state transducers that output strings or numbers. The algorithms are shown to be efficient since in the case of acyclic transducers and for output strings they operate in O(S + \ E \ + \ V \ + (\ E \ - \ V \ + \ F \).(\ P-max\ + 1)) steps, where S is the sum of the lengths of all output labels of the resulting transducer, E the set of transitions of the given transducer, V the set of its states, F the set of final states, and P-max one of the longest of the longest common prefixes of the output paths leaving each state of the transducer. The algorithms apply to a larger class of transducers which includes subsequential transducers. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： finite automata finite-state transducers rational power series semiring shortest-paths algorithms

来源：评论

学校读者我要写书评

暂无评论

A Computational Study of Routing algorithms for Realistic Transportation Networks

引用

ACM Journal of Experimental Algorithmics 1999年 4卷 6-6页

作者： Jacob, Riko Marathe, Madhav Nagel, Kai RRTCS Department of Computer Science University of Aarhus DK-8000 Århus C Ny Munkegade Bldg. 540 Denmark Los Alamos National Laboratory MS M997 Los Alamos NM 87545 P.O. Box 1663 United States

We carry out an experimental analysis of a number of shortest-path (routing) algorithms investigated in the context of the TRANSIMS (TRansportation ANalysis and SIMulation System) project. The main focus of the paper is to study how various heuristic as well as exact solutions and associated data structures affect the computational performance of the software developed for realistic transportation networks. For this purpose we have used a road network representing, with high degree of resolution, the Dallas Fort-Worth urban area. We discuss and experimentally analyze various one-to-one shortest-path algorithms. These include classical exact algorithms studied in the literature as well as heuristic solutions that are designed to take into account the geometric structure of the input instances. Computational results are provided to compare empirically the efficiency of various algorithms. Our studies indicate that a modified Dijkstra's algorithm is computationally fast and an excellent candidate for use in various transportation planning applications as well as ITS related technologies. © 1999, ACM. All rights reserved.

关键词： Design and Analysis of algorithms Experimental Analysis Network Design shortest-paths algorithms Transportation Planning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：