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 i...
详细信息
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.
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....
详细信息
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 shortestpath 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.
The objective of this paper is to advance the view that solving the all-pairs shortestpath (APSP) problem for a chordal graph G is a two-step process: the first step is determining vertex pairs at distance two (i.e.,...
详细信息
The objective of this paper is to advance the view that solving the all-pairs shortestpath (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 shortestpaths. 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.
This paper presents six new variants of the polynomially bounded Partitioning shortestpath (PSP) algorithm for finding the shortestpath from one node to all other nodes in a network. Three of these variants, one for...
详细信息
This paper presents six new variants of the polynomially bounded Partitioning shortestpath (PSP) algorithm for finding the shortestpath 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.
Dijkstra's algorithm solves the single-source shortestpath problem on any directed graph in O(m + n log n) time when a Fibonacci heap is used as the frontier set data structure. Here n is the number of vertices a...
详细信息
Dijkstra's algorithm solves the single-source shortestpath problem on any directed graph in O(m + n log n) time when a Fibonacci heap is used as the frontier set data structure. Here n is the number of vertices and m is the number of edges in the graph. If the graph is nearly acyclic, other algorithms can achieve a time complexity lower than that of Dijkstra's algorithm. Abuaiadh and Kingston gave a single-source shortestpath algorithm for nearly acyclic graphs with O(m + n log t) time complexity, where the new parameter, t, is the number of delete-min operations performed in priority queue manipulation. If the graph is nearly acyclic, then t is expected to be small, and the algorithm out-performs Dijkstra's algorithm. Takaoka, using a different definition for acyclicity, gave an algorithm with O(m + n log k) time complexity. In this algorithm, the new parameter, k, is the maximum cardinality of the strongly connected components in the graph. The generalised single-source (GSS) problem allows an initial distance to be defined at each vertex in the graph. Decomposing a graph into r trees allows the GSS problem to be solved within O(m + r log r) time. This paper presents a new all-pairs algorithm with a time complexity of O(mn + nr log r), where r is the number of acyclic parts resulting when the graph is decomposed into acyclic parts. The acyclic decomposition used is setwise unique and can be computed in O(mn) time. If the decomposition has been pre-calculated, then GSS can be solved within O(m + r log r) time whenever edge-costs in the graph change. A second new all-pairs algorithm is presented, with O(mn + nr 2) worst-case time complexity, where r is the number of vertices in a pre-calculated feedback vertex set for the nearly acyclic graph. For certain graphs, these new algorithms offer an improvement on the time complexity of the previous algorithms. (C) 2002 Elsevier Science B.V. All rights reserved.
作者：
UditiArun, M.VIT Univ
Elect & Commun Engn Vellore Tamil Nadu India VIT Univ
Embedded Syst Vellore Tamil Nadu India
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 shortestpaths. Th...
详细信息
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 shortestpaths. 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.
A multimodal trip planner that produces optimal journeys involving both public transport and private vehicle legs has to solve a number of shortestpath problems, both on the road network and the public transport netw...
详细信息
A multimodal trip planner that produces optimal journeys involving both public transport and private vehicle legs has to solve a number of shortestpath problems, both on the road network and the public transport network. The algorithms that are used to solve these shortestpath 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.
In the single-source shortestpath (SSSP) problem, we have to find the shortestpaths from a source vertex v to all other vertices in a graph. In this paper, we introduce a novel parallel algorithm, derived from the B...
详细信息
ISBN:
(纸本)9780769552071
In the single-source shortestpath (SSSP) problem, we have to find the shortestpaths 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.
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 ...
详细信息
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.
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 arbit...
详细信息
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.
暂无评论