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

shortest path algorithms for functional environments

DISCRETE OPTIMIZATION 2015年 18卷 217-251页

作者： Boguchwal, Louis

This research generalises classic shortest path algorithms to network environments in which arc-costs are governed by functions, rather than fixed weights. We show that the asymptotic efficiency of our algorithms is identical to their classic counterparts. Previous results, since Knuth in 1976, require several restrictive assumptions on the functions permitted in the network. In contrast, our algorithms require only monotonicity. We present examples illustrating that this is the largest class of functions to which classic algorithms can be generalised. Applications of this work include critical path extensions to solve sequential decision-problems, and generalised network flow with nonlinear gain functions. (C) 2015 Elsevier B.V. All rights reserved.

关键词： shortest path algorithms Combinatorial optimisation Networks Sequential decision-problems Generalised flow

来源：评论

学校读者我要写书评

暂无评论

Modeling wildfire propagation with Delaunay triangulation and shortest path algorithms

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2012年第3期218卷 775-788页

作者： Stepanov, Alexander Smith, James MacGregor Univ Massachusetts Dept Mech & Ind Engn Amherst MA 01003 USA

In this paper, a methodology for modeling surface wildfire propagation through a complex landscape is presented. The methodology utilizes a Delaunay triangulation to represent surface fire spread within the landscape. A procedure to construct the graph and estimate the rate of spread along the edges of a network is discussed. After the Delaunay data structure is constructed, a two pass shortest path algorithm is incorporated to estimate the minimum travel time paths and fire arrival times. Experimental results are also included. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Natural resources Delaunay triangulation shortest path algorithms Minimum travel time Wildfire modeling

来源：评论

学校读者我要写书评

暂无评论

Unified all-pairs shortest path algorithms in the chordal hierarchy

引用

DISCRETE APPLIED MATHEMATICS 1997年第1期77卷 59-71页

作者： Han, K Sekharan, CN Sridhar, R LOYOLA UNIV DEPT MATH & COMP SCI CHICAGO IL 60626 USA UNIV OKLAHOMA SCH COMP SCI NORMAN OK 73019 USA

The objective of this paper is to advance the view that solving the all-pairs shortest path (APSP) problem for a chordal graph G is a two-step process: the first step is determining vertex pairs at distance two (i.e., computing G(2)) and the second step is finding the vertex pairs at distance three or more. The main technical result here is that the APSP problem for a chordal graph can be solved in O(n(2)) time (optimally), if G(2) is already known. It can be shown that computing G(2) for chordal graphs is as hard as for general graphs. We then show certain subclasses of chordal graphs for which G(2) can be computed more efficiently. This leads to optimal APSP algorithms for these classes of graphs in a more natural way than previously known results. Finally, we present an optimal parallel algorithm for the APSP problem on chordal graphs by exploiting new structural properties of shortest paths. Our parallel algorithm uses O(M(n)) operations where M(n) is the time needed for the fastest known algorithm for multiplying two II x ii matrices over a ring.

关键词： CRYGEP gene Parallel algorithms KIAA1549L gene shortest path Chord shortest path algorithms PRRC2A gene COPPER ALLOY NO 92310

来源：评论

学校读者我要写书评

暂无评论

NEW POLYNOMIAL shortest-path algorithms AND THEIR COMPUTATIONAL ATTRIBUTES

引用

MANAGEMENT SCIENCE 1985年第9期31卷 1106-1128页

作者： GLOVER, F KLINGMAN, DD PHILLIPS, NV SCHNEIDER, RF UNIV TEXAS GRAD SCH BUSINESSAUSTINTX 78712

This paper presents six new variants of the polynomially bounded Partitioning shortest path (PSP) algorithm for finding the shortest path from one node to all other nodes in a network. Three of these variants, one for negative arc lengths, but without negative cycles, and two for nonnegative arc lengths, augment the PSP algorithm to maintain a property called sharp by Shier and Witzgall. The other three variants augment the PSP algorithm to maintain a property called near-sharp for nonnegative arc lengths. Extensive computational testing is presented on one of the sharp variants for nonnegative arc lengths and two of the near-sharp variants. The empirical results based on 4500 test problems with 90 different configurations and three different network topologies indicate that these new algorithms have excellent computational performance characteristics. Based on total solution times for the 4500 test problems, these new algorithms out-perform all other algorithms tested. In addition, one of the near-sharp algorithms strictly dominates all others on all problem topologies tested.

关键词： shortest path algorithms

来源：评论

学校读者我要写书评

暂无评论

Comparative Analysis of Parallelised shortest path algorithms using Open MP 3

Comparative Analysis of Parallelised Shortest Path Algorithm...

引用

3rd IEEE International Conference on Sensing, Signal Processing and Security (ICSSS)

作者： Uditi Arun, M. VIT Univ Elect & Commun Engn Vellore Tamil Nadu India VIT Univ Embedded Syst Vellore Tamil Nadu India

ISBN: (纸本)9781509049295

this paper presents parallel implementations and includes performance analysis of three prominent graph algorithms (i.e., Bellman Ford, Floyd-Warshall and Dijkstra) used for finding the all-pairs of shortest paths. The algorithm implementations were parallelized using Open MP (Open Multi-Processing). Their performances were measured on 4 different configurations i.e. dual core i3, quad core i5, quad core i7 and 8 core processors. This paper also presents a comparative study of serial and parallel implementations of these algorithms keeping execution time and number of graph nodes as the parameter. Finally, the results show that, execution time can be reduced using parallel implementation for larger number of graph nodes. Also, the conclusions are drawn for the best algorithm to be used which works for all the graph nodes with less execution time.

关键词： shortest path algorithms Open MP Parallel computing execution time

来源：评论

学校读者我要写书评

暂无评论

Critical Review of Time-Dependent shortest path algorithms: A Multimodal Trip Planner Perspective

引用

TRANSPORT REVIEWS 2014年第4期34卷 522-539页

作者： Casey, Bradley Bhaskar, Ashish Guo, Hao Chung, Edward Queensland Univ Technol Fac Built Environm & Engn Smart Transport Res Ctr Brisbane Australia Queensland Univ Technol Smart Transport Res Ctr Fac Built Environm & Engn Brisbane Qld 4001 Australia

A multimodal trip planner that produces optimal journeys involving both public transport and private vehicle legs has to solve a number of shortest path problems, both on the road network and the public transport network. The algorithms that are used to solve these shortest path problems have been researched since the late 1950s. However, in order to provide accurate journey plans that can be trusted by the user, the variability of travel times caused by traffic congestion must be taken into consideration. This requires the use of more sophisticated time-dependent shortest path algorithms, which have only been researched in depth over the last two decades, from the mid-1990s. This paper will review and compare nine algorithms that have been proposed in the literature, discussing the advantages and disadvantages of each algorithm on the basis of five important criteria that must be considered when choosing one or more of them to implement in a multimodal trip planner.

关键词： multimodal trip planning time-dependent dynamic shortest path algorithms

来源：评论

学校读者我要写书评

暂无评论

Scalable Single Source shortest path algorithms for Massively Parallel Systems

Scalable Single Source Shortest Path Algorithms for Massivel...

引用

IEEE 28th International Parallel & Distributed Processing Symposium (IPDPS)

作者： Chakaravarthy, Venkatesan T. Checconi, Fabio Petrini, Fabrizio Sabharwal, Yogish IBM Res India New Delhi India IBM Corp TJ Watson Res Ctr Armonk NY 10504 USA

ISBN: (纸本)9780769552071

In the single-source shortest path (SSSP) problem, we have to find the shortest paths from a source vertex v to all other vertices in a graph. In this paper, we introduce a novel parallel algorithm, derived from the Bellman-Ford and Delta-stepping algorithms. We employ various pruning techniques, such as edge classification and direction-optimization, to dramatically reduce inter-node communication traffic, and we propose load balancing strategies to handle higher-degree vertices. The extensive performance analysis shows that our algorithms work well on scale-free and real-world graphs. In the largest tested configuration, an R-MAT graph with 2(38) vertices and 2(42) edges on 32, 768 Blue Gene/Q nodes, we have achieved a processing rate of three Trillion Edges Per Second (TTEPS), a four orders of magnitude improvement over the best published results.

关键词： BFS Blue Gene/Q Graph algorithms Parallelization SSSP Supercomputer Graph algorithms supercomputer parallelization vertex head shortest path algorithms parallel system BUNDESAMT FUER STRAHLENSCHUTZ Parallel algorithms scale-free shortest path

来源：评论

学校读者我要写书评

暂无评论

shortest path algorithms for Sensor Node Localization for Internet of Things

Shortest Path Algorithms for Sensor Node Localization for In...

引用

Emerging Trends in Communication, Control and Computing (ICONC3), International Conference on

作者： Ajay Kumar V. K. Jain P. P. Bhattacharya Computer Science and Engineering School of Engineering and Technology Mody University of Science and Technology Lakshmangarh India

ISBN: (数字)9781728114200

ISBN: (纸本)9781728114217

Internet of Things have gained the interest of researchers and other academic communities due to their applications in various fields. Determining the location of a sensor node within the specified area consisting of number of sensors and smart devices is very crucial, which requires association between the devices and the sensor nodes[1]. Localization is the basic requirement for other services of any smart network like communication, clustering, distribution, routing etc. Multidimensional scaling is one of the approach used effectively for the sensor node localization. In this approach the process to obtain the minimum distance path between the pair of sensors are used which helps in estimating the relative positions of the nodes. This paper includes the explanation and comparison of different types shortest path algorithms. Then, we discuss about the use of multidimensional scaling process to obtain the absolute positions of nodes with reduced error cumulation in a smart network. It is mandatory to have a efficient, economic and scalable sensor node position estimation process for a wireless sensor network and hence for internet of Things. The results obtained experimentally proves the efficiency and effectiveness of the methods discussed for use in Internet of Things with various routing, topology and area.

关键词： Global Positioning System Internet of Things Multidimensional Scaling shortest path Wireless Sensor Networks Internet of things Multi dimensional scaling Wireless sensor networks shortest path Global Positioning Systems Sensors shortest path algorithms Thing Internets minimum distance DESIGNATED AREA

来源：评论

学校读者我要写书评

暂无评论

I/O-Efficient shortest path algorithms for Undirected Graphs with Random or Bounded Edge Lengths

引用

ACM TRANSACTIONS ON algorithms 2012年第3期8卷 22-22页

作者： Meyer, Ulrich Zeh, Norbert Dalhousie Univ Fac Comp Sci Halifax NS B3H 1W5 Canada Goethe Univ Frankfurt Inst Informat D-60325 Frankfurt Germany

We present I/O-efficient single-source shortest path algorithms for undirected graphs. Our main result is an algorithm with I/O complexity O(root nm log L)/ B + MST(n, m)) on graphs with n vertices, m edges, and arbitrary edge lengths between 1 and L;MST(n, m) denotes the I/O complexity of computing a minimum spanning tree;B denotes the disk block size. If the edge lengths are drawn uniformly at random from ( 0, 1], the expected I/O complexity of the algorithm is O(root nm/ B + ( m/ B) log B + MST(n, m)). A simpler algorithm has expected I/O complexity O(root nm log B)/ B + MST(n, m) for uniformly random edge lengths.

关键词： algorithms Theory Graph algorithms I/O-efficient algorithms memory hierarchies shortest path algorithms

来源：评论

学校读者我要写书评

暂无评论

Scalable Single Source shortest path algorithms for Massively Parallel Systems

Scalable Single Source Shortest Path Algorithms for Massivel...

引用

IEEE International Parallel and Distributed Processing Symposium

作者： Venkatesan T. Chakaravarthy Fabio Checconi Fabrizio Petrini Yogish Sabharwal IBM Research - India IBM T J Watson Research Center

ISBN: (纸本)9781479938018

In the single-source shortest path (SSSP) problem, we have to find the shortest paths from a source vertex v to all other vertices in a graph. In this paper, we introduce a novel parallel algorithm, derived from the Bellman-Ford and Delta-stepping algorithms. We employ various pruning techniques, such as edge classification and direction-optimization, to dramatically reduce inter-node communication traffic, and we propose load balancing strategies to handle higher-degree vertices. The extensive performance analysis shows that our algorithms work well on scale-free and real-world graphs. In the largest tested configuration, an R-MAT graph with 2~(38) vertices and 2~(42) edges on 32,768 Blue Gene/Q nodes, we have achieved a processing rate of three Trillion Edges Per Second (TTEPS), a four orders of magnitude improvement over the best published results.

关键词： vertex head shortest path algorithms parallel system Parallel algorithms scale-free shortest path Scalability telecommunication traffic

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：