Note: This page contains sample records for the topic shortest path problems from Science.gov.
While these samples are representative of the content of Science.gov,
they are not comprehensive nor are they the most current set.
We encourage you to perform a real-time search of Science.gov
to obtain the most current and comprehensive results.
Last update: August 15, 2014.
1

Shortest Paths.  

ERIC Educational Resources Information Center

There are many uses for the shortest path algorithm presented which are limited only by our ability to recognize when a problem may be converted into the shortest path in a graph representation. (Author/TG)

Shore, M. L.

1980-01-01

2

An applicable method for solving the shortest path problems  

Microsoft Academic Search

A theorem of Hardy, Littlewood, and Polya, first time is used to find the variational form of the well known shortest path problem, and as a consequence of that theorem, one can find the shortest path problem via quadratic programming. In this paper, we use measure theory to solve this problem. The shortest path problem can be written as an

M. Zamirian; M. H. Farahi; A. R. Nazemi

2007-01-01

3

Faster algorithms for the shortest path problem  

Microsoft Academic Search

Efficient implementations of Dijkstra's shortest path algorithm are investigated. A new data structure, called the radix heap, is proposed for use in this algorithm. On a network with n vertices, m edges, and nonnegative integer arc costs bounded by C, a one-level form of radix heap gives a time bound for Dijkstra's algorithm of O(m + n log C). A

Ravindra K. Ahuja; Kurt Mehlhorn; James B. Orlin; Robert Endre Tarjan

1990-01-01

4

On an instance of the inverse shortest paths problem  

Microsoft Academic Search

The inverse shortest paths problem in a graph is considered, that is, the problem of recovering the arc costs given some information about the shortest paths in the graph. The problem is first motivated by some practical examples arising from applications. An algorithm based on the Goldfarb-Idnani method for convex quadratic programming is then proposed and analyzed for one of

D. Burton; Philippe L. Toint

1992-01-01

5

Valid Inequalities for a Shortest-Path Routing Optimization Problem  

Microsoft Academic Search

In autonomous systems of the Internet packets are routed on shortest paths to their destinations, for example according to the ECMP principle. The problem of finding a feasible traffic routing configuration realized on paths which can be generated by a system of weights assigned to IP links is NP-hard. This problem can be formulated as a mixed-integer program and attempted

M. Dzida; M. Mycek; M. Zago

6

Incremental Algorithms for the Single-Source Shortest Path Problem  

Microsoft Academic Search

We consider the problem of updating a single source shortest path tree in either a directed or an undirected graph, with positive real edge weights. Our semidynamic algorithms for the incremental problem (handling edge insertions and cost decrements) work for any graph, but their performances depend on the class of the considered graph. In any case our algorithms have optimal

Daniele Frigioni; Alberto Marchetti-spaccamela; Umberto Nanni

1994-01-01

7

An Improved Physarum polycephalum Algorithm for the Shortest Path Problem  

PubMed Central

Shortest path is among classical problems of computer science. The problems are solved by hundreds of algorithms, silicon computing architectures and novel substrate, unconventional, computing devices. Acellular slime mould P. polycephalum is originally famous as a computing biological substrate due to its alleged ability to approximate shortest path from its inoculation site to a source of nutrients. Several algorithms were designed based on properties of the slime mould. Many of the Physarum-inspired algorithms suffer from a low converge speed. To accelerate the search of a solution and reduce a number of iterations we combined an original model of Physarum-inspired path solver with a new a parameter, called energy. We undertook a series of computational experiments on approximating shortest paths in networks with different topologies, and number of nodes varying from 15 to 2000. We found that the improved Physarum algorithm matches well with existing Physarum-inspired approaches yet outperforms them in number of iterations executed and a total running time. We also compare our algorithm with other existing algorithms, including the ant colony optimization algorithm and Dijkstra algorithm.

Wang, Qing; Adamatzky, Andrew; Chan, Felix T. S.; Mahadevan, Sankaran

2014-01-01

8

Average Network Flow Problem: Shortest Path and Minimum Cost Flow Formulations, Algorithms, Heuristics, and Complexity.  

National Technical Information Service (NTIS)

Integrating value focused thinking with the shortest path problem results in a unique formulation called the multiobjective average shortest path problem. We prove this is NP-complete for general graphs. For directed acyclic graphs, an efficient algorithm...

J. D. Jordan

2012-01-01

9

Randomized Shortest-Path Problems: A first study  

Microsoft Academic Search

Suppose you have to route agents through a network from a source node to a destination node in some optimal way; for instance by minimizing the total travel cost. Nothing new up to now - you could use a standard shortest- path algorithm. Suppose, however, that you want to avoid pure deterministic routing policies in order, for instance, to allow

Marco Saerens; Luh Yen; Francois Fouss; Youssef Achbany

10

A branch and bound algorithm for the robust shortest path problem with interval data  

Microsoft Academic Search

Many real problems in transportation and telecommunications can be modelled in mathematical terms as shortest path problems on in- terval digraphs, where an interval of costs is associated with each arc. Intervals represent uncertainty, typical of real situations, about the exact values of costs. In this context, a robust shortest path is a path which is ideally not too far

R. Montemanni; L. M. Gambardella; A. E. Rizzoli; A. V. Donati

2002-01-01

11

A branch and bound algorithm for the robust shortest path problem with interval data  

Microsoft Academic Search

Many real problems in transportation and telecommunications can be modelled in mathematical terms as shortest path problems on interval digraphs, where an interval cost is associated with each arc. Intervals represent uncertainty, typical of real situations, about the exact values of costs. A robust shortest path is a path which is not too far from the best one, whatever the

Roberto Montemanni; Luca Maria Gambardella; Alberto V. Donati

2004-01-01

12

The weighted region problem: finding shortest paths through a weighted planar subdivision  

Microsoft Academic Search

The problem of determining shortest paths through a weighted planar polygonal subdivision with n vertices is considered. Distances are measured according to a weighted Euclidean metric: The length of a path is defined to be the weighted sum of (Euclidean) lengths of the subpaths within each region. An algorithm that constructs a (restricted) “shortest path map” with respect to a

Joseph S. B. Mitchell; Christos H. Papadimitriou

1991-01-01

13

On the Shortest Path to Solve the Problem Based on Vague Sets  

Microsoft Academic Search

The shortest path problem (SPP) is currently being greatly studied in fuzzy sets and systems area. Previously published algorithms and methods for the fuzzy shortest path problem based on discrete or continuous types fuzzy sets of fuzzy arc lengths. However, to present an arc real length in vague set is more reasonable than in fuzzy set. Moreover,carrying on various kinds

Yaling Dou; Hongxing Guo; Jingli Zhou

2008-01-01

14

Shortest Paths for Line Segments  

Microsoft Academic Search

Abstract We study the problem of shortest paths for a line segment in the plane. As a measure of the distance traversed by a path, we take the average curve length of the orbits of prescribed points on the line segment. This problem is nontrivial even in free space (i.e., in the absence of obstacles). We characterize all shortest paths

Christian Icking; Giinter Rote; Emo Welzl; Chee-keng Yap

1993-01-01

15

Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons  

Microsoft Academic Search

Given a triangulation of a simple polygonP, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility withinP. These problems include calculation of the collection of all shortest paths insideP from a given source vertexS to all the other vertices ofP, calculation of the subpolygon ofP consisting of points that are visible from a given

Leonidas J. Guibas; John Hershberger; Daniel Leven; Micha Sharir; Robert Endre Tarjan

1987-01-01

16

Greedy partitioned algorithms for the shortest-path problem  

SciTech Connect

A partitioned, priority-queue algorithm for solving the single-source best-path problem is defined and evaluated. Finding single-source paths for sparse graphs is notable because of its definite lack of parallelism-no known algorithm are scalable. Qualitatively, they discuss the close relationship between the algorithm and previous work by Quinn, Chikayama, and others. Performance measurements of variations of the algorithm, implemented both in concurrent and imperative programming languages on a shared-memory multiprocessor, are presented. This quantitative analysis of the algorithms provides insights into the tradeoffs between complexity and overhead in graph-searching executed in high-level parallel languages with automatic task scheduling.

Adamson, P.; Tick, E. (Univ. of Oregon (United States))

1991-08-01

17

An Evaluation of Potentials of Genetic Algorithm in Shortest Path Problem  

NASA Astrophysics Data System (ADS)

One of the most typical issues considered in combinatorial systems in transportation networks, is the shortest path problem. In such networks, routing has a significant impact on the network's performance. Due to natural complexity in transportation networks and strong impact of routing in different fields of decision making, such as traffic management and vehicle routing problem (VRP), appropriate solutions to solve this problem are crucial to be determined. During last years, in order to solve the shortest path problem, different solutions are proposed. These techniques are divided into two categories of classic and evolutionary approaches. Two well-known classic algorithms are Dijkstra and A*. Dijkstra is known as a robust, but time consuming algorithm in finding the shortest path problem. A* is also another algorithm very similar to Dijkstra, less robust but with a higher performance. On the other hand, Genetic algorithms are introduced as most applicable evolutionary algorithms. Genetic Algorithm uses a parallel search method in several parts of the domain and is not trapped in local optimums. In this paper, the potentiality of Genetic algorithm for finding the shortest path is evaluated by making a comparison between this algorithm and classic algorithms (Dijkstra and A*). Evaluation of the potential of these techniques on a transportation network in an urban area shows that due to the problem of classic methods in their small search space, GA had a better performance in finding the shortest path.

Hassany Pazooky, S.; Rahmatollahi Namin, Sh; Soleymani, A.; Samadzadegan, F.

2009-04-01

18

Shortest Paths Without a Map  

Microsoft Academic Search

Papadimitriou, C.H. and M. Yannakakis, Shortest paths without a map, Theoretical Computer Science 84 (1991) 127-150. We study several versions of the shortest-path problem when the map is not known in advance, but is specified dynamically. We are seeking dynamic decision rules that optimize the worst-case ratio of the distance covered to the length of the (statically) optimal path. We

Christos H. Papadimitriou; Mihalis Yannakakis

1989-01-01

19

Partially observed stochastic shortest path problem - application to sequential paging in cellular networks  

Microsoft Academic Search

Polling a roaming mobile user in a cellular network to determine its location is called paging and it requires the use of limited wireless resources. We formulate the paging problem as an optimal sequential search problem for a Markovian target and show that the resulting problem is an instance of a Partially Observed Stochastic Shortest Path (POSSP) problem. Using the

Sumeetpal Singh; Vikram Krishnamurthy

2001-01-01

20

A genetic algorithm for shortest path routing problem and the sizing of populations  

Microsoft Academic Search

This paper presents a genetic algorithmic approach to the shortest path (SP) routing problem. Variable-length chromosomes (strings) and their genes (parameters) have been used for encoding the problem. The crossover operation exchanges partial chromosomes (partial routes) at positionally independent crossing sites and the mutation operation maintains the genetic diversity of the population. The proposed algorithm can cure all the infeasible

Chang Wook Ahn; Rudrapatna S. Ramakrishna

2002-01-01

21

Research on the Algorithm for K-Shortest Paths Problem based on A* in Complicated Network  

Microsoft Academic Search

Focusing on the optimization problems about complicated network, this paper presents an algorithm KSPA to solve the K-shortest paths problem in complicated network based on A* algorithm, in which the time cost is taken as target function and the establishment of the target function model is given. Experimental results show the proposed KSPA maintains an excellent efficiency on certain public

Lichao Chen; Jia Liu; Yingjun Zhang; Binhong Xie

2007-01-01

22

Linear time algorithms for visibility and shortest path problems inside simple polygons  

Microsoft Academic Search

We present linear time algorithms for solving the following problems involving a simple planar polygon P: (i) Computing the collection of all shortest paths inside P from a given source vertex s to all the other vertices of P; (ii) Computing the subpolygon of P consisting of points that are visible from a segment within P; (iii) Preprocessing P so

Leonidas J. Guibas; John Hershberger; Daniel Leven; Micha Sharir; Robert Endre Tarjan

1986-01-01

23

An Incremental Algorithm for a Generalization of the Shortest-Path Problem  

Microsoft Academic Search

Abstract: The grammar problem, a generalization of the single-source shortest-path problem introduced by Knuth, is to computethe minimum-cost derivation of a terminal string from each non-terminal of a given context-free grammar, with the costof a derivation being suitably defined. This problem also subsumes the problem of finding optimal hyperpaths indirected hypergraphs (under varying optimization criteria) that has received attention recently.

G. Ramalingam; Thomas W. Reps

1996-01-01

24

LABELLING METHODS FOR THE GENERAL CASE OF THE MULTI-OBJECTIVE SHORTEST PATH PROBLEM - A COMPUTATIONAL STUDY  

Microsoft Academic Search

This paper is devoted to the study of labelling techniques for solving the multi-objective shortest path problem (MSPP) which is an extension of the shortest path problem (SPP) resulting from considering simultaneously more than one cost function (criteria) for the arcs. The generalization of the well known SPP labelling algorithm for the multi- objective situation is studied in detail and

E MANUEL PAIX; E LUIS SANTOS

25

A Bio-Inspired Method for the Constrained Shortest Path Problem  

PubMed Central

The constrained shortest path (CSP) problem has been widely used in transportation optimization, crew scheduling, network routing and so on. It is an open issue since it is a NP-hard problem. In this paper, we propose an innovative method which is based on the internal mechanism of the adaptive amoeba algorithm. The proposed method is divided into two parts. In the first part, we employ the original amoeba algorithm to solve the shortest path problem in directed networks. In the second part, we combine the Physarum algorithm with a bio-inspired rule to deal with the CSP. Finally, by comparing the results with other method using an examples in DCLC problem, we demonstrate the accuracy of the proposed method.

Wang, Hongping; Lu, Xi; Wang, Qing

2014-01-01

26

Discrete Dynamic Shortest Path Problems in Transportation Applications: Complexity and Algorithms with Optimal Run Time  

Microsoft Academic Search

Abstract: This paper solves what appears to be a 30 years old problem dealing with the discovery of most efficient algorithms possible to compute all-to-one shortest paths in discrete dynamic,networks. This problem lies at the heart of efficient solution approaches to dynamic network models that arise in dynamic transportation systems, such as Intelligent Transportation Systems (ITS), applications. While the main

Ismail Chabini

1998-01-01

27

Probabilistic inference and ranking of gene regulatory pathways as a shortest-path problem  

PubMed Central

Background Since the advent of microarray technology, numerous methods have been devised to infer gene regulatory relationships from gene expression data. Many approaches that infer entire regulatory networks. This produces results that are rich in information and yet so complex that they are often of limited usefulness for researchers. One alternative unit of regulatory interactions is a linear path between genes. Linear paths are more comprehensible than networks and still contain important information. Such paths can be extracted from inferred regulatory networks or inferred directly. Since criteria for inferring networks generally differs from criteria for inferring paths, indirect and direct inference of paths may achieve different results. Results This paper explores a strategy to infer linear pathways by converting the path inference problem into a shortest-path problem. The edge weights used are the negative log-transformed probabilities of directness derived from the posterior joint distributions of pairwise mutual information between gene expression levels. Directness is inferred using the data processing inequality. The method was designed with two goals. One is to achieve better accuracy in path inference than extraction of paths from inferred networks. The other is to facilitate priorization of interactions for laboratory validation. A method is proposed for achieving this by ranking paths according to the joint probability of directness of each path's edges. The algorithm is evaluated using simulated expression data and is compared to extraction of shortest paths from networks inferred by two alternative methods, ARACNe and a minimum spanning tree algorithm. Conclusions Direct path inference appears to achieve accuracy competitive with that obtained by extracting paths from networks inferred by the other methods. Preliminary exploration of the use of joint edge probabilities to rank paths is largely inconclusive. Suggestions for a better framework for such comparisons are discussed.

2013-01-01

28

Time-Varying Shortest Path Problems with Perishable Product and Constraints  

Microsoft Academic Search

This paper develops a new version of time-varying shortest path problem. Let G = (V, E) be a directed graph. A set of perishable products will be transferred by vehicles from source s to destination d. Each arc eepsiE has four parameters: transit time b(e, n2, u), transit cost c(e, n2, u), vehicle cost S(e, n2, u, t) and vehicle

Hou. Wenting; Cai Xiaoqiang

2007-01-01

29

The d-edge shortest-path problem for a Monge graph  

SciTech Connect

A complete edge-weighted directed graph on vertices 1,2,...,n that assigns cost c(i,j) to the edge (i,j) is called Monge if its edge costs form a Monge array, i.e., for all i < k and j < l, c[i, j]+c[k,l]{le} < c[i,l]+c[k,j]. One reason Monge graphs are interesting is that shortest paths can be computed quite quickly in such graphs. In particular, Wilber showed that the shortest path from vertex 1 to vertex n of a Monge graph can be computed in O(n) time, and Aggarwal, Klawe, Moran, Shor, and Wilber showed that the shortest d-edge 1-to-n path (i.e., the shortest path among all 1-to-n paths with exactly d edges) can be computed in O(dn) time. This paper`s contribution is a new algorithm for the latter problem. Assuming 0 {le} c[i,j] {le} U and c[i,j + 1] + c[i + 1,j] {minus} c[i,j] {minus} c[i + 1, j + 1] {ge} L > 0 for all i and j, our algorithm runs in O(n(1 + 1g(U/L))) time. Thus, when d {much_gt} 1 + 1g(U/L), our algorithm represents a significant improvement over Aggarwal et al.`s O(dn)-time algorithm. We also present several applications of our algorithm; they include length-limited Huffman coding, finding the maximum-perimeter d-gon inscribed in a given convex n-gon, and a digital-signal-compression problem.

Bein, W.W. [New Mexico Univ., Albuquerque, NM (United States). Dept. of Computer Science; Larmore, L.L. [California Univ., Riverside, CA (United States). Dept. of Computer Science; Park, J.K. [Sandia National Labs.,Albuquerque, NM (United States)

1992-07-14

30

Randomized distributed shortest paths algorithms  

Microsoft Academic Search

This paper is concerned with distributed algorithm for finding shortest paths in an asynchronous communication network. For the problem of Breadth First Search, the best previously known algorithms required either &THgr;(V) time, or &THgr; (E + V · D) communication. We present new algorithm, which requires O(D1+?) time, and O(E1+?) messages, for any ? > 0. (Here, V is number

B. Awerbuch

1989-01-01

31

Tight analysis of the (1+1)-EA for the single source shortest path problem.  

PubMed

We conduct a rigorous analysis of the (1+1) evolutionary algorithm for the single source shortest path problem proposed by Scharnow, Tinnefeld, and Wegener (The analyses of evolutionary algorithms on sorting and shortest paths problems, 2004, Journal of Mathematical Modelling and Algorithms, 3(4):349-366). We prove that with high probability, the optimization time is O(n2 max{?, log(n)}), where ? is the smallest integer such that any vertex can be reached from the source via a shortest path having at most ? edges. This bound is tight. For all values of n and ? we provide a graph with edge weights such that, with high probability, the optimization time is of order ?(n2 max{?, log(n)}). To obtain such sharp bounds, we develop a new technique that overcomes the coupon collector behavior of previously used arguments. Also, we exhibit a simple Chernoff type inequality for sums of independent geometrically distributed random variables, and one for sequences of random variables that are not independent, but show a desired behavior independent of the outcomes of the previous random variables. We are optimistic that these tools find further applications in the analysis of evolutionary algorithms. PMID:21838552

Doerr, Benjamin; Happ, Edda; Klein, Christian

2011-01-01

32

Parallel shortest augmenting path algorithm for the assignment problem. Technical report  

SciTech Connect

We describe a parallel version of the shortest augmenting path algorithm for the assignment problem. While generating the initial dual solution and partial assignment in parallel does not require substantive changes in the sequential algorithm, using several augmenting paths in parallel does require a new dual variable recalculation method. The parallel algorithm was tested on a 14-processor Butterfly Plus computer, on problems with up to 900 million variables. The speedup obtained increases with problem size. The algorithm was also embedded into a parallel branch and bound procedure for the traveling salesman problem on a directed graph, which was tested on the Butterfly Plus on problems involving up to 7,500 cities. To our knowledge, these are the largest assignment problems and traveling salesman problems solved so far.

Balas, E.; Miller, D.; Pekny, J.; Toth, P.

1989-04-01

33

A comparison of two new exact algorithms for the robust shortest path problem  

Microsoft Academic Search

Real road networks can be modelled in mathematical terms as interval digraphs, where an interval of travel times (costs) is associated with each arc. Intervals represent uncer- tainty, typical of real situations, about exact travel times. A robust shortest path is a path which is not too far from the shortest one, whatever the exact values of arc costs are.

Roberto Montemanni; Luca Maria; Gambardella Alberto Donati

2004-01-01

34

Shortest path algorithms  

Microsoft Academic Search

Theshortest path problem is considered from a computational point of view. Eight algorithms which solve theshortest path tree problem on directed graphs are presented, together with the results of wide-ranging experimentation designed to compare their relative performances on different graph topologies. The focus of this paper is on the implementation of the different data structures used in the algorithms. A

Giorgio Gallo; Stefano Pallottino

1988-01-01

35

Exact and Approximate Truthful Mechanisms for the Shortest Paths Tree Problem  

Microsoft Academic Search

Let a communication network be modeled by an undirected graph G=(V,E) of n nodes and m edges, and assume that edges are controlled by selfish agents. In this paper we analyze the problem of designing a truthful\\u000a mechanism for computing one of the most popular structures in communication networks, i.e., the single-source shortest paths tree.\\u000a \\u000a \\u000a \\u000a More precisely, we will study

Luciano Gualà; Guido Proietti

2007-01-01

36

An Improved Ant Colony Algorithm for the Shortest Path Problem in Time-Dependent Networks  

NASA Astrophysics Data System (ADS)

Research of the shortest path problem in time-dependent networks has important practical value. An improved pheromone update strategy suitable for time-dependent networks was proposed. Under this strategy, the residual pheromone of each road can accurately reflect the change of weighted value of each road. An improved selection strategy between adjacent cities was used to compute the cities' transfer probabilities, as a result, the amount of calculation is greatly reduced. To avoid the algorithm converging to the local optimal solution, the ant colony algorithm was combined with genetic algorithm. In this way, the solutions after each traversal were used as the initial species to carry out single-point crossover. An improved ant colony algorithm for the shortest path problem in time-dependent networks based on these improved strategies was presented. The simulation results show that the improved algorithm has greater probability to get the global optimal solution, and the convergence rate of algorithm is better than traditional ant colony algorithm.

Chang, Qing; Liu, Yongqiang; Xiong, Huagang

37

A minimum resource neural network framework for solving multiconstraint shortest path problems.  

PubMed

Characterized by using minimum hard (structural) and soft (computational) resources, a novel parameter-free minimal resource neural network (MRNN) framework is proposed for solving a wide range of single-source shortest path (SP) problems for various graph types. The problems are the k-shortest time path problems with any combination of three constraints: time, hop, and label constraints, and the graphs can be directed, undirected, or bidirected with symmetric and/or asymmetric traversal time, which can be real and time dependent. Isomorphic to the graph where the SP is to be sought, the network is activated by generating autowave at source neuron and the autowave travels automatically along the paths with the speed of a hop in an iteration. Properties of the network are studied, algorithms are presented, and computation complexity is analyzed. The framework guarantees globally optimal solutions of a series of problems during the iteration process of the network, which provides insight into why even the SP is still too long to be satisfied. The network facilitates very large scale integrated circuit implementation and adapt to very large scale problems due to its massively parallel processing and minimum resource utilization. When implemented in a sequentially processing computer, experiments on synthetic graphs, road maps of cities of the USA, and vehicle routing with time windows indicate that the MRNN is especially efficient for large scale sparse graphs and even dense graphs with some constraints, e.g., the CPU time taken and the iteration number used for the road maps of cities of the USA is even less than  ? 2% and 0.5% that of the Dijkstra's algorithm. PMID:25050952

Zhang, Junying; Zhao, Xiaoxue; He, Xiaotao

2014-08-01

38

Finding the k Shortest Paths  

Microsoft Academic Search

We describe algorithms for finding the k shortest paths connectinga given pair of vertices in a digraph (allowing cycles). Our algorithmsoutput an implicit representation of the paths as an unordered setin time O(m + n log n + k). The paths can be output in order bylength in total time O(m + n log n + k log k). We

David Eppstein

1994-01-01

39

Shortest paths on a polyhedron  

Microsoft Academic Search

We present an algorithm for determining the shortest path between a source point and any destination point along the surface of a polyhedron (need not be convex). Our algorithm uses a new approach which deviates from the conventional “continuous Dijkstra” technique. It takes &Ogr;(n2) time and ⊖(n) space to determine the shortest path and to compute the inward layout which

Jindong Chen; Yijie Han

1990-01-01

40

Shortest Paths in Euclidean Graphs  

Microsoft Academic Search

We analyze a simple method for finding shortest paths inEuclidean graphs (where vertices are points in a Euclidean space and edge weights are Euclidean distances between points). For many graph\\u000a models, the average running time of the algorithm to find the shortest path between a specified pair of vertices in a graph\\u000a withV vertices andE edges is shown to beO(V)

Robert Sedgewick; Jeffrey Scott Vitter

1986-01-01

41

Genetic algorithms with elitism-based immigrants for dynamic shortest path problem in mobile ad hoc networks  

Microsoft Academic Search

In recent years, the static shortest path (SP) problem has been well addressed using intelligent optimization techniques, e.g., artificial neural networks (ANNs), genetic algorithms (GAs), particle swarm optimization (PSO), etc. However, with the advancement in wireless communications, more and more mobile wireless networks appear, e.g., mobile ad hoc network (MANET), wireless sensor network (WSN), etc. One of the most important

Hui Cheng; Shengxiang Yang

2009-01-01

42

Genetic Algorithms With Immigrants and Memory Schemes for Dynamic Shortest Path Routing Problems in Mobile Ad Hoc Networks  

Microsoft Academic Search

In recent years, the static shortest path (SP) problem has been well addressed using intelligent optimization techniques, e.g., artificial neural networks, genetic algorithms (GAs), particle swarm optimization, etc. However, with the advancement in wireless communications, more and more mobile wireless networks appear, e.g., mobile networks [mobile ad hoc networks (MANETs)], wireless sensor networks, etc. One of the most important characteristics

Shengxiang Yang; Hui Cheng; Fang Wang

2010-01-01

43

An Appraisal of Some Shortest Path Algorithms.  

National Technical Information Service (NTIS)

A critical review of the literature of shortest paths in networks that examines methods for determining (1) the shortest path between two specified nodes; (2) the shortest path between all pairs of nodes; (3) the second, third, etc., shortest path; (4) th...

S. E. Dreyfus

1967-01-01

44

On the Approximability of the Minimum Congestion Unsplittable Shortest Path Routing Problem  

Microsoft Academic Search

\\u000a We are given an undirected simple graph G = (V,E) with edge capacities ce e<\\/font\\u000a>Z+c_{e} \\\\epsilon \\\\mathcal{Z}+, e ? E, and a set K???V\\u000a 2 of commodities with demand values d\\u000a (s,t)\\u000a ??, (s, t) ? K. An unsplittable shortest path routing (USPR) of the commodities K is a set of flow paths ?(s,t), (s, t) ? K, such

Andreas Bley

2005-01-01

45

Approximating weighted shortest paths on polyhedral surfaces  

Microsoft Academic Search

IntroductionShortest path problems are among the fundamental problemsstudied in computational geometry. In this video,we consider the problem of computing a shortest costpath between two points s and t on a (possibly nonconvex)polyhedral surface P. The surface is composedof triangular regions (faces) in which each region has anassociated positive weight. The cost of travel througheach region is the distance traveled times

Mark Lanthier; Anil Maheshwari; Jörg-Rüdiger Sack

1997-01-01

46

A Distributed Context-Free Language Constrained Shortest Path Algorithm  

Microsoft Academic Search

Formal language constrained shortest path problems are concerned with finding shortest paths in labeled graphs. These labeled paths have the constraint that the concatenation of labels along a path constitute a valid string in some formal language Lambda over alphabet Sigma. These problems are well studied where the formal language is regular or context-free, and have been used in a

Charles B. Ward; Nathan M. Wiegand; Phillip G. Bradford

2008-01-01

47

Multi-population Genetic Algorithms with Immigrants Scheme for Dynamic Shortest Path Routing Problems in Mobile Ad Hoc Networks  

Microsoft Academic Search

\\u000a The static shortest path (SP) problem has been well addressed using intelligent optimization techniques, e.g., artificial\\u000a neural networks, genetic algorithms (GAs), particle swarm optimization, etc. However, with the advancement in wireless communications,\\u000a more and more mobile wireless networks appear, e.g., mobile ad hoc network (MANET), wireless mesh network, etc. One of the\\u000a most important characteristics in mobile wireless networks is

Hui Cheng; Shengxiang Yang

2010-01-01

48

Shortest paths algorithms: theory and experimental evaluation  

Microsoft Academic Search

We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove interesting theoretical results suggested by the experimental data. Our computational study is based on several natural problem classes which identify strengths and weaknesses of various algorithms. These problem classes and algorithm implementations form

Boris V. Cherkassky; Andrew V. Goldberg; Tomasz Radzikt

1994-01-01

49

Distributed computation on graphs: shortest path algorithms  

Microsoft Academic Search

We use the paradigm of diffusing computation, introduced by Dijkstra and Scholten, to solve a class of graph problems. We present a detailed solution to the problem of computing shortest paths from a single vertex to all other vertices, in the presence of negative cycles.

K. Mani Chandy; Jayadev Misra

1982-01-01

50

A Simpler Algorithm for the All Pairs Shortest Path Problem with O(n 2logn) Expected Time  

NASA Astrophysics Data System (ADS)

The best known expected time for the all pairs shortest path problem on a directed graph with non-negative edge costs is O(n 2logn) by Moffat and Takaoka. Let the solution set be the set of vertices to which the given algorithm has established shortest paths. The Moffat-Takaoka algorithm maintains complexities before and after the critical point in balance, which is the moment when the size of the solution set is n - n/logn. In this paper, we remove the concept of critical point and the data structure, called a batch list, whereby we make the algorithm simpler and seamless, resulting in a simpler analysis and speed-up.

Takaoka, Tadao; Hashim, Mashitoh

51

Large margin shortest path routing  

Microsoft Academic Search

A new discriminative approach to routing inspired by the large margin criterion serving as a basis for support vector machines\\u000a is presented. The proposed formulation uses the benefit of the dualization convex program, and it is possible for standard\\u000a solvers to learn the weighting metrics of the shortest path routing. In order to demonstrate this and due to its simplicity,

Yadamsuren Lutbat; Rentsen Enkhbat; Won-Joo Hwang

52

A temporal ant colony optimization approach to the shortest path problem in dynamic scale-free networks  

NASA Astrophysics Data System (ADS)

A large number of networks in the real world have a scale-free structure, and the parameters of the networks change stochastically with time. Searching for the shortest paths in a scale-free dynamic and stochastic network is not only necessary for the estimation of the statistical characteristics such as the average shortest path length of the network, but also challenges the traditional concepts related to the “shortest path” of a network and the design of path searching strategies. In this paper, the concept of shortest path is defined on the basis of a scale-free dynamic and stochastic network model, and a temporal ant colony optimization (TACO) algorithm is proposed for searching for the shortest paths in the network. The convergence and the setup for some important parameters of the TACO algorithm are discussed through theoretical analysis and computer simulations, validating the effectiveness of the proposed algorithm.

Yu, Feng; Li, Yanjun; Wu, Tie-Jun

2010-02-01

53

Stochastic shortest path with unlimited hops  

Microsoft Academic Search

We present new results for the Stochastic Shortest Path problem when an unlimited number of hops may be used. Nodes and links in the network may be congested or uncongested, and their states change over time. The goal is to adaptively choose the next node to visit such that the expected cost to the destination is minimized. Since the state

Ananya Das; Charles U. Martel

2009-01-01

54

Engineering Label-Constrained Shortest-Path Algorithms  

Microsoft Academic Search

We consider a generalization of the shortest-path problem: given an alphabet ?, a graph G whose edges are weighted and ?-labeled, and a regular language L ? ??, the L-constrained shortest-path problem consists of finding a shortest path p in G such that the concatenated labels along p form a word of L. This definition allows to model, e.g., many

Christopher L. Barrett; Keith Bisset; Martin Holzer; Goran Konjevod; Madhav V. Marathe; Dorothea Wagner

2008-01-01

55

On shortest paths in polyhedral spaces  

Microsoft Academic Search

We consider the problem of computing the shortest path between two points in two- or three-dimensional space bounded by polyhedral surfaces. In the 2-D case the problem is easily solved in time O(n2 log n).In the general 3-D case the problem is quite hard to solve, and is not even discrete; we present a doubly-exponential procedure for solving the discrete

Amir Schorr

1984-01-01

56

A fuzzy shortest path with the highest reliability  

NASA Astrophysics Data System (ADS)

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max-min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141-164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.

Keshavarz, Esmaile; Khorram, Esmaile

2009-08-01

57

Expected shortest paths in dynamic and stochastic traffic networks  

Microsoft Academic Search

The dynamic and stochastic shortest path problem (DSSPP) is defined as finding the expected shortest path in a traffic network where the link travel times are modeled as a continuous-time stochastic process. The objective of this paper is to examine the properties of the problem and to identify a technique that can be used to solve the DSSPP given information

Liping Fu; L. R. Rilett

1998-01-01

58

Vickrey Prices and Shortest Paths: What is an Edge Worth?  

Microsoft Academic Search

We solve a shortest path problem that is motivated by recent interest in pricing networks or other computational resources. Informally, how much is an edge in a network worth to a user who wants to send data between two nodes along a shortest path? If the network is a decentralized en- tity, such as the Internet, in which multiple self-interest

John Hershberger; Subhash Suri

2001-01-01

59

Another adaptive distributed shortest path algorithm  

Microsoft Academic Search

The authors give a distributed algorithm to compute shortest paths in a network with changing topology. The authors analyze its behavior. The proof of correctness is discussed. It does not suffer from the routing table looping behavior associated with the Ford-Bellman distributed shortest path algorithm although it uses truly distributed processing. Its time and message complexities are evaluated. Comparisons with

Pierre A. Humblet

1991-01-01

60

Shortest path and Schramm-Loewner Evolution  

PubMed Central

We numerically show that the statistical properties of the shortest path on critical percolation clusters are consistent with the ones predicted for Schramm-Loewner evolution (SLE) curves for ? = 1.04 ± 0.02. The shortest path results from a global optimization process. To identify it, one needs to explore an entire area. Establishing a relation with SLE permits to generate curves statistically equivalent to the shortest path from a Brownian motion. We numerically analyze the winding angle, the left passage probability, and the driving function of the shortest path and compare them to the distributions predicted for SLE curves with the same fractal dimension. The consistency with SLE opens the possibility of using a solid theoretical framework to describe the shortest path and it raises relevant questions regarding conformal invariance and domain Markov properties, which we also discuss.

Pose, N.; Schrenk, K. J.; Araujo, N. A. M.; Herrmann, H. J.

2014-01-01

61

k-Link Shortest Paths in Weighted Subdivisions  

Microsoft Academic Search

We study the shortest path problem in weighted polygonal subdivisions of the plane, with the additional constraint of an upper bound, k, on the number of links (segments) in the path. We prove structural properties of optimal paths and utilize these results to ob- tain approximation algorithms that yield a path having O(k) links and weighted length at most (1

Ovidiu Daescu; Joseph S. B. Mitchell; Simeon C. Ntafos; James D. Palmer; Chee-keng Yap

2005-01-01

62

Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations  

Microsoft Academic Search

We consider the problem of routing vehicles stationed at a central facility (depot) to supply customers with known demands, in such a way as to minimize the total distance travelled. The problem is referred to as the vehicle routing problem (VRP) and is a generalization of the multiple travelling salesman problem that has many practical applications.

N. Christofides; A. Mingozzi; P. Toth

1981-01-01

63

Asymptotic Optimality of Shortest Path Routing.  

National Technical Information Service (NTIS)

Many communication networks use adaptive shortest path routing. By this the authors mean that each network link is periodically assigned a length that depends on its congestion level during the preceding period, and all traffic generated between length up...

E. M. Gafni D. P. Pertsekas

1983-01-01

64

Highway Hierarchies Hasten Exact Shortest Path Queries  

Microsoft Academic Search

\\u000a We present a new speedup technique for route planning that exploits the hierarchy inherent in real world road networks. Our\\u000a algorithm preprocesses the eight digit number of nodes needed for maps of the USA or Western Europe in a few hours using linear\\u000a space. Shortest (i.e. fastest) path queries then take around eight milliseconds to produce exact shortest paths. This

Peter Sanders; Dominik Schultes

2005-01-01

65

The Number of Shortest Paths in the  

Microsoft Academic Search

\\u000a We enumerate all of the shortest paths between any vertex v and the identity vertex in an (n, k)-star graph by enumerating the minimum factorizations of v in terms of the transpositions corresponding to edges in that graph. This result generalizes a previous one for the star\\u000a graph, and can be applied to obtain the number of the shortest paths

Eddie Cheng; Ke Qiu; Zhi Zhang Shen

2010-01-01

66

A Shortest Path Approach to the Multiple-Vehicle Routing Problem  

Microsoft Academic Search

Abstract We examine,a multiple-vehicle routing problem,that permits split pick-ups (mVRPSP). This problem,involves a fleet of trucks having identical capacity, multiple suppliers, and a single assembly plant. The fleet is responsible for moving parts from the suppliers to the assembly plant. The problem is to determine, for each truck, how many parts to pick up at each supplier to then transport

Yavuz A. Bozer

67

Identifying the Shortest Path in Large Networks using Boolean Satisfiability  

Microsoft Academic Search

Today, most routing problems are solved using Dijkstra's shortest path algorithm. Many efficient implementations of Dijkstra's algorithm exist and can handle large networks in short runtimes. Despite these advances, it is difficult to incorporate user-specific conditions on the solution when using Dijkstra's algorithm. Such conditions can include forcing the path to go through a specific node, forcing the path to

Fadi A. Aloul; Bashar Al Rawi

2006-01-01

68

Balancing minimum spanning and shortest path trees  

Microsoft Academic Search

This paper give a simple linear-time algorithm that, given a weighted\\u000adigraph, finds a spanning tree that simultaneously approximates a shortest-path\\u000atree and a minimum spanning tree. The algorithm provides a continuous\\u000atrade-off: given the two trees and epsilon > 0, the algorithm returns a\\u000aspanning tree in which the distance between any vertex and the root of the\\u000ashortest-path

Samir Khuller; Balaji Raghavacharit; Neal E. Young

1993-01-01

69

Visibility graphs and obstacle-avoiding shortest paths  

Microsoft Academic Search

Summary Two closely related problems in Computational Geometry are determining visibility graphs and shortest paths in a two- or three-dimensional environment containing obstacles. Applications are within Computer Graphics and Robotics. We give a survey on recent research done on efficient algorithms for these problems.

H. Alt; E. Welzl

1988-01-01

70

Computing shortest paths with comparisons and additions  

Microsoft Academic Search

We present an undirected all-pairs shortest paths (APSP) algorithm which runs on a pointer machine in time O(mn?(m,n)) while making O(mnlog ?(m, n)) comparisons and additions, where m and n are the number of edges and vertices, respectively, and ?(m, n) is Tarjan's inverse-Ackermann function. This improves upon all previous comparison & addition-based APSP algorithms when the graph is sparse,

Seth Pettie; Vijaya Ramachandran

2002-01-01

71

A Shortest Path Algorithm with Constraints in Networks  

Microsoft Academic Search

\\u000a The paper deals with the shortest path problem with Constraints, and it is NP-complete problem. The problem is formulated\\u000a as an optimization model. To solve this model Lagrangean relaxation algorithm is adopted. For the solution of the dual problem\\u000a a subgradient method is used. The general algorithm steps for our problem are presented, and a numerical example on communication\\u000a network

Fanguo He; Kuobin Dai

72

Shortest paths of Bounded Curvature in the Plane  

Microsoft Academic Search

Given two oriented points in the plane, we determine and compute the shortest paths of bounded curvature joigning them. This problem has been solved recently, by Dubins in the no-cusp case, and by Reeds and Shepp otherwise. We propose a new solution based on the minimum principle of Pontryagin. Our approach simplifies the proofs and makes clear the global or

Jean-daniel Boissonnat; André Cérézo; Juliette Leblond

1991-01-01

73

Efficient Algorithms for Shortest Paths in Sparse Networks  

Microsoft Academic Search

Algorithms for finding shortest paths are presented which are faster than algorithms previously known on networks which are relatively sparse in arcs. Known results which the results of this paper extend are surveyed briefly and analyzed. A new implementation for priority queues is employed, and a class of “arc set partition” algorithms is introduced. For the single source problem on

Donald B. Johnson

1977-01-01

74

Optimal capacity allocation for load balanced shortest path routing  

Microsoft Academic Search

In this paper we first describe the load balanced shortest path routing (LB-SPR) protocol. Then, we present the linear program for the optimal capacity allocation, to minimize the resource consumption when LB-SPR is applied in the network. We show that when the load balancing is applied, the capacity allocation problem can be expressed only in terms of the total traffic

Marija Antic; Aleksandra Smiljanic

2009-01-01

75

A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem  

Microsoft Academic Search

A general procedure is presented for computing the best, 2nd best,..., Kth best solutions to a given discrete optimization problem. If the number of computational steps required to find an optimal solution to a problem with n(0, 1) variables is c(n), then the amount of computation required to obtain the if best solutions is O(Knc<\\/sub>(n)). The procedure specializes to published

Eugene L. Lawler

1972-01-01

76

A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths  

Microsoft Academic Search

We address the problem of finding a polynomial-time approximation scheme for shortest bounded-curvature paths in the presence\\u000a of obstacles. Given an arbitrary environment E\\\\mathcal{E} consisting of polygonal obstacles, two feasible configurations, a length ?, and an approximation factor ?, our algorithm either (i) verifies that every feasible bounded-curvature path joining the two configurations is longer than\\u000a ? or (ii) constructs

Jonathan Backer; David Kirkpatrick

2008-01-01

77

A New Necessary Condition for Shortest Path Routing  

Microsoft Academic Search

In shortest path routing, traffic is routed along shortest paths defined by link weights. However, not all path systems are feasible in that they can be realized in this way. This is something which needs to be taken into account when searching for a set of paths that minimize capacity consumption. In this paper, we discuss a new necessary condition

Mats Petter Pettersson; Krzysztof Kuchcinski

2007-01-01

78

Undirected single-source shortest paths with positive integer weights in linear time  

Microsoft Academic Search

The single-source shortest paths problem (SSSP) is one of the classic problems in algorithmic graph theory: given a positively weighted graph G with a source vertex s, find the shortest path from s to all other vertices in the graph.Since 1959, all theoretical developments in SSSP for general directed and undirected graphs have been based on Dijkstra's algorithm, visiting the

Mikkel Thorup

1999-01-01

79

Shortest paths synthesis for a car-like robot  

Microsoft Academic Search

This paper deals with the complete characterization of the shortest paths for a car-like robot. Previous works have shown that the search for a shortest path may be limited to a simple family of trajectories. Our work completes this study by providing a way to select inside this family an optimal path to link any two configurations. We combine the

P. Soueres; J.-P. Laumond

1996-01-01

80

Shortest path ray tracing with sparse graphs  

SciTech Connect

A technique for improving the efficiency of shortest path ray tracing (SPR) is presented. The authors analyze situations where SPR fails and provide quantitative measures to assess the performance of SPR ray tracing with varying numbers of nodes. Their improvements include perturbing the ray at interfaces according to Snell's Law, and a method to find correct rays efficiently in regions of low velocity contract. This approach allows the investigator to use fewer nodes in the calculation, thereby increasing the computational efficiency. In two-dimensional (2-D) cross-borehole experiments they find that with their improvements, they need only use 2/3 as many nodes, saving up to 60 percent in time. Savings should be even greater in three dimensions. These improvements make SPR more attractive for tomographic applications in three dimensions.

Fischer, R.; Lees, J.M. (Yale Univ., New Haven, CT (United States). Dept. of Geology and Geophysics)

1993-07-01

81

Neural networks for shortest path computation and routing in computer networks  

Microsoft Academic Search

The application of neural networks to the optimum routing problem in packet-switched computer networks, where the goal is to minimize the network-wide average time delay, is addressed. Under appropriate assumptions, the optimum routing algorithm relies heavily on shortest path computations that have to be carried out in real time. For this purpose an efficient neural network shortest path algorithm that

Mustafa K. Mehmet Ali; Faouzi Kamoun

1993-01-01

82

Shortcut in the Decomposition Algorithm for Shortest Paths in a Network  

Microsoft Academic Search

The problem considered is that of finding the shortest path between the two nodes of every pair in a large n-node network. A decomposition algorithm is proposed for use when the number of arcs is less than n(n - 1). The network is first decomposed into several overlapping subnetworks. Next, with each subnetwork treated separately, conditional shortest paths are obtained

T. C. Hu; W. T. Torres

1969-01-01

83

DT-MRI fiber tracking: a shortest paths approach.  

PubMed

We derive a new fiber tracking algorithm for DT-MRI that parts with the locally "greedy" paradigm intrinsic to conventional tracking algorithms. We demonstrate the ability to precisely reconstruct a diverse range of fiber trajectories in authentic and computer-generated DT-MRI data, for which well-known conventional tracking algorithms are shown to fail. Our approach is to pose fiber tracking as a problem in computing shortest paths in a weighted digraph. Voxels serve as vertices, and edges are included between neighboring voxels. We assign probabilities (weights) to edges using a Bayesian framework. Higher probabilities are assigned to edges that are aligned with fiber trajectories in their close proximity. We compute optimal paths of maximum probability using computationally scalable shortest path algorithms. The salient features of our approach are: global optimality--unlike conventional tracking algorithms, local errors do not accumulate and one "wrong-turn" does not spell disaster; a target point is specified a priori; precise reconstruction is demonstrated for extremely low signal-to-noise ratio; impartiality to which of two endpoints is used as a seed; and, faster computation times than conventional all-paths tracking. We can use our new tracking algorithm in either a single-path tracking mode (deterministic tracking) or an all-paths tracking mode (probabilistic tracking). PMID:18815098

Zalesky, Andrew

2008-10-01

84

Witnesses for Boolean Matrix Multiplication and for Shortest Paths  

Microsoft Academic Search

The subcubic methods to compute the shortest distances between all pairs of vertices also do not provide for witnesses; namely they compute the shortest distances but do not generate information for computing quickly the paths themselves. A witness for a shortest path from vi to vj is an index k such that vk is the rst vertex on such a

Noga Alon; Zvi Galilt; Oded Margalit; Moni Naor

1992-01-01

85

Computing the shortest path: A search meets graph theory  

Microsoft Academic Search

We propose shortest path algorithms that use A* search in combination with a new graph-theoretic lower-bounding technique based on landmarks and the triangle inequality. Our algorithms compute optimal shortest paths and work on any directed graph. We give experimental results showing that the most efficient of our new algorithms outperforms previous algorithms, in particular A* search with Euclidean bounds, by

Andrew V. Goldberg; Chris Harrelson

2005-01-01

86

A distributed, loop-free, shortest-path routing algorithm  

Microsoft Academic Search

A new distributed algorithm for the dynamic computation of the shortest paths in a computer network is presented, validated, and analyzed. According to this algorithm, each node maintains the lengths of the shortest path to each network destination and a feasibility vector. Update messages from a node are sent only to its neighbors; each such message contains one or more

1988-01-01

87

Fast and accurate estimation of shortest paths in large graphs  

Microsoft Academic Search

Computing shortest paths between two given nodes is a fundamental operation over graphs, but known to be nontrivial over large disk-resident instances of graph data. While a number of techniques exist for answering reachability queries and approximating node distances efficiently, determining actual shortest paths (i.e. the sequence of nodes involved) is often neglected. However, in applications arising in massive online

Andrey Gubichev; Srikanta J. Bedathur; Stephan Seufert; Gerhard Weikum

2010-01-01

88

Shortest Path First with Emergency Exits  

Microsoft Academic Search

Under heavy and dynamic traffic, the SPF routing algorithm often suffers from wild oscilla- tion and severe congestion, and results in degradation of the network performance. In this paper, we present a new routing algorithm (SPF-EE) which attempts to eliminate the problems associated with the SPF algo- rithm by providing alternate paths as emergency exits. With the SPF-EE algorithm, traffic

Zheng Wang; Jon Crowcroft

1990-01-01

89

All Pairs Shortest Paths for Graphs with Small Integer Length Edges  

Microsoft Academic Search

The authors have solved the all pairs shortest distances (APSD) problem for graphs with integer edge lengths. Our algorithm is subcubic for edge lengths of small (?M) absolute value. In this paper we show how to transform these algorithms to solve the all pairs shortest paths (APSP), in the same time complexity, up to a polylogarithmic factor. Forn=|V| the number

Zvi Galil; Oded Margalit

1997-01-01

90

Corridor location: the multi-gateway shortest path model  

NASA Astrophysics Data System (ADS)

The problem of corridor location can be found in a number of fields including power transmission, highways, and pipelines. It involves the placement of a corridor or rights-of-way that traverses a landscape starting at an origin and ending at a destination. Since most systems are subject to environmental review, it is important to generate competitive, but different alternatives. This paper addresses the problem of generating efficient, spatially different alternatives to the corridor location problem. We discuss the weaknesses in current models and propose a new approach which is designed to overcome many of these problems. We present an application of this model to a real landscape and compare the results to past work. Overall, the new model called the multi-gateway shortest path problem can generate a wide variety of efficient alignments, which eclipse what could be generated by past work.

Scaparra, Maria P.; Church, Richard L.; Medrano, F. Antonio

2014-03-01

91

ON THE ACCELERATION OF SHORTEST PATH CALCULATIONS IN TRANSPORTATION NETWORKS  

SciTech Connect

Shortest path algorithms are a key element of many graph problems. They are used in such applications as online direction finding and navigation, as well as modeling of traffic for large scale simulations of major metropolitan areas. As the shortest path algorithms are an execution bottleneck, it is beneficial to move their execution to parallel hardware such as Field-Programmable Gate Arrays (FPGAs). Hardware implementation is accomplished through the use of a small A core replicated on the order of 20 times on an FPGA device. The objective is to maximize the use of on-board random-access memory bandwidth through the use of multi-threaded latency tolerance. Each shortest path core is responsible for one shortest path calculation, and when it is finished it outputs its result and requests the next source from a queue. One of the innovations of this approach is the use of a small bubble sort core to produce the extract-min function. While bubble sort is not usually considered an appropriate algorithm for any non-trivial usage, it is appropriate in this case as it can produce a single minimum out of the list in O(n) cycles, whwere n is the number of elements in the vertext list. The cost of this min operation does not impact the running time of the architecture, because the queue depth for fetching the next set of edges from memory is roughly equivalent to the number of cores in the system. Additionally, this work provides a collection of simulation results that model the behavior of the node queue in hardware. The results show that a hardware queue, implementing a small bubble-type minimum function, need only be on the order of 16 elements to provide both correct and optimal paths. Because the graph database size is measured in the hundreds of megabytes, the Cray SRAM memory is insufficient. In addition to the A* cores, they have developed a memory management system allowing round-robin servicing of the nodes as well as virtual memory managed over the Hypertransport bus. With support for a DRAM graph store with SRAM-based caching on the FPGA, the system provides a speedup of roughly 8.9x over the CPU-based implementation.

BAKER, ZACHARY K. [Los Alamos National Laboratory; GOKHALE, MAYA B. [Los Alamos National Laboratory

2007-01-08

92

Faster Parametric Shortest Path and Minimum Balance Algorithms  

Microsoft Academic Search

We use Fibonacci heaps to improve a parametric shortest path algorithm of Karp and Orlin, and we combine our algorithm and the method of Schneider and Schneider's minimum-balance algorithm to obtain a faster minimum-balance algorithm. For a graph with n vertices and m edges, our parametric shortest path algorithm and our minimum-balance algorithm both run in O(nm + n2 logn)

Neal E. Young; James B. Orlinz

1991-01-01

93

Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length  

Microsoft Academic Search

In this paper the shortest-path problem in networks in which the delay (or weight) of the edges changes with time according to arbitrary functions is considered. Algorithms for finding the shortest path and minimum delay under various waiting constraints are presented and the properties of the derived path are investigated. It is shown that if departure time from the source

Ariel Orda; Raphael Rom

1990-01-01

94

Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths  

Microsoft Academic Search

The fusion tree method is extended to develop a linear-time algorithm for the minimum spanning tree problem and an O(m +n log n\\/log log n) implementation of Dijkstra's shortest-path algorithm for a graph with n vertices and m edges. The shortest-path algorithm surpasses information-theoretic limitations. The extension of the fusion tree method involves the development of a new data structure,

Michael L. Fredman; Dan E. Willard

1990-01-01

95

Optimal shortest path queries in a simple polygon  

Microsoft Academic Search

Let P be a simple polygon with n sides. This paper shows how to preprocess the polygon so that, given two query points p and q inside P, the length of the shortest path inside the polygon from p to q can be found in time &Ogr;(log n). The path itself must be polygonal and can be extracted in additional

Leonidas J. Guibas; John Hershberger

1987-01-01

96

Shortest Paths to Obstacles for a Polygonal Dubins Car  

Microsoft Academic Search

In this paper, we characterize the time-optimal trajectories leading a Dubins car in collision with the obstacles in its workspace. Due to the constant velocity constraint characterizing the Dubins car model, these trajectories form a sufficient set of shortest paths between any robot configuration and the obstacles in the environment. Based on these paths, we define and give the algorithm

Paolo Robuffo Giordano; Marilena Vendittelli

2009-01-01

97

Approximate Shortest Paths Guided by a Small Index  

Microsoft Academic Search

Distance oracles and graph spanners are excerpts of a graph that allow to compute approximate shortest paths. Here, we consider the situation where it is possible to access the original graph in addition to the graph excerpt while computing paths. This allows for asymptotically much smaller excerpts than distance oracles or spanners. The quality of an algorithm in this setting

Jörg Derungs; Riko Jacob; Peter Widmayer

2007-01-01

98

Three Methods for Optimizing Single-Shortest Path Routing  

Microsoft Academic Search

Intra-domain routing in IP networks is based on the shortest path principle by assigning administrative weights (costs) to links. The resulting least-cost paths determine routes between pairs of routers. If several such equal-cost paths exist between a pair of routers, it may not be clear which of them is actually used to route traffic. This makes it difficult to predict

Mateusz Dzida; M. Zagozdzon; M. Zotkiewicz; M. P. Pettersson; M. Pioro; M. Duelli; M. Menth

2008-01-01

99

Shortest path based splitting line finding for touching cells  

NASA Astrophysics Data System (ADS)

A shortest path based algorithm is proposed in this paper to find splitting lines for touching cells. Firstly, an initial splitting line is obtained through the distance transform of a marker image and the watershed algorithm. Then, the initial splitting line is separated into different line segments if necessary, and the start and end points of these line segments act as the start and end points of shortest path. Finally, the shortest path algorithm is used to find the splitting line between the start and end points, and the final result of touching cells splitting can be formed by the contour of the touching cells and the splitting lines. Experimental results show that the proposed algorithm is efficient for different types of touching cells.

Bai, Xiangzhi; Sun, Changming; Wang, Peng; Zhou, Fugen

2013-10-01

100

Faster Shortest-Path Algorithms for Planar Graphs  

Microsoft Academic Search

Abstract: We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegativeedge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graphwith the source and sink on the same face.

Monika Rauch Henzinger; Philip N. Klein; Satish Rao; Sairam Subramanian

1997-01-01

101

Finding the K Shortest Loopless Paths in a Network  

Microsoft Academic Search

This paper presents an algorithm for finding the K loopless paths that have the shortest lengths from one node to another node in a network. The significance of the new algorithm is that its computational upper bound increases only linearly with the value of K. Consequently, in general, the new algorithm is extremely efficient as compared with the algorithms proposed

Jin Y. Yen

1971-01-01

102

Open Shortest Path First (OSPF) Routing Protocol Simulation  

Microsoft Academic Search

Open Shortest Path First (OSPF) is a dynamic, hierarchical routing protocol designed to support routing in TCP\\/IP networks. A simulation of the OSPF Election Protocol shows three results: (1) The Designated Router (DR) can be elected in constant time. (2) If a router has a limited number of input buffers, a competition for buffers between the Election and the Flooding

Deepinder P. Sidhu; Tayang Fu; Shukri Abdallah; Raj Nair; Rob Coltun

1993-01-01

103

Shortest Path Games: Computational Complexity of Solution Concepts  

Microsoft Academic Search

Shortest Path Games: Computational Complexity of Solution Concepts Frank Nebel Abstract: Over the last few years a series of papers has been published that analyse the computational complexity of solution concepts applied to different types of coalitional games, which are expressed by more or less concise representation languages. However, the coalitional games that have been analysed in a computational context

Frank Nebel

2010-01-01

104

Approximate Shortest Path Queries in Graphs Using Voronoi Duals  

Microsoft Academic Search

We propose an approximation method to answer shortest path queries in graphs, based on hierarchical random sampling and Voronoi duals. The lowest level of the hierarchy stores the initial graph. At each higher level, we compute a simplification of the graph on the level below, by selecting a constant fraction of nodes. Edges are generated as the Voronoi dual within

Shinichi Honiden; Michael E. Houle; Christian Sommer; Martin Wolff

2009-01-01

105

Approximate Shortest Paths Guided by a Small Index  

Microsoft Academic Search

Distance oracles and graph spanners are excerpts of a graph that allow to compute approximate shortest paths. Here, we consider\\u000a the situation where it is possible to access the original graph in addition to the graph excerpt while computing paths. This\\u000a allows for asymptotically much smaller excerpts than distance oracles or spanners. The quality of an algorithm in this setting

Jörg Derungs; Riko Jacob; Peter Widmayer

2010-01-01

106

Shortest-Path Kernels on Graphs  

Microsoft Academic Search

Data mining algorithms are facing the challenge to deal with an increasing number of complex objects. For graph data, a whole toolbox of data mining algorithms becomes available by defining a kernel function on instances of graphs. Graph kernels based on walks, subtrees and cycles in graphs have been proposed so far. As a general problem, these kernels are either

Karsten M. Borgwardt; Hans-peter Kriegel

2005-01-01

107

All pairs shortest paths using bridging sets and rectangular matrix multiplication  

Microsoft Academic Search

We present two new algorithms for solving the All Pairs Shortest Paths (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms.The first algorithm solves the APSP problem for weighted directed graphs in which the edge weights are integers of small absolute value in Õ(n2+?) time, where ? satisfies the equation ?(1, ?, 1) = 1 +

Uri Zwick

2002-01-01

108

The stable paths problem and interdomain routing  

Microsoft Academic Search

Dynamic routing protocols such as RIP and OSPF essentially implement distributed algorithms for solving the shortest paths problem. The border gateway protocol (BGP) is currently the only interdomain routing protocol deployed in the Internet. BGP does not solve a shortest paths problem since any interdomain protocol is required to allow policy-based metrics to override distance-based metrics and enable autonomous systems

Timothy G. Griffin; F. Bruce Shepherd; Gordon T. Wilfong

2002-01-01

109

Ant colony algorithm for the shortest loop design problem  

Microsoft Academic Search

In this paper, a new algorithm for solving the shortest loop design problem is presented. The shortest loop design problem is to find the shortest loop for an automated guided vehicle covering at least one edge of each department of a block layout. In this paper, first it is shown that this problem can be represented as a graph model.

Kourosh Eshghi; Morteza Kazemi

2006-01-01

110

Optimal Shortest Path Queries in a Simple Polygon  

Microsoft Academic Search

Abstract Let P be a simple polygon with n sides. This paper shows how to preprocess,the polygon so that, given two query points p and q inside P, the length of the shortest,path,inside the polygon($#$to q can be found,in time,O(Iogn). The path,itself must,be polygonal and can be extracted,in additional,time proportional,to the number,of turns,it makes.,The preprocessing consists of triangulation,plus a linear

Leonidas J. Guibas; John Hershberger

1989-01-01

111

Approximation Algorithms for Shortest Path Motion Planning (Extended Abstract)  

Microsoft Academic Search

This paper gives approximation algorithms for solvingthe following motion planning problem: Given aset of polyhedral obstacles and points s and t, find ashortest path from s to t that avoids the obstacles.The paths found by the algorithms are piecewise linear,and the length of a path is the sum of the lengthsof the line segments making up the path. Approximationalgorithms will

Kenneth L. Clarkson

1987-01-01

112

A Study on Shortest Path Routing Algorithm on Dataflow Parallel Reconfigurable Processor DAPDNA2  

Microsoft Academic Search

In IP networks, we ordinally use OSPF(Open Shortest Path First) as a routing protocol. OSPF find the shortest path using Dijkstra's Shortest Path Algorithm. Dijkstra's Algorithm is suitable for program counter based CPU, however it is not scalable for the number of nodes in the networks since its computational complexity is O(n2). In this paper, We propose a parallel shortest

Sho SHIMIZU; Yutaka ARAKAWA; Naoaki YAMANAKA; Kosuke SHIBA

113

Transmission Scheduling for Sensor Network Lifetime Maximization: A Shortest Path Bandit Formulation  

Microsoft Academic Search

This paper addresses optimal sensor scheduling for maximizing network lifetime. We formulate this problem as a stochastic shortest-path multi-armed bandit problem. The optimal transmission scheduling policy is thus to choose the sensor with the largest Gittins index. Exploiting the underlying structure of the sensor scheduling problem, we derive a closed-form expression for the Gittins index. We show that choosing the

Yunxia Chen; Qing Zhao; Vikram Krishnamurthy; Dejan Djonin

2006-01-01

114

A Graph Search Heuristic for Shortest Distance Paths  

SciTech Connect

This paper presents a heuristic for guiding A* search for finding the shortest distance path between two vertices in a connected, undirected, and explicitly stored graph. The heuristic requires a small amount of data to be stored at each vertex. The heuristic has application to quickly detecting relationships between two vertices in a large information or knowledge network. We compare the performance of this heuristic with breadth-first search on graphs with various topological properties. The results show that one or more orders of magnitude improvement in the number of vertices expanded is possible for large graphs, including Poisson random graphs.

Chow, E

2005-03-24

115

Universal behavior of the shortest-path aggregation  

SciTech Connect

The shortest-path aggregation in a two-dimensional square lattice is studied numerically. We find universal behavior of the cluster formation when the released particles are weakly correlated, and a distinct universal behavior for clusters generated by a strongly correlated release. In particular, we find the fractal dimension {ital D}=1.20{plus minus}0.01 when the released particles are weakly correlated, while a one-dimensional object is obtained when the correlation is strong. We also find the anisotropic exponent {delta}=1.0 in the weak-correlation region.

Wang, X.R.; Wang, X.F. (School of Physics and Astronomy, University of Minnesota, Minneapolis, Minnesota 55455 (United States))

1992-01-15

116

A Decentralized Algorithm for Finding the Shortest Paths in Defense Communications Networks.  

National Technical Information Service (NTIS)

This paper presents a decentralized shortest path algorithm which finds the shortest distances between all pairs of nodes without requiring that any particular node have information about the complete topology of the network. The algorithm requires at mos...

J. Y. Yen

1979-01-01

117

Fast Algorithms for Solving Path Problems  

Microsoft Academic Search

Let G = (V, E) be a directed graph with a distinguished source vertex s. The single-source path expression problem is to find, for each vertex v, a regular expression P(s, v) which represents the set of all paths in G from s to v A solution to this problem can be used to solve shortest path problems, solve sparse

Robert Endre Tarjan

1981-01-01

118

Damage detection via shortest-path network sampling  

NASA Astrophysics Data System (ADS)

Large networked systems are constantly exposed to local damages and failures that can alter their functionality. The knowledge of the structure of these systems is, however, often derived through sampling strategies whose effectiveness at damage detection has not been thoroughly investigated so far. Here, we study the performance of shortest-path sampling for damage detection in large-scale networks. We define appropriate metrics to characterize the sampling process before and after the damage, providing statistical estimates for the status of nodes (damaged, not damaged). The proposed methodology is flexible and allows tuning the trade-off between the accuracy of the damage detection and the number of probes used to sample the network. We test and measure the efficiency of our approach considering both synthetic and real networks data. Remarkably, in all of the systems studied, the number of correctly identified damaged nodes exceeds the number of false positives, allowing us to uncover the damage precisely.

Ciulla, Fabio; Perra, Nicola; Baronchelli, Andrea; Vespignani, Alessandro

2014-05-01

119

A new approach to shortest paths on networks based on the quantum bosonic mechanism  

NASA Astrophysics Data System (ADS)

This paper presents quantum bosonic shortest path searching (QBSPS), a natural, practical and highly heuristic physical algorithm for reasoning about the recognition of network structure via quantum dynamics. QBSPS is based on an Anderson-like itinerant bosonic system in which a boson's Green function is used as a navigation pointer for one to accurately approach the terminals. QBSPS is demonstrated by rigorous mathematical and physical proofs and plenty of simulations, showing how it can be used as a greedy routing to seek the shortest path between different locations. In methodology, it is an interesting and new algorithm rooted in the quantum mechanism other than combinatorics. In practice, for the all-pairs shortest-path problem in a random scale-free network with N vertices, QBSPS runs in O(?(N) ln ln N) time. In application, we suggest that the corresponding experimental realizations are feasible by considering path searching in quantum optical communication networks; in this situation, the method performs a pure local search on networks without requiring the global structure that is necessary for current graph algorithms.

Jiang, Xin; Wang, Hailong; Tang, Shaoting; Ma, Lili; Zhang, Zhanli; Zheng, Zhiming

2011-01-01

120

SHORTEST PATHS FOR THE REEDS-SHEPP CAR: A WORKED OUT EXAMPLE OF THE USE OF GEOMETRIC TECHNIQUES IN NONLINEAR OPTIMAL CONTROL. 1  

Microsoft Academic Search

We illustrate the use of the techniques of modern geometric optimal control theory by studying the shortest paths for a model of a car that can move forwards and backwards. This problem was discussed in recent work by Reeds and Shepp who showed, by special methods, (a) that shortest path motion could always be achieved by means of trajectories of

J. Sussmann; Guoqing Tang

1991-01-01

121

Should QoS routing algorithms prefer shortest paths?  

Microsoft Academic Search

Multimedia traffic and real-time e-commerce applications can experience quality degradation in traditional networks such as the Internet. These difficulties can be overcome in networks which feature dynamically set up paths with bandwidth and delay guarantees. The problem of selecting such constrained paths is the task of quality of service (QoS) routing. This paper considers link-state routing, and the choice of

Karol Kowalik; Martin Collier

2003-01-01

122

Dynamic shortest path in stochastic traffic networks based on fluid neural network and Particle Swarm Optimization  

Microsoft Academic Search

The shortest path algorithm is critical for dynamic traffic assignment and for the realization of route guidance in intelligent transportation systems (ITS). In this paper, a hybrid Particle Swarm Optimization (PSO) algorithm combined fluid neural network (FNN) to search for the shortest path in stochastic traffic networks is introduced. The algorithm overcomes the weight coefficient symmetry restrictions of the traditional

Yanfang Deng; Hengqing Tong; Xiedong Zhang

2010-01-01

123

Using Edge-Valued Decision Diagrams for Symbolic Generation of Shortest Paths  

Microsoft Academic Search

We present a new method for the symbolic construction of shortest paths in reachability graphs. Our algorithm relies on a variant of edge{valued decision diagrams that supports ecien t xed{p oint it- erations for the joint computation of both the reachable states and their distance from the initial states. Once the distance function is known, a shortest path from an

Gianfranco Ciardo; Radu Siminiceanu

2002-01-01

124

Size and Weight of Shortest Path Trees with Exponential Link Weights  

Microsoft Academic Search

We derive the distribution of the number of links and the average weight for the shortest path tree (SPT) rooted at an arbitrary node to m uniformly chosen nodes in the complete graph of size N with i.i.d. exponential link weights. We rely on the fact that the full shortest path tree to all destinations (i.e., m = N ?

Remco Van Der Hofstad; Gerard Hooghiemstra; Piet Van Mieghem

2006-01-01

125

Gene Function Prediction with the Shortest Path in Functional Linkage Graph  

Microsoft Academic Search

This paper presents a new technique for gene function prediction with the shortest path in functional linkage graph. With existing protein-protein interaction data, complex data and gene expression data, a weighted functional linkage graph is inferred. By finding the shortest path in the functional linkage graph, the functions of unknown genes can be predicted with the functions of those that

Xing-Ming Zhao; Luonan Chen; Kazuyuki Aihara

2007-01-01

126

An Efficient Parallel Algorithm for Shortest Paths in Planar Layered Digraphs  

Microsoft Academic Search

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We present a first step in this direction by giving efficient parallel algorithms for shortest paths in planar

Sairam Subramanian; Roberto Tamassia; Jeffrey Scott Vitter

1995-01-01

127

Color texture classification using shortest paths in graphs.  

PubMed

Color textures are among the most important visual attributes in image analysis. This paper presents a novel method to analyze color textures by modeling a color image as a graph in two different and complementary manners (each color channel separately and the three color channels altogether) and by obtaining statistical moments from the shortest paths between specific vertices of this graph. Such an approach allows to create a set of feature vectors, which were extracted from VisTex, USPTex, and TC00013 color texture databases. The best classification results were 99.07%, 96.85%, and 91.54% (LDA with leave-one-out), 87.62%, 66.71%, and 88.06% (1NN with holdout), and 98.62%, 96.16%, and 91.34% (LDA with holdout) of success rate (percentage of samples correctly classified) for these three databases, respectively. These results prove that the proposed approach is a powerful tool for color texture analysis to be explored. PMID:24988594

de Mesquita Sa Junior, Jarbas Joaci; Cortez, Paulo Cesar; Backes, Andre Ricardo

2014-09-01

128

Critical analysis of hopfield's neural network model for TSP and its comparison with heuristic algorithm for shortest path computation  

Microsoft Academic Search

For shortest path computation, Travelling-Salesman problem is NP-complete and is among the intensively studied optimization problems. Hopfield and Tank's proposed neural network based approach, for solving TSP, is discussed. Since original Hopfield's model suffers from some limitations as the number of cities increase, some modifications are discussed for better performance. With the increase in the number of cities, the best

Farah Sarwar; Abdul Aziz Bhatti

2012-01-01

129

Fast estimation of diameter and shortest paths (without matrix multiplication)  

Microsoft Academic Search

In the recent past, there has been considerable progress in devising algorithms for the allpairsshortest paths problem running in time significantly smaller than the obvious time bound ofO(n3). Unfortunately, all the new algorithms are based on fast matrix multiplication algorithmsthat are notoriously impractical. Our work is motivated by the goal of devising purely combinatorialalgorithms that match these improved running times.

Donald Aingworth; Chandra Chekuri; Rajeev Motwani

1996-01-01

130

Identification of Colorectal Cancer Related Genes with mRMR and Shortest Path in Protein-Protein Interaction Network  

Microsoft Academic Search

One of the most important and challenging problems in biomedicine and genomics is how to identify the disease genes. In this study, we developed a computational method to identify colorectal cancer-related genes based on (i) the gene expression profiles, and (ii) the shortest path analysis of functional protein association networks. The former has been used to select differentially expressed genes

Bi-Qing Li; Tao Huang; Lei Liu; Yu-Dong Cai; Kuo-Chen Chou

2012-01-01

131

Texture recognition by the shortest path on 3D discrete gray-level surface  

NASA Astrophysics Data System (ADS)

In this paper, we apply geodesic paths (the shortest path which is an important object in the task of 3D shape analysis) to the description of natural textures. We first introduce an approach called propagation algorithm to estimate the shortest paths on discrete surfaces and then derive a set of texture features (LR, PLR, SDR, DIF and 1c) from them. The results of the experiments indicate that these features can reflect texture surface patterns in various aspects and are suitable for texture description.

Liao, Mengyang; Li, Xinliang; Qin, Jiamei; Wang, Sixian

1995-05-01

132

A sieve algorithm for the shortest lattice vector problem  

Microsoft Academic Search

We present a randomized 2^{O(n)} time algorithm to compute a shortest non-zero vector in an n-dimensional rational lattice. The best known time upper bound for this problem was 2^{O(n\\\\log n)} first given by Kannan [7] in 1983. We obtain several consequences of this algorithm for related problems on lattices and codes, including an improvement for polynomial time approximations to the

Miklós Ajtai; Ravi Kumar; D. Sivakumar

2001-01-01

133

Thinnest Path Problem.  

National Technical Information Service (NTIS)

We consider the thinnest path problem for secure communication in wireless ad hoc networks. For a given source and a destination, the thinnest path problem asks for a path from the source to the destination that results in the minimum number of nodes hear...

A. Swami J. Gao Q. Zhao

2013-01-01

134

Performance of multihop wireless networks: shortest path is not enough  

Microsoft Academic Search

Existing wireless ad hoc routing protocols typically find routes with the minimum hop-count. This paper presents experimental evidence from two wireless test-beds which shows that there are usually multiple minimum hop-count paths, many of which have poor throughput. As a result, minimum-hop-count routing often chooses routes that have significantly less capacity than the best paths that exist in the network.

Douglas S. J. De Couto; Daniel Aguayo; Benjamin A. Chambers; Robert Morris

2003-01-01

135

Finding Shortest Paths on Surfaces Using Level Sets Propagation  

Microsoft Academic Search

We present a new algorithm for determining minimal length paths between two regions on a three dimensional surface. The numerical implementation is based on finding equal geodesic distance contours from a given area. These contours are calculated as zero sets of a bivariate function designed to evolve so as to track the equal distance curves on the given surface. The

Ron Kimmel; Arnon Amir; Alfred M. Bruckstein

1995-01-01

136

Faster shortest-path algorithms for planar graphs  

Microsoft Academic Search

We give a linear-time algorithm for single-sourceshortest paths in planar graphs with nonnegative edgelengths.Our algorithm also yields a linear-time algorithmfor maximum flow in a planar graph with thesource and sink on the same face. The previous best algorithmsfor these problemsrequired\\\\Omega\\\\Gammanplog n) timewhere n is the number of nodes in the input graph.For the case where negative edge-lengths are allowed,we give

Philip N. Klein; Satish Rao; Monika Raucht; Sairam Subramanian

1994-01-01

137

The approach for shortest paths in fire succor based on component GIS technology  

NASA Astrophysics Data System (ADS)

Fire safety is an important issue for the national economy and people's living. Efficiency and exactness of fire department succor directly relate to safety of peoples' lives and property. Many disadvantages of the traditional fire system have been emerged in practical applications. The preparation of pumpers is guided by wireless communication or wire communication, so its real-time and accurate performances are much poorer. The information about the reported fire, such as the position, disaster and map, et al., for alarm and command was processed by persons, which slows the reaction speed and delays the combat opportunity. In order to solve these disadvantages, it has an important role to construct a modern fire command center based on high technology. The construction of modern fire command center can realize the modernization and automation of fire command and management. It will play a great role in protecting safety of peoples' lives and property. The center can enhance battle ability and can reduce the direct and indirect loss of fire damage at most. With the development of science technology, Geographic Information System (GIS) has becoming a new information industry for hardware production, software development, data collection, space analysis and counseling. With the popularization of computers and the development of GIS, GIS has gained increasing broad applications for its strong functionality. Network analysis is one of the most important functions of GIS, and the most elementary and pivotal issue of network analysis is the calculation of shortest paths. The shortest paths are mostly applied to some emergent systems such as 119 fire alarms. These systems mainly require that the computation time of the optimal path should be 1-3 seconds. And during traveling, the next running path of the vehicles should be calculated in time. So the implement of the shortest paths must have a high efficiency. In this paper, the component GIS technology was applied to collect and record the data information (such as, the situation of this disaster, map and road status et al) of the reported fire firstly. The ant colony optimization was used to calculate the shortest path of fire succor secondly. The optimization results were sent to the pumpers, which can let pumpers choose the shortest paths intelligently and come to fire position with least time. The programming method for shortest paths is proposed in section 3. There are three parts in this section. The elementary framework of the proposed programming method is presented in part one. The systematic framework of GIS component is described in part two. The ant colony optimization employed is presented in part three. In section 4, a simple application instance was presented to demonstrate the proposed programming method. There are three parts in this section. The distributed Web application based on component GIS was described in part one. The optimization results without traffic constraint were presented in part two. The optimization results with traffic constraint were presented in part three. The contributions of this paper can be summarized as follows. (1) It proposed an effective approach for shortest paths in fire succor based on component GIS technology. This proposed approach can achieve the real-time decisions of shortest paths for fire succor. (2) It applied the ant colony optimization to implement the shortest path decision. The traffic information was considered in the shortest path decision using ant colony optimization. The final application instance suggests that the proposed approach is feasible, correct and valid.

Han, Jie; Zhao, Yong; Dai, K. W.

2007-08-01

138

Weight of a link in a shortest path tree and the Dedekind Eta function  

Microsoft Academic Search

The weight of a randomly chosen link in the shortest path tree on the complete graph with exponential i.i.d. link weights is studied. The corresponding exact probability generating function and the asymptotic law are derived. As a remarkable coincidence, this asymptotic law is precisely the same as the distribution of the cost of one \\

Piet Van Mieghem

2010-01-01

139

Spatial interpolation of fine particulate matter concentrations using the shortest wind-field path distance.  

PubMed

Effective assessments of air-pollution exposure depend on the ability to accurately predict pollutant concentrations at unmonitored locations, which can be achieved through spatial interpolation. However, most interpolation approaches currently in use are based on the Euclidean distance, which cannot account for the complex nonlinear features displayed by air-pollution distributions in the wind-field. In this study, an interpolation method based on the shortest path distance is developed to characterize the impact of complex urban wind-field on the distribution of the particulate matter concentration. In this method, the wind-field is incorporated by first interpolating the observed wind-field from a meteorological-station network, then using this continuous wind-field to construct a cost surface based on Gaussian dispersion model and calculating the shortest wind-field path distances between locations, and finally replacing the Euclidean distances typically used in Inverse Distance Weighting (IDW) with the shortest wind-field path distances. This proposed methodology is used to generate daily and hourly estimation surfaces for the particulate matter concentration in the urban area of Beijing in May 2013. This study demonstrates that wind-fields can be incorporated into an interpolation framework using the shortest wind-field path distance, which leads to a remarkable improvement in both the prediction accuracy and the visual reproduction of the wind-flow effect, both of which are of great importance for the assessment of the effects of pollutants on human health. PMID:24798197

Li, Longxiang; Gong, Jianhua; Zhou, Jieping

2014-01-01

140

Comparison of k-shortest paths and maximum flow routing for network facility restoration  

Microsoft Academic Search

In the development of technologies for span failure restoration, a question arises about the restoration rerouting characteristics to be specified. In theory, maximal rerouting capacity is obtained with a maximum flow (Max Flow) criterion. However, rerouting that realizes the k-successively shortest link disjoint paths (KSP) may be faster, easier, and, in distributed implementation, more robust than a distributed counterpart for

D. Anthony Dunn; Wayne D. Grover; Mike H. MacGregor

1994-01-01

141

Transitive Functional Annotation by Shortest-path Analysis of Gene Expression Data  

Microsoft Academic Search

attribute to link genes of the same biological pathway. Based on large-scale yeast microarray expression data, we use the shortest-path analysis to identify transitive genes between two given genes from the same biological process. We find that not only functionally related genes with correlated expression profiles are identified but also those without. In the latter case, we compare our method

Xianghong Zhou; Ming-Chih J. Kao; Wing Hung Wong

2002-01-01

142

Topology and Shortest Path Length Evolution of The Internet Autonomous Systems Interconnectivity  

Microsoft Academic Search

Connection networks are observed in many areas of human knowledge. The characterization and topological studies of these networks may be performed through distribution of connectivity degrees, rank properties, shortest path length between nodes, adjacency matrix etc. This paper characterizes the Internet con- nections evolution over the last 10 years at the Autonomous Systems (AS) level analyzing the complete BGP data

N. ALVES Jr.; M. P. de ALBUQUERQUE; Xavier Sigaud; J. T. de ASSIS

143

Shortest Path Cost Distribution in Random Graphs with Positive Integer Edge Costs  

Microsoft Academic Search

The probability distribution of the shortest path cost from a source node to an arbitrary destination node is considered for a random network model consisting of a complete digraph with positive integer random edge costs. Edge costs are chosen according to a common probability distribution for each direction. For this model, the joint distribution of the number of nodes which

Scott K. Walley; Harry H. Tan; Audrey M. Viterbi

1993-01-01

144

NETWORK REPRESENTATION AND SHORTEST PATH REFLECTING THE RAMP ENTRY OR EXIT DIRECTION LIMITATION  

Microsoft Academic Search

There are some ramp entry or exit direction limitations on networks. This kind of limitation is represented by successive passage prohibition (SPP). It indicates that the vehicles cannot successively pass two links with SPP attributes. However, the shortest-path tree sometimes cannot be expressed with a simple tree when a network having this limitation is represented with single nodes. In such

Kazutaka TAKAO; Tohru HIGASHI; Koji YASUDA; Yasuo ASAKURA

145

Spatial Interpolation of Fine Particulate Matter Concentrations Using the Shortest Wind-Field Path Distance  

PubMed Central

Effective assessments of air-pollution exposure depend on the ability to accurately predict pollutant concentrations at unmonitored locations, which can be achieved through spatial interpolation. However, most interpolation approaches currently in use are based on the Euclidean distance, which cannot account for the complex nonlinear features displayed by air-pollution distributions in the wind-field. In this study, an interpolation method based on the shortest path distance is developed to characterize the impact of complex urban wind-field on the distribution of the particulate matter concentration. In this method, the wind-field is incorporated by first interpolating the observed wind-field from a meteorological-station network, then using this continuous wind-field to construct a cost surface based on Gaussian dispersion model and calculating the shortest wind-field path distances between locations, and finally replacing the Euclidean distances typically used in Inverse Distance Weighting (IDW) with the shortest wind-field path distances. This proposed methodology is used to generate daily and hourly estimation surfaces for the particulate matter concentration in the urban area of Beijing in May 2013. This study demonstrates that wind-fields can be incorporated into an interpolation framework using the shortest wind-field path distance, which leads to a remarkable improvement in both the prediction accuracy and the visual reproduction of the wind-flow effect, both of which are of great importance for the assessment of the effects of pollutants on human health.

Li, Longxiang; Gong, Jianhua; Zhou, Jieping

2014-01-01

146

Efficiently Answering Probability Threshold-Based Shortest Path Queries over Uncertain Graphs  

Microsoft Academic Search

\\u000a Efficiently processing shortest path (SP) queries over stochastic networks attracted a lot of research attention as such queries\\u000a are very popular in the emerging real world applications such as Intelligent Transportation Systems and communication networks\\u000a whose edge weights can be modeled as a random variable. Some pervious works aim at finding the most likely SP (the path with\\u000a largest probability

Ye Yuan; Lei Chen; Guoren Wang

2010-01-01

147

Fighting organized crimes: using shortest-path algorithms to identify associations in criminal networks  

Microsoft Academic Search

Effective and efficient link analysis techniques are needed to help law enforcement and intelligence agencies fight organized crimes such as narcotics violation, terrorism, and kidnapping. In this paper, we propose a link analysis technique that uses shortest-path algorithms, priority-first-search (PFS) and two-tree PFS, to identify the strongest association paths between entities in a criminal network. To evaluate effectiveness, we compared

Jennifer Jie Xu; Hsinchun Chen

2004-01-01

148

Bounded Incremental Single-Source Shortest-Paths  

Microsoft Academic Search

We consider the problem of maintaining the distances of all vertices of a directed graph from a specific vertex, its source. We show algorithms in the bounded incremental computation (BIC) model which handle the insertion or deletion of an arc (or a batch of arcs outgoing from a shared vertex) in O(kk + |?|log |?|) amortized time on Cyclic>0 graphs

Irit Katriel; Pascal Van Hentenryck

149

Pectoral muscle detection in mammograms based on polar coordinates and the shortest path.  

PubMed

The automatic detection and segmentation of the pectoral muscle in the medio-lateral oblique view of mammograms is essential for further analysis of breast anormalies. However, it is still a very difficult task since the sizes, shapes and intensity contrasts of pectoral muscles change greatly from image to image. In this paper, an algorithm based on the shortest path on a graph is proposed to automatically detect the pectoral muscle contour. To overcome the difficulties of searching for the path between a lateral and the top margins of the image, this is first transformed, using polar coordinates. In the transformed image, the muscle boundary in amongst the shortest paths between the top and the bottom rows. A comprehensive comparison with manually-drawn contours reveals the strength of the proposed method. PMID:21096253

Cardoso, Jaime S; Domingues, Ines; Amaral, Igor; Moreira, Ines; Passarinho, Pedro; Santa Comba, Joao; Correia, Ricardo; Cardoso, Maria J

2010-01-01

150

Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems  

NASA Astrophysics Data System (ADS)

We present an algorithm which returns a shortest path and related number of entanglements for a given configuration of a polymeric system in 2 or 3 dimensions. Rubinstein and Helfand, and later Everaers et al. introduced a concept to extract primitive paths for dense polymeric melts made of linear chains (a multiple disconnected multibead 'path'), where each primitive path is defined as a path connecting the (space-fixed) ends of a polymer under the constraint of non-interpenetration (excluded volume) between primitive paths of different chains, such that the multiple disconnected path fulfills a minimization criterion. The present algorithm uses geometrical operations and provides a—model independent—efficient approximate solution to this challenging problem. Primitive paths are treated as 'infinitely' thin (we further allow for finite thickness to model excluded volume), and tensionless lines rather than multibead chains, excluded volume is taken into account without a force law. The present implementation allows to construct a shortest multiple disconnected path (SP) for 2D systems (polymeric chain within spherical obstacles) and an optimal SP for 3D systems (collection of polymeric chains). The number of entanglements is then simply obtained from the SP as either the number of interior kinks, or from the average length of a line segment. Further, information about structure and potentially also the dynamics of entanglements is immediately available from the SP. We apply the method to study the 'concentration' dependence of the degree of entanglement in phantom chain systems. Program summaryTitle of program:Z Catalogue number:ADVG Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADVG Program obtainable from: CPC Program Library, Queen's University of Belfast, N. Ireland Computer for which the program is designed and others on which it has been tested: Silicon Graphics (Irix), Sun (Solaris), PC (Linux) Operating systems or monitors under which the program has been tested: UNIX, Linux Program language used: USANSI Fortran 77 and Fortran 90 Memory required to execute with typical data: 1 MByte No. of lines in distributed program, including test data, etc.: 10 660 No. of bytes in distributed program, including test data, etc.: 119 551 Distribution formet:tar.gz Nature of physical problem: The problem is to obtain primitive paths substantiating a shortest multiple disconnected path (SP) for a given polymer configuration (chains of particles, with or without additional single particles as obstacles for the 2D case). Primitive paths are here defined as in [M. Rubinstein, E. Helfand, J. Chem. Phys. 82 (1985) 2477; R. Everaers, S.K. Sukumaran, G.S. Grest, C. Svaneborg, A. Sivasubramanian, K. Kremer, Science 303 (2004) 823] as the shortest line (path) respecting 'topological' constraints (from neighboring polymers or point obstacles) between ends of polymers. There is a unique solution for the 2D case. For the 3D case it is unique if we construct a primitive path of a single chain embedded within fixed line obstacles [J.S.B. Mitchell, Geometric shortest paths and network optimization, in: J.-R. Sack, J. Urrutia (Eds.), Handbook of Computational Geometry, Elsevier, Amsterdam, 2000, pp. 633-701]. For a large 3D configuration made of several chains, short is meant to be the Euclidean shortest multiple disconnected path (SP) where primitive paths are constructed for all chains simultaneously. While the latter problem, in general, does not possess a unique solution, the algorithm must return a locally optimal solution, robust against minor displacements of the disconnected path and chain re-labeling. The problem is solved if the number of kinks (or entanglements Z), explicitly deduced from the SP, is quite insensitive to the exact conformation of the SP which allows to estimate Z with a small error. Efficient method of solution: Primitive paths are constructed from the given polymer configuration (a non-shortest multiple disconnected path, including obstacles, if present) by first replacing each polymer contour by a line wi

Kröger, Martin

2005-06-01

151

Soft-decision Decoding of Block Codes using the k Shortest Paths Algorithm  

Microsoft Academic Search

In this paper, we develop a soft-decision decoding algorithm for block codes using the k shortest paths algorithm. The performance of this algorithm is investigated and compared with other decoding schemes. The results show the proposed algorithm gives large gains over the generalised minimum distance (GMD) decoding algorithm and algebraic hard-decision decoding. Further, the proposed algorithm achieves near-MLD performance for

Ismail Shakeel; Alex Grant

2006-01-01

152

Prediction of Transitive Co-expressed Genes Function by Shortest-Path Algorithm  

Microsoft Academic Search

\\u000a The present paper predicted the function of unknow genes by analyzing the co-expression data of Arabidopsis thaliana from biological pathway based on the shortest-path algorithm. This paper proposed that transitive co-expression among genes\\u000a can be used as an important attribute to link genes of the same biological pathway. The genes from the same biological pathway\\u000a with similar functions are strongly

Huang JiFeng

153

F-TPR: fine two-phase IP routing scheme over shortest paths for hose model  

Microsoft Academic Search

This letter proposes an IP-based finely-distributed routing scheme based on two-phase routing (TPR) over shortest paths for the hose model. It is called the fine-TPR (F-TPR) scheme. Compared to the original TPR, F-TPR distributes traffic from a source node to intermediate nodes more finely, where the distribution ratio is determined for each source-destination pair. To determine an optimum set of

Eiji Oki; Ayako Iwaki

2009-01-01

154

Probability distribution of the shortest path on the percolation cluster, its backbone, and skeleton  

Microsoft Academic Search

We consider the mean distribution functions Phi(r\\\\|l), PhiB(r\\\\|l), and PhiS(r\\\\|l), giving the probability that two sites on the incipient percolation cluster, on its backbone and on its skeleton, respectively, connected by a shortest path of length l are separated by an Euclidean distance r. Following a scaling argument due to de Gennes for self-avoiding walks, we derive analytical expressions for

Markus Porto; Shlomo Havlin; H. Eduardo Roman; Armin Bunde

1998-01-01

155

Swapping a Failing Edge of a Single Source Shortest Paths Tree Is Good and Fast  

Microsoft Academic Search

  \\u000a \\u000a Abstract. Let G=(V,E) be a 2-edge connected, undirected and nonnegatively weighted graph, and let S(r) be a single source shortest paths tree (SPT) of G rooted at r ? V . Whenever an edge e in S(r) fails, we are interested in reconnecting the nodes now disconnected from the root by means of a single edge e' crossing the

Enrico Nardelli; Guido Proietti; Peter Widmayer

2003-01-01

156

Energy penalties for non-shortest paths in wireless sensor networks with link failures  

Microsoft Academic Search

ABSTRACT This paper addresses the additional energy consumption,in wire- less sensor networks where the communication,between the sensor nodes and the sink nodes does not always make,use of the shortest path, due to the presence of link failures. For simplicity, link fail- ures are assumed,to be stochastic and independent. The basis for the analysis is a planned topology, with multiple sinks

Geir Egeland; Paal E. Engelstad

2009-01-01

157

Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs  

Microsoft Academic Search

We present parallel algorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexity O. f.n\\/= pC I.n\\/ log n\\/ on the PRAM using p processors, where I.n\\/ is log n on the EREW PRAM, log logn on the CCRW PRAM, f.n\\/ is o.n3\\/. On the randomized CRCW PRAM we are able to achieve time complexity

Yijie Han; Victor Y. Pan; John H. Reif

1997-01-01

158

A New Closeness Metric for Social Networks Based on the k Shortest Paths  

Microsoft Academic Search

\\u000a We axiomatically develop a metric of personal connection between individuals in social networks, and construct an optimal\\u000a model to find the best weight of the metric. Our metric optimizes, in some strict-established sense, weighted average of the\\u000a k shortest paths so that it is able to distinguish the closeness between nodes more relevantly than traditional metrics. The\\u000a algorithms are implemented

Chun Shang; Yuexian Hou; Shuo Zhang; Zhaopeng Meng

2010-01-01

159

How to Swap a Failing Edge of a Single Source Shortest Paths Tree  

Microsoft Academic Search

In this paper we introduce the notion of best swap for a failing edge of a single source shortest paths tree (SPT) S(r) rooted in r in a weighted graph G =( V; E). Given an edge e 2 S(r), an edge e0 2 E nfeg is a swap edge if the swap tree Se=e0(r) obtained by swapping e with

Enrico Nardelli; Guido Proietti; Peter Widmayer

1999-01-01

160

Approximating Shortest Paths in Large-Scale Networks with an Application to Intelligent Transportation Systems  

Microsoft Academic Search

We propose a hierarchical algorithm for approximating shortest paths between all pairs of nodes in a large-scale network. The algorithm begins by extracting a high-level subnetwork of rela- tively long links (and their associated nodes) where routing decisions are most crucial. This high-level network partitions the shorter links and their nodes into a set of lower-level sub- networks. By fixing

Yu-li Chou; H. Edwin Romeijn; Robert L. Smith

1998-01-01

161

Scaling of average weighted shortest path and average receiving time on weighted hierarchical networks  

NASA Astrophysics Data System (ADS)

Recent work on the networks has focused on the weighted hierarchical networks that are significantly different from the un-weighted hierarchical networks. In this paper we study a family of weighted hierarchical networks which are recursively defined from an initial uncompleted graph, in which the weights of edges have been assigned to different values with certain scale. Firstly, we study analytically the average weighted shortest path (AWSP) on the weighted hierarchical networks. Using a recursive method, we determine explicitly the AWSP. The obtained rigorous solution shows that the networks grow unbounded but with the logarithm of the network size, while the weighted shortest paths stay bounded. Then, depending on a biased random walk, we research the mean first-passage time (MFPT) between a hub node and any peripheral node. Finally, we deduce the analytical expression of the average of MFPTs for a random walker originating from any node to first visit to a hub node, which is named as the average receiving time (ART). The obtained result shows that ART is bounded or grows sublinearly with the network order relating to the number of initial nodes and the weighted factor or grows quadratically with the iteration.

Sun, Yu; Dai, Meifeng; Xi, Lifeng

162

Identification of Lung-Cancer-Related Genes with the Shortest Path Approach in a Protein-Protein Interaction Network  

PubMed Central

Lung cancer is one of the leading causes of cancer mortality worldwide. The main types of lung cancer are small cell lung cancer (SCLC) and nonsmall cell lung cancer (NSCLC). In this work, a computational method was proposed for identifying lung-cancer-related genes with a shortest path approach in a protein-protein interaction (PPI) network. Based on the PPI data from STRING, a weighted PPI network was constructed. 54 NSCLC- and 84 SCLC-related genes were retrieved from associated KEGG pathways. Then the shortest paths between each pair of these 54 NSCLC genes and 84 SCLC genes were obtained with Dijkstra's algorithm. Finally, all the genes on the shortest paths were extracted, and 25 and 38 shortest genes with a permutation P value less than 0.05 for NSCLC and SCLC were selected for further analysis. Some of the shortest path genes have been reported to be related to lung cancer. Intriguingly, the candidate genes we identified from the PPI network contained more cancer genes than those identified from the gene expression profiles. Furthermore, these genes possessed more functional similarity with the known cancer genes than those identified from the gene expression profiles. This study proved the efficiency of the proposed method and showed promising results.

Li, Bi-Qing; You, Jin; Chen, Lei; Zhang, Jian; Zhang, Ning; Li, Hai-Peng; Huang, Tao; Kong, Xiang-Yin; Cai, Yu-Dong

2013-01-01

163

Optimal Network Structure for Packet Flow in Shortest-Path Routing Control Model  

NASA Astrophysics Data System (ADS)

A network structure is responsible for efficient communication through a computer network. In order to obtain a network structure suitable for optimal packet communication on the network, we introduce a cost function for the efficiency of packet communication. By means of numerical simulations, we find an optimized network structure by reconnecting links in the network so as to minimize the defined cost function by using a shortest-path routing control model for packet flow. It turns out that the obtained optimized networks have the small-world property but a different structure from Erdös and Rényi's random graph [P. Erdös and A. Rényi, Publ. Math. (Debrecen) 6 (1959), 290] nor the real Internet. In addition, the distribution of links in the obtained network is not homogeneous and hence different from that obtained by Guimerá} et al., who have also investigated an optimal network structure for packet communication without packet routing processes.

Yamaguchi, C.; Horiguchi, T.

164

The tomography of human mobility -- what do shortest-path trees reveal?  

NASA Astrophysics Data System (ADS)

Similar to illustrating the anatomy of organs using pictures of tissue slices taken at various depths, we construct shortest-path trees of different nodes to create a tomogram of large-scale mobility networks. This tomography allows us to measure global properties of the system conditioned on a reference location in the network to gain a fuller characterization of a node. Using this technqiue, we discovered a new symmetry that characterizes a large class of mobility networks. Furthermore, introducing the notion of tree similarity, we devised a new technique for clustering nodes with similar topological footprint, yielding a new, unique and efficient method for community identification in these networks and extracting their topological backbone. We applied these methods to a multi-scale human mobility network obtained from the dollar-bill-tracking site wheresgoerge.com and to the U.S. and world-wide air transportation network.

Grady, Daniel; Thiemann, Christian; Brockmann, Dirk

2010-03-01

165

Shortest path ray tracing in cell model with a second-level forward star  

NASA Astrophysics Data System (ADS)

The high-level forward star is routinely applied in seismic ray tracing using graph theory (sometimes referred to as the shortest path method) with a grid model. For a cell model, the forward star is often restricted to nodes at the same cell (i.e. first-level forward star). The performance of a cell model with second-level forward stars is found to be comparable in both computation time and accuracy to that of a doubly dense cell model with first-level forward stars. Moreover, the cell model with second-level forward stars has the advantage of halving the required computer storage. An optimization of the secondary node geometry leads to a further 20 per cent improvement in accuracy. Concepts derived from grid models for analytical error estimation are found to be less applicable to cell models. An empirical approach works better in the optimization of the secondary node geometry.

Mak, Sum; Koketsu, Kazuki

2011-09-01

166

Long Path Problems  

Microsoft Academic Search

We demonstrate the interesting, counter-intuitive result that simple paths to the global optimum can be so long that climbing the path is intractable. This means that a unimodal search space, which consists of a single hill and in which each point in the space is on a simple path to the global optimum, can be difficult for a hillclimber to

Jeffrey Horn; David E. Goldberg; Kalyanmoy Deb

1994-01-01

167

Identification of colorectal cancer related genes with mRMR and shortest path in protein-protein interaction network.  

PubMed

One of the most important and challenging problems in biomedicine and genomics is how to identify the disease genes. In this study, we developed a computational method to identify colorectal cancer-related genes based on (i) the gene expression profiles, and (ii) the shortest path analysis of functional protein association networks. The former has been used to select differentially expressed genes as disease genes for quite a long time, while the latter has been widely used to study the mechanism of diseases. With the existing protein-protein interaction data from STRING (Search Tool for the Retrieval of Interacting Genes), a weighted functional protein association network was constructed. By means of the mRMR (Maximum Relevance Minimum Redundancy) approach, six genes were identified that can distinguish the colorectal tumors and normal adjacent colonic tissues from their gene expression profiles. Meanwhile, according to the shortest path approach, we further found an additional 35 genes, of which some have been reported to be relevant to colorectal cancer and some are very likely to be relevant to it. Interestingly, the genes we identified from both the gene expression profiles and the functional protein association network have more cancer genes than the genes identified from the gene expression profiles alone. Besides, these genes also had greater functional similarity with the reported colorectal cancer genes than the genes identified from the gene expression profiles alone. All these indicate that our method as presented in this paper is quite promising. The method may become a useful tool, or at least plays a complementary role to the existing method, for identifying colorectal cancer genes. It has not escaped our notice that the method can be applied to identify the genes of other diseases as well. PMID:22496748

Li, Bi-Qing; Huang, Tao; Liu, Lei; Cai, Yu-Dong; Chou, Kuo-Chen

2012-01-01

168

Detection of Changes in Transitive Associations by Shortest-path Analysis of Protein Interaction Networks Integrated with Gene Expression Profiles  

Microsoft Academic Search

Shortest-path (SP) clustering can detect transitive associations in co-expression networks. In this work, we show that it can detect changes of transitive associations caused by perturbations in a protein interaction network (PIN). Specifically, we compare SPs between genes under perturbation and in a reference state. The PIN under perturbation can be obtained through integration with gene expression profiles, using either

Hong Qin; Li Yang

2008-01-01

169

Identification of Thyroid Carcinoma Related Genes with mRMR and Shortest Path Approaches.  

PubMed

Thyroid cancer is a malignant neoplasm originated from thyroid cells. It can be classified into papillary carcinomas (PTCs) and anaplastic carcinomas (ATCs). Although ATCs are in an very aggressive status and cause more death than PTCs, their difference is poorly understood at molecular level. In this study, we focus on the transcriptome difference among PTCs, ATCs and normal tissue from a published dataset including 45 normal tissues, 49 PTCs and 11 ATCs, by applying a machine learning method, maximum relevance minimum redundancy, and identified 9 genes (BCL2, MRPS31, ID4, RASAL2, DLG2, MY01B, ZBTB5, PRKCQ and PPP6C) and 1 miscRNA (miscellaneous RNA, LOC646736) as important candidates involved in the progression of thyroid cancer. We further identified the protein-protein interaction (PPI) sub network from the shortest paths among the 9 genes in a PPI network constructed based on STRING database. Our results may provide insights to the molecular mechanism of the progression of thyroid cancer. PMID:24718460

Xu, Yaping; Deng, Yue; Ji, Zhenhua; Liu, Haibin; Liu, Yueyang; Peng, Hu; Wu, Jian; Fan, Jingping

2014-01-01

170

More algorithms for all-pairs shortest paths in weighted graphs  

Microsoft Academic Search

In the first part of the paper, we reexamine the all-pairsshortest paths (APSP) problem and present a newalgorithm with running time approaching O(n3\\/log2n), which improves all known algorithms for general real-weighted dense graphs andis perhaps close to the best result possible without using fast matrix multiplication, modulo a few log log n factors. In the second part of the paper,

Timothy M. Chan

2007-01-01

171

Application of Single-Source Shortest Path Algorithms to an OJCS (Organization of the Joint Chiefs of Staff) Contingency Planning Model and a Vehicle Routing Model.  

National Technical Information Service (NTIS)

This thesis investigates the use of single-source shortest path algorithms in two unrelated contexts. In the first application, the label setting and label correcting algorithms are examined for applicability to and implementation with a J-8, Organization...

J. W. Brown

1987-01-01

172

Performance Analysis of Reactive Shortest Single-path and Multipath Routing Mechanism With Load Balance  

Microsoft Academic Search

Research on multi-path routing protocols to provideimproved throughput and route resilience as compared withsingle-path routing has been explored in details in the contextof wired networks. However, multi-path routing mechanism hasnot been explored thoroughly in the domain of ad hoc networks.In this paper, we analyze and compare reactive single-path andmulti-path routing with load balance mechanisms in ad hoc networks,in terms of

Peter P. Pham; Sylvie Perreau

2003-01-01

173

Constraint-Based Local Search for Constrained Optimum Paths Problems  

NASA Astrophysics Data System (ADS)

Constrained Optimum Path (COP) problems arise in many real-life applications and are ubiquitous in communication networks. They have been traditionally approached by dedicated algorithms, which are often hard to extend with side constraints and to apply widely. This paper proposes a constraint-based local search (CBLS) framework for COP applications, bringing the compositionality, reuse, and extensibility at the core of CBLS and CP systems. The modeling contribution is the ability to express compositional models for various COP applications at a high level of abstraction, while cleanly separating the model and the search procedure. The main technical contribution is a connected neighborhood based on rooted spanning trees to find high-quality solutions to COP problems. The framework, implemented in COMET, is applied to Resource Constrained Shortest Path (RCSP) problems (with and without side constraints) and to the edge-disjoint paths problem (EDP). Computational results show the potential significance of the approach.

Pham, Quang Dung; Deville, Yves; van Hentenryck, Pascal

174

A study on design of dynamic route guidance system using forecasted travel time based on GPS data and modified shortest path algorithm  

Microsoft Academic Search

The objective of this paper is to propose the design of a dynamic route guidance system using forecasted travel time based on Global Positioning System (GPS) data and a modified shortest path algorithm. The Box-Jenkins method is used to forecast the travel time of each path between network nodes. The Floyd-Warshall algorithm is used to find the optimal route based

Sung-Soo Kim; Jong-Hyun Lee

1999-01-01

175

A Multilevel Probabilistic Beam Search Algorithm for the Shortest Common Supersequence Problem  

PubMed Central

The shortest common supersequence problem is a classical problem with many applications in different fields such as planning, Artificial Intelligence and especially in Bioinformatics. Due to its NP-hardness, we can not expect to efficiently solve this problem using conventional exact techniques. This paper presents a heuristic to tackle this problem based on the use at different levels of a probabilistic variant of a classical heuristic known as Beam Search. The proposed algorithm is empirically analysed and compared to current approaches in the literature. Experiments show that it provides better quality solutions in a reasonable time for medium and large instances of the problem. For very large instances, our heuristic also provides better solutions, but required execution times may increase considerably.

Gallardo, Jose E.

2012-01-01

176

A multilevel probabilistic beam search algorithm for the shortest common supersequence problem.  

PubMed

The shortest common supersequence problem is a classical problem with many applications in different fields such as planning, Artificial Intelligence and especially in Bioinformatics. Due to its NP-hardness, we can not expect to efficiently solve this problem using conventional exact techniques. This paper presents a heuristic to tackle this problem based on the use at different levels of a probabilistic variant of a classical heuristic known as Beam Search. The proposed algorithm is empirically analysed and compared to current approaches in the literature. Experiments show that it provides better quality solutions in a reasonable time for medium and large instances of the problem. For very large instances, our heuristic also provides better solutions, but required execution times may increase considerably. PMID:23300667

Gallardo, José E

2012-01-01

177

Algorithms and Bounds for Shortest Paths and Diameter in Faulty Hypercubes  

Microsoft Academic Search

In an n-dimensional hypercube Qn, with the fault set |F|<2n-2, assuming S and D are not isolated, it is shown that there exists a path of length equal to at most their Hamming distance plus 4. An algorithm with complexity O (|F|logn) is given to find such a path. A bound for the diameter of the faulty hypercube Qn-F, when

Sing-ban Tien; C. S. Raghavendra

1993-01-01

178

A computational study identifies HIV progression-related genes using mRMR and shortest path tracing.  

PubMed

Since statistical relationships between HIV load and CD4+ T cell loss have been demonstrated to be weak, searching for host factors contributing to the pathogenesis of HIV infection becomes a key point for both understanding the disease pathology and developing treatments. We applied Maximum Relevance Minimum Redundancy (mRMR) algorithm to a set of microarray data generated from the CD4+ T cells of viremic non-progressors (VNPs) and rapid progressors (RPs) to identify host factors associated with the different responses to HIV infection. Using mRMR algorithm, 147 gene had been identified. Furthermore, we constructed a weighted molecular interaction network with the existing protein-protein interaction data from STRING database and identified 1331 genes on the shortest-paths among the genes identified with mRMR. Functional analysis shows that the functions relating to apoptosis play important roles during the pathogenesis of HIV infection. These results bring new insights of understanding HIV progression. PMID:24244287

Ma, Chengcheng; Dong, Xiao; Li, Rudong; Liu, Lei

2013-01-01

179

A Computational Study Identifies HIV Progression-Related Genes Using mRMR and Shortest Path Tracing  

PubMed Central

Since statistical relationships between HIV load and CD4+ T cell loss have been demonstrated to be weak, searching for host factors contributing to the pathogenesis of HIV infection becomes a key point for both understanding the disease pathology and developing treatments. We applied Maximum Relevance Minimum Redundancy (mRMR) algorithm to a set of microarray data generated from the CD4+ T cells of viremic non-progressors (VNPs) and rapid progressors (RPs) to identify host factors associated with the different responses to HIV infection. Using mRMR algorithm, 147 gene had been identified. Furthermore, we constructed a weighted molecular interaction network with the existing protein-protein interaction data from STRING database and identified 1331 genes on the shortest-paths among the genes identified with mRMR. Functional analysis shows that the functions relating to apoptosis play important roles during the pathogenesis of HIV infection. These results bring new insights of understanding HIV progression.

Liu, Lei

2013-01-01

180

Transmission Scheduling for Optimizing Sensor Network Lifetime: A Stochastic Shortest Path Approach  

Microsoft Academic Search

We present transmission scheduling algorithms for maximizing the lifetime of a sensor network. In each data collection, only one group of sensors are scheduled to transmit their measurements directly to an access point (AP) through a fading channel, causing a reduction in battery energy levels of these sensors. We formulate the problem of dynamically choosing which group of sensors should

Yunxia Chen; Qing Zhao; Vikram Krishnamurthy; Dejan V. Djonin

2007-01-01

181

New Bounds for Old Algorithms: On the Average-Case Behavior of Classic Single-Source Shortest-Paths Approaches  

NASA Astrophysics Data System (ADS)

Despite disillusioning worst-case behavior, classic algorithms for single-source shortest-paths (SSSP) like Bellman-Ford are still being used in practice, especially due to their simple data structures. However, surprisingly little is known about the average-case complexity of these approaches. We provide new theoretical and experimental results for the performance of classic label-correcting SSSP algorithms on graph classes with non-negative random edge weights. In particular, we prove a tight lower bound of ?(n 2) for the running times of Bellman-Ford on a class of sparse graphs with O(n) nodes and edges; the best previous bound was ?(n 4/3 - ? ). The same improvements are shown for Pallottino's algorithm. We also lift a lower bound for the approximate bucket implementation of Dijkstra's algorithm from ?(n logn / loglogn) to ?(n 1.2 - ? ). Furthermore, we provide an experimental evaluation of our new graph classes in comparison with previously used test inputs.

Meyer, Ulrich; Negoescu, Andrei; Weichert, Volker

182

Identification of hepatocellular carcinoma related genes with k-th shortest paths in a protein-protein interaction network.  

PubMed

Hepatocellular carcinoma (HCC) is the most common type of liver cancer worldwide and one of the deadliest cancers in Asia. But at present, effective targets for HCC clinical therapy are still limited. The "guilt by association" rule suggests that interacting proteins share the same or similar functions and hence may be involved in the same pathway. This assumption can be used to identify disease related genes from protein association networks constructed from existing PPI data. Given the close association between Hepatitis B virus and Hepatitis B which may lead to HCC, here we develop a computational method to identify hepatocellular carcinoma related genes based on k-th shortest paths in the protein-protein interaction (PPI) network (we set k=1, 2 in this study). Finally, we found 33 genes whose p-values were less than 0.05, and most of them have been reported to be involved in HCC tumorigenesis and development. The results also provide a new reference for research into HCC oncogenesis and for development of new strategies for HCC clinical therapies. PMID:24056857

Jiang, Min; Chen, Yukang; Zhang, Yuchao; Chen, Lei; Zhang, Ning; Huang, Tao; Cai, Yu-Dong; Kong, XiangYin

2013-11-01

183

Traffic equilibrium problem with nonadditive path costs.  

National Technical Information Service (NTIS)

In this paper the authors present a version of the (static) traffic equilibrium problem in which the cost incurred on a path is not simply the sum of the costs on the arcs that constitute that path. The authors motivate this nonadditive version of the pro...

S. A. Gabriel D. Bernstein

1995-01-01

184

An Alternate Path To Stoichiometric Problem Solving.  

ERIC Educational Resources Information Center

Discusses an alternate path to teaching introductory stoichiometry based on research findings. The recommendation is to use problems that can be solved easily by rapid mental calculation as well as by pure logic. (AIM)

Schmidt, Hans-Jurgen

1997-01-01

185

An Implementation of Genetic Algorithm in Matlab: Solution to the Route Choice Problem in the Urban Traffic Network  

Microsoft Academic Search

Urban traffic network can be considered as an undirected graph. So the route choice problem in the traffic network can be converted to shortest path problem. The idea of using genetic algorithm to solve shortest path problem is proposed in this paper. The model of using genetic algorithm to solve shortest path problem which is programmed in Matlab is also

Jie Li; Minghao Zhu

2010-01-01

186

New Lower Bound Techniques for Robot Motion Planning Problems  

Microsoft Academic Search

We present new techniques for establishing lower bounds in robot motion planning problems. Our scheme is based on path encoding and uses homotopy equivalence classes of paths to encode state. We first apply the method to the shortest path problem in 3 dimensions. The problem is to find the shortest path under an Lp metric (e.g. a euclidean metric) between

John F. Canny; John H. Reif

1987-01-01

187

D-edge shortest-path problem for a Monge graph.  

National Technical Information Service (NTIS)

A complete edge-weighted directed graph on vertices 1,2,...,n that assigns cost c(i,j) to the edge (i,j) is called Monge if its edge costs form a Monge array, i.e., for all i < k and j < l, c(i, j)+c(k,l)(le) < c(i,l)+c(k,j). One reason Monge graphs are i...

W. W. Bein L. L. Larmore J. K. Park

1992-01-01

188

A Landmark Algorithm for the Time-Dependent Shortest Path Problem  

Microsoft Academic Search

Acknowledgments The author is heartily grateful to Professor Hiroshi Nagamochi for his continual guidance and invaluable suggestions to accomplish the thesis. He commented,in de- tail on the whole work in the thesis, which significantly improved the accuracy of the arguments and the quality of the expression. Without his generous help, none of this work could have been completed. He is

Hiroshi Nagamochi; Tatsuya Ohshima

189

Identification of Influenza A/H7N9 Virus Infection-Related Human Genes Based on Shortest Paths in a Virus-Human Protein Interaction Network.  

PubMed

The recently emerging Influenza A/H7N9 virus is reported to be able to infect humans and cause mortality. However, viral and host factors associated with the infection are poorly understood. It is suggested by the "guilt by association" rule that interacting proteins share the same or similar functions and hence may be involved in the same pathway. In this study, we developed a computational method to identify Influenza A/H7N9 virus infection-related human genes based on this rule from the shortest paths in a virus-human protein interaction network. Finally, we screened out the most significant 20 human genes, which could be the potential infection related genes, providing guidelines for further experimental validation. Analysis of the 20 genes showed that they were enriched in protein binding, saccharide or polysaccharide metabolism related pathways and oxidative phosphorylation pathways. We also compared the results with those from human rhinovirus (HRV) and respiratory syncytial virus (RSV) by the same method. It was indicated that saccharide or polysaccharide metabolism related pathways might be especially associated with the H7N9 infection. These results could shed some light on the understanding of the virus infection mechanism, providing basis for future experimental biology studies and for the development of effective strategies for H7N9 clinical therapies. PMID:24955349

Zhang, Ning; Jiang, Min; Huang, Tao; Cai, Yu-Dong

2014-01-01

190

Identification of Influenza A/H7N9 Virus Infection-Related Human Genes Based on Shortest Paths in a Virus-Human Protein Interaction Network  

PubMed Central

The recently emerging Influenza A/H7N9 virus is reported to be able to infect humans and cause mortality. However, viral and host factors associated with the infection are poorly understood. It is suggested by the “guilt by association” rule that interacting proteins share the same or similar functions and hence may be involved in the same pathway. In this study, we developed a computational method to identify Influenza A/H7N9 virus infection-related human genes based on this rule from the shortest paths in a virus-human protein interaction network. Finally, we screened out the most significant 20 human genes, which could be the potential infection related genes, providing guidelines for further experimental validation. Analysis of the 20 genes showed that they were enriched in protein binding, saccharide or polysaccharide metabolism related pathways and oxidative phosphorylation pathways. We also compared the results with those from human rhinovirus (HRV) and respiratory syncytial virus (RSV) by the same method. It was indicated that saccharide or polysaccharide metabolism related pathways might be especially associated with the H7N9 infection. These results could shed some light on the understanding of the virus infection mechanism, providing basis for future experimental biology studies and for the development of effective strategies for H7N9 clinical therapies.

Huang, Tao; Cai, Yu-Dong

2014-01-01

191

Spreading paths in partially observed social networks  

PubMed Central

Understanding how and how far information, behaviors, or pathogens spread in social networks is an important problem, having implications for both predicting the size of epidemics, as well as for planning effective interventions. There are, however, two main challenges for inferring spreading paths in real-world networks. One is the practical difficulty of observing a dynamic process on a network, and the other is the typical constraint of only partially observing a network. Using a static, structurally realistic social network as a platform for simulations, we juxtapose three distinct paths: (1) the stochastic path taken by a simulated spreading process from source to target; (2) the topologically shortest path in the fully observed network, and hence the single most likely stochastic path, between the two nodes; and (3) the topologically shortest path in a partially observed network. In a sampled network, how closely does the partially observed shortest path (3) emulate the unobserved spreading path (1)? Although partial observation inflates the length of the shortest path, the stochastic nature of the spreading process also frequently derails the dynamic path from the shortest path. We find that the partially observed shortest path does not necessarily give an inflated estimate of the length of the process path; in fact, partial observation may, counterintuitively, make the path seem shorter than it actually is.

Onnela, Jukka-Pekka; Christakis, Nicholas A.

2012-01-01

192

Solving the 2Disjoint Paths Problem in Nearly Linear Time  

Microsoft Academic Search

Given four distinct vertices s1,s2,t1, and t2 of a graph G, the\\u000a 2-disjoint paths problem is to determine two disjoint paths, p1 from s1 to t1 and p2 from s2 to t2, if such paths exist. Disjoint can mean vertex- or edge-disjoint. Both, the edge- and the vertex-disjoint version of the\\u000a problem, are NP-hard in the case of directed graphs.

Torsten Tholey

2006-01-01

193

The traffic equilibrium problem with nonadditive path costs  

SciTech Connect

In this paper the authors present a version of the (static) traffic equilibrium problem in which the cost incurred on a path is not simply the sum of the costs on the arcs that constitute that path. The authors motivate this nonadditive version of the problem by describing several situations in which the classical additivity assumption fails. They also present an algorithm for solving nonadditive problems that is based on the recent NE/SQP algorithm, a fast and robust method for the nonlinear complementarity problem. Finally, they present a small example that illustrates both the importance of using nonadditive costs and the effectiveness of the NE/SQP method.

Gabriel, S.A. [Argonne National Lab., IL (United States). Mathematics and Computer Science Div.; Bernstein, D. [Princeton Univ., NJ (United States). Dept. of Civil Engineering and Operations Research

1995-08-21

194

An Application of Calculus: Optimum Parabolic Path Problem  

ERIC Educational Resources Information Center

A practical and technological application of calculus problem is posed to motivate freshman students or junior high school students. A variable coefficient of friction is used in modelling air friction. The case in which the coefficient of friction is a decreasing function of altitude is considered. The optimum parabolic path for a flying object…

Atasever, Merve; Pakdemirli, Mehmet; Yurtsever, Hasan Ali

2009-01-01

195

Improved Algorithms for the 2Vertex Disjoint Paths Problem  

Microsoft Academic Search

Given distinct vertices s\\u000a 1,s\\u000a 2,t\\u000a 1, and t\\u000a 2 the 2-vertex-disjoint paths problem (2-VDPP) consists in determining two vertex-disjoint paths p\\u000a 1, from s\\u000a 1 to t\\u000a 1, and p\\u000a 2, from s\\u000a 2 to t\\u000a 2, if such paths exist.\\u000a \\u000a We show that by using some kind of sparsification technique the previously best known time bound of O(n?+?m?(m,n))

Torsten Tholey

2009-01-01

196

Solving the 2Disjoint Paths Problem in Nearly Linear Time  

Microsoft Academic Search

\\u000a Given four distinct vertices s\\u000a 1,s\\u000a 2,t\\u000a 1, and t\\u000a 2 of a graph G, the 2-disjoint paths problem is to determine two disjoint paths, p\\u000a 1 from s\\u000a 1 to t\\u000a 1 and p\\u000a 2 from s\\u000a 2 to t\\u000a 2, if such paths exist. Disjoint can mean vertex- or edge-disjoint.\\u000a \\u000a \\u000a Both, the edge- and the vertex-disjoint version of

Torsten Tholey; Johann Wolfgang

2004-01-01

197

A strategy for solving static multiple-optimal-path transit network problems  

SciTech Connect

The trip making process using transit versus private automobile differs in the use of time schedules, walking paths, transfer stops, plus issues such as fare and safety. Due to these factors, many of the standard shortest path algorithms do not apply. The purpose of this study is to develop an algorithm and strategy for transit providers to find best alternatives for the user, and to demonstrate how a geographic information system can be used in the development of transit advanced traveler information system (TATIS) to meet these needs. This paper presents a short introduction to TATIS systems, some commonly used algorithms in determining the shortest and multiple paths, and a new strategy that was developed in this study which differs from standard network algorithms. The major features of this proposed algorithm are: (1) Capability of handling multiple modes of transit; (2) providing paths that include walking distances from and to the transit path as well as between transfer points; and (3) provision of multiple optimal paths to allow the user flexibility in choosing a path.

Koncz, N.; Greenfeld, J.; Mouskos, K. [New Jersey Inst. of Tech., Newark, NJ (United States). Dept. of Civil Engineering

1996-05-01

198

Path Integral Treatment of Singular Problems and Bound States  

NASA Astrophysics Data System (ADS)

A path-integral approach for the computation of quantum-mechanical propagators and energy Green's functions is presented. Its effectiveness is demonstrated through its application to singular interactions, with particular emphasis on the inverse square potential — possibly combined with a delta-function interaction. The emergence of these singular potentials as low-energy nonrelativistic limits of quantum field theory is highlighted. Not surprisingly, the analog of ultraviolet regularization is required for the interpretation of these singular problems.

Camblong, Horacio E.; Ordóñez, Carlos R.

199

Vehicle routing problems with alternative paths: An application to on-demand transportation  

Microsoft Academic Search

The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin–destination connection. Several attributes can be defined for one arc (travel time, travel cost, etc.), but

Thierry Garaix; Christian Artigues; Dominique Feillet; Didier Josselin

2010-01-01

200

Optimizing public transit quality and system access: the multiple-route, maximal covering\\/shortest-path problem  

Microsoft Academic Search

Public transit service is a promising travel mode because of its potential to address urban sustainability. However, current ridership of public transit is very low in most urban regions -- particularly those in the United States. Low transit ridership can be attributed to many factors, among which poor service quality is key. Transit service quality may potentially be improved by

Changshan Wu; Alan T Murray

2005-01-01

201

Using a modified invasive weed optimization algorithm for a personalized urban multi-criteria path optimization problem  

NASA Astrophysics Data System (ADS)

The personalized urban multi-criteria quasi-optimum path problem (PUMQPP) is a branch of multi-criteria shortest path problems (MSPPs) and it is classified as a NP-hard problem. To solve the PUMQPP, by considering dependent criteria in route selection, there is a need for approaches that achieve the best compromise of possible solutions/routes. Recently, invasive weed optimization (IWO) algorithm is introduced and used as a novel algorithm to solve many continuous optimization problems. In this study, the modified algorithm of IWO was designed, implemented, evaluated, and compared with the genetic algorithm (GA) to solve the PUMQPP in a directed urban transportation network. In comparison with the GA, the results have shown the significant superiority of the proposed modified IWO algorithm in exploring a discrete search-space of the urban transportation network. In this regard, the proposed modified IWO algorithm has reached better results in fitness function, quality metric and running-time values in comparison with those of the GA.

Pahlavani, Parham; Delavar, Mahmoud R.; Frank, Andrew U.

2012-08-01

202

Conflict-free shortest-time bidirectional AGV routeing  

Microsoft Academic Search

This paper presents an efficient algorithm for finding conflict-free shortest-time routes for automated guided vehicles moving in a bidirectional flow path network. The proposed algorithm is based on Dijkstra's shortest-path method. It maintains, for each node, a list of time windows reserved by scheduled vehicles and a list of free time windows available for vehicles to be scheduled. We introduce

CHANG W. KIM; J. M. A. TANCHOCO

1991-01-01

203

Construction of Optimal-Path Maps for Homogeneous-Cost-Region Path-Planning Problems.  

National Technical Information Service (NTIS)

Fast path-planning algorithms are needed for autonomous vehicles and tactical terrain-analysis tools. We explore a new approach using 'optimal-path maps', that give the best path to a goal point from any given start point in cross-country two-dimensional ...

R. S. Alexander

1989-01-01

204

The optimal path of logistics distribution in electronic commerce  

Microsoft Academic Search

Efficient and fast logistics distribution system is of paramount significance for enterprises, especially for the development of e-commerce. At present, the problem that e-commerce puzzles businessmen is logistics distribution. Based on Dijkstra's shortest path algorithm, an intelligent optimal path algorithm is presented with the aid of the thoughts of state space searching and dynamic cut branch in artificial intelligence. The

Zhang Yong-mei; Ma Li

2010-01-01

205

Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs  

Microsoft Academic Search

The edge and vertex-disjoint path problems together with their unsplittable flow generalization are NP-hard problems with a multi- tude of applications in areas such as routing, scheduling and bin packing. Given the hardness of the problems, we study polynomial-time approxi- mation algorithms with bounded performance guarantees. We introduce techniques which yield new algorithms for a wide range of disjoint-path problems.

Stavros G. Kolliopoulos; Clifford Stein

1998-01-01

206

Solving graph problems with dynamic computation structures  

Microsoft Academic Search

We introduce dynamic computation structures (DCS), a compilation technique to produce dynamic code for reconfigurable computing. DCS specializes directed graph instances into user-level hardware for reconfigurable architectures. Several problems such as shortest path and transitive closure exhibit the general properties of closed semirings, an algebraic structure for solving directed paths. Motivating our application domain choice of closed semiring problems is

Jonathan W. Babb; Matthew I. Frank; Anant Agarwal

1996-01-01

207

A general approximation technique for constrained forest problems  

Microsoft Academic Search

We present a general approximation technique for a large class of graph problems. Our technique mostly applies to problems of covering, at minimum cost, the vertices of a graph with trees, cycles or paths satisfying certain requirements. In particular, many basic combinatorial optimization problems fit in this framework, including the shortest path, minimum spanning tree, minimum-weight perfect matching, traveling salesman

Michel X. Goemans; David P. Williamson

1992-01-01

208

Planning Monotone Paths to Visit a Set of Obstacles.  

National Technical Information Service (NTIS)

Computing a shortest collision-free path connecting points s and t that visits a given set of obstacles in two dimensions is like the travelling salesman problem and is NP-hard. We consider a restricted version of the above problem called the s-t-monotone...

L. P. Gewali

1990-01-01

209

A Path Following Algorithm for the Graph Matching Problem  

Microsoft Academic Search

We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex-concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices.

Mikhail Zaslavskiy; Francis R. Bach; Jean-philippe Vert

2009-01-01

210

What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? —Using Outerplanar Graphs, Trapezoid Graphs and In-Tournament Graphs as Examples  

Microsoft Academic Search

SUMMARY This paper analyzes what structural features of graph problems allow efficient parallel algorithms. We survey some parallel algorithms for typical problems on three kinds of graphs, outerplanar graphs, trapezoid graphs and in-tournament graphs. Our results on the shortest path problem, the longest path problem and the maximum flow problem on outerplanar graphs, the minimum-weight connected dominating set problem and

Shigeru MASUYAMA; Shin-ichi NAKAYAMA

211

Path integral Monte Carlo method and maximum entropy: a complete solution for the derivative valuation problem  

Microsoft Academic Search

Summary form only given. We propose a combination of the path-integral Monte Carlo method and the maximum entropy method as a comprehensive solution for the problem of pricing of derivative securities. The path-integral Monte Carlo approach relies on the probability distribution of the complete histories of the underlying security, from the present time to the contract expiration date. In our

M. S. Makivic

1996-01-01

212

Exact path-integration for the two-dimensional Coulomb problem  

Microsoft Academic Search

The lagrangian path integral for the Coulomb problem in two dimensions is explicitly calculated in the parabolic coordinates with the new ``time'' parameter of Duru and Kleinert. Supported in part by the Deutscher Akademischer Austauschdienst.

A. Inomata

1982-01-01

213

k-PathA: k-shortest Path Algorithm  

Microsoft Academic Search

One important aspect of computational systems biology includes the identification and analysis of functional response networks within large biochemical networks. These functional response networks represent the response of a biological system under a particular experimental condition which can be used to pinpoint critical biological processes.For this purpose, we have developed a novel algorithm to calculate response networks as scored\\/weighted sub-graphs

Alexander Ullrich; Christian V. Forst

2009-01-01

214

PATH  

NSDL National Science Digital Library

Started in the 1970s as an agency to assist men and women in gaining access to a variety of birth control methods, PATH has since expanded its focus to provide "sustainable, culturally relevant [health] solutions, enabling communities worldwide to break longstanding cycles of poor health." The PATH website has more than a dozen videos and slideshows available to visitors at the "Our Multimedia" link near the bottom right hand corner of the homepage. A three-minute video entitled "Better Nutrition For Life" educates visitors about an innovative rice product that could bring greater nutrition to millions of malnourished people where rice is a staple food. The product is Ultra Rice, and is actually fortified pasta that looks, cooks, and tastes like rice, but is fortified with nutrients. The "rice" can be fortified with the needed nutrients the particular population being served is lacking. A slideshow about TB in the Ukraine, explains to visitors why there has been a resurgence of TB in Eastern Europe, and how PATH and its partners set out to help control it throughout the region.

215

Ranking Sports Teams and the Inverse Equal Paths Problem  

Microsoft Academic Search

The problem of rank aggregation has been studied in con- texts varying from sports, to multi-criteria decision making, to machine learning, to academic citations, to ranking web pages, and to descriptive decision theory. Rank aggregation is the mapping of inputs that rank subsets of a set of objects into a consistent ranking that represents in some meaningful way the various

Dorit S. Hochbaum; Walter A. Haas

2006-01-01

216

Pareto memetic algorithm with path relinking for bi-objective traveling salesperson problem  

Microsoft Academic Search

The paper presents an effective version of the Pareto memetic algorithm with path relinking and efficient local search for multiple objective traveling salesperson problem. In multiple objective Traveling salesperson problem (TSP), multiple costs are associated with each arc (link). The multiple costs may for example correspond to the financial cost of travel along a link, time of travel, or risk

Andrzej Jaszkiewicz; Piotr Zielniewicz

2009-01-01

217

Path-Following Techniques for Solving the Static Contact Problem with Coulomb Friction  

NASA Astrophysics Data System (ADS)

A discrete contact problem with static Coulomb friction is considered. It is known that the problem may not have a unique solution. We explore continuation (path-following) techniques to find numerical solutions. In bioengineering, the application can arise in mathematical models of artificial joints.

Janovský, Vladimír

2011-09-01

218

Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks  

Microsoft Academic Search

This paper extends the A* methodology to shortest path problems in dynamic networks, in which arc travel times are time dependent. We present efficient adaptations of the A* algorithm for computing fastest (minimum travel time) paths from one origin node to one destination node, for one as well as multiple departure times at the origin node, in a class of

Ismaïl Chabini; Shan Lan

2002-01-01

219

Optimal robust path planning in general environments  

SciTech Connect

The authors address robust path planning for a mobile agent in a general environment by finding minimum cost source-destination paths having prescribed widths. The main result is a new approach that optimally solves the robust path planning problem using an efficient network flow formulation. Their algorithm represents a significant departure from conventional shortest-path or graph search based methods; it not only handles environments with solid polygonal obstacles, but also generalizes to arbitrary cost maps that may arise in modeling incomplete or uncertain knowledge of the environment. Simple extensions allow them to address higher dimensional problems instances and minimum-surface computations; the latter is a result of independent interest. They use an efficient implementation to exhibit optimal path-planning solutions for a variety of test problems. The paper concludes with open issues and directions for future work.

Hu, T.C. (Univ. of California, San Diego, La Jolla, CA (United States). Computer Science and Engineering Dept.); Kahng, A.B. (Univ. of California, Los Angeles, CA (United States). Computer Science Dept.); Robins, G. (Univ. of Virginia, Charlottesville, VA (United States). Dept. of Computer Science)

1993-12-01

220

Application of the CIRSSE cooperating robot path planner to the NASA Langley truss assembly problem  

NASA Technical Reports Server (NTRS)

A method for autonomously planning collision free paths for two cooperating robots in a static environment was developed at the Center for Intelligent Robotic Systems for Space Exploration (CIRSSE). The method utilizes a divide-and-conquer type of heuristic and involves non-exhaustive mapping of configuration space. While there is no guarantee of finding a solution, the planner was successfully applied to a variety of problems including two cooperating 9 degrees of freedom (dof) robots. Although developed primarily for cooperating robots the method is also applicable to single robot path planning problems. A single 6 dof version of the planner was implemented for the truss assembly east, at NASA Langley's Automated Structural Assembly Lab (ASAL). The results indicate that the planner could be very useful in addressing the ASAL path planning problem and that further work along these lines is warranted.

Weaver, Jonathan M.; Derby, Stephen J.

1993-01-01

221

Path-integral Monte Carlo simulations without the sign problem: Multilevel blocking approach for effective actions  

Microsoft Academic Search

The multilevel blocking algorithm recently proposed as a possible solution to the sign problem in path-integral Monte Carlo simulations has been extended to systems with long-ranged interactions along the Trotter direction. As an application, results for the real-time quantum dynamics of the spin-boson model are presented.

R. Egger; L. Mühlbacher; C. H. Mak

2000-01-01

222

A Path Analysis of Social Problem-Solving as a Predictor of White Racial Identity  

ERIC Educational Resources Information Center

This study examined (a) whether a developmental model or a model in which all subscales' measurement errors are correlated best explains the relationships among White racial identity (WRI) statuses, and (b) social problem-solving (SPS) skills as a predictor of WRI. Path analysis was conducted with a sample of 255 White undergraduate students from…

Carr, Amanda G.; Caskie, Grace I. L.

2010-01-01

223

Search Path Mapping: A Versatile Approach for Visualizing Problem-Solving Behavior.  

ERIC Educational Resources Information Center

Computer-based problem-solving examinations in immunology generate graphic representations of students' search paths, allowing evaluation of how organized and focused their knowledge is, how well their organization relates to critical concepts in immunology, where major misconceptions exist, and whether proper knowledge links exist between content…

Stevens, Ronald H.

1991-01-01

224

Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times  

Microsoft Academic Search

We consider an extension of the optimal searcher path problem (OSP), where a searcher moving through a discretised environment may now need to spend a non- uniform amount of time travelling from one region to another before being able to search it for the presence of a moving target. In constraining not only where but when the search of each

Haye Lau; Shoudong Huang; Gamini Dissanayake

2008-01-01

225

Home-delivered Problem Adaptation Therapy (PATH) for Depressed, Cognitively Impaired, Disabled Elders: A Preliminary Study  

PubMed Central

Objectives This preliminary study examines the efficacy of 12-week home-delivered Problem Adaptation Therapy (PATH) vs. home-delivered Supportive Therapy (ST) in reducing depression and disability in 30 depressed, cognitively impaired, disabled older adults. Design A 12-week randomized clinical trial. Research assistants were unaware of the participants' randomization status. Assessments were conducted at baseline, 6 and 12 weeks. Setting Weill Cornell - Advanced Center for Interventions and Services Research (ACISR). Participants Thirty elders with major depression, cognitive impairment, and disability were recruited through advertisement and the Home-Delivered Meals Program of the Westchester County Department of Senior Programs and Services. Intervention PATH is a home-delivered intervention designed to reduce depression and disability in depressed, cognitively impaired, disabled elders. PATH is based on Problem Solving Therapy (PST) and integrates environmental adaptation and caregiver participation. PATH is consistent with Lawton's ecological model of adaptive functioning in aging. Measurements Depression and disability were measured with Hamilton Depression Rating Scale – 24 items and Sheehan Disability Scale, respectively. Client Satisfaction Questionnaire was used to assess patient satisfaction with treatment. Results Mixed-effects model analyses revealed that PATH was more efficacious than ST in reducing depression and disability at 12 weeks. Participants in both treatment groups were satisfied with treatment. Conclusions This preliminary study suggests that PATH is well accepted and efficacious in depressed elders with major depression, cognitive impairment, and disability. Because this population may not adequately respond to antidepressant medication treatment, PATH may provide relief to many patients who would otherwise remain depressed and suffer.

Kiosses, Dimitris N.; Arean, Patricia A.; Teri, Linda; Alexopoulos, George S.

2010-01-01

226

Nonequilibrium problems in Quantum Field Theory and Schwinger's closed time path formalism  

NASA Astrophysics Data System (ADS)

We review the closed time path formalism of Schwinger using a path integral approach. We apply this formalism to the study of pair production from strong external fields as well as the time evolution of a nonequilibrium chiral phase transition. In 1961 in his classic paper 'Brownian Motion of a Quantum Particle,' Schwinger solved the formidable technical problem of how to use the action principle to study initial value problems. Previously, the action principle was formulated to study only transition matrix elements from an earlier time to a later time. The elegant solution of this problem was the invention of the closed time path (CTP) formalism. This formalism was first used to study field theory problems by Mahanthappa and Bakshi. With the advent of supercomputers, it has now become possible to use this formalism to numerically solve important field theory questions which are presented as initial value problems. Two of these problems we shall review here. They are: (1) The time evolution of the quark-gluon plasma; and (2) Dynamical evolution of a non-equilibrium chiral phase transition following a relativistic heavy ion collision.

Cooper, Fred

1995-04-01

227

Nonequilibrium problems in quantum field theory and Schwinger`s closed time path formalism  

SciTech Connect

We review the closed time path formalism of Schwinger using a path integral approach. We apply this formalism to the study of pair production from strong external fields as well as the time evolution of a nonequilibrium chiral phase transition. In 1961 in his classic paper ``Brownian Motion of a Quantum Particle,`` Schwinger solved the formidable technical problem of how to use the action principle to study initial value problems. Previously, the action principle was formulated to study only transition matrix elements from an earlier time to a later time. The elegant solution of this problem was the invention of the closed time path (CTP) formalism. This formalism was first used to study field theory problems by Mahanthappa and Bakshi. With the advent of supercomputers, it has now become possible to use this formalism to numerically solve important field theory questions which are presented as initial value problems. Two of these problems we shall review here. They are (1) The time evolution of the quark- gluon plasma. (2) Dynamical evolution of a non-equilibrium chiral phase transition following a relativistic heavy ion collision.

Cooper, F.

1995-05-01

228

Analysing Shortest Expected Delay Routing for Erlang Servers.  

National Technical Information Service (NTIS)

The queueing problem with a Poisson arrival stream and two identical, Erlang servers is analyzed for the queueing discipline based on shortest expected delay. This queueing problem may be represented as a random walk on the integer grid in the first quadr...

I. J. B. F. Adan J. Wessels

1993-01-01

229

A General Approximation Technique for Constrained Forest Problems  

Microsoft Academic Search

Abstract.,We present,a general approximation technique for a large class of graph problems.,Our technique mostly applies to problems of covering, at minimum cost, the vertices ofa graph with trees, cycles, or paths satisfying certain requirements. In particular, many basic combinatorial optimization problems fit in this framework, including the shortest path, minimum-cost spanning tree, minimum-weight perfect matching, traveling salesman, and Steiner tree,problems.

Michel X. Goemans; David P. Williamson

1995-01-01

230

Hard water problems and soft water paths: The "supply versus demand" conundrum  

NASA Astrophysics Data System (ADS)

Water problems are complex, interdisciplinary, and have profound effects on human and ecosystem health and well-being. And they are classic "hard" problems. Good science is necessary to solve these problems, but it is rarely sufficient. One of these hard problems is that of "perception" and "frame" - traditional water planners and managers frame freshwater as a "supply" problem, i.e., how can we access and deliver sufficient quantities of water of suitable quality, to satisfy perceived demand. In recent years, however, as water scarcity in different regions has increased due to growing populations and expanding economies, "peak water" limits (including peak renewable, non-renewable, and ecological limits) have started to constrain development of traditional "supply" options (Figure 1). That has led to new thinking about the other side of the equation: what is meant by water "demand" and can demand management tools and approaches offer a way to solve water problems. The "soft path for water" addresses this issue of water demand directly, but implementing demand-side solutions faces serious barriers. This talk will expound on the soft path approach and its potential to overcome some of the gridlock and stagnation in current water policy debates, with examples from both developed and developing countries, and different economic sectors.umulative global reservoir storage (major reservoirs) from 1900 to 2010, showing leveling off of traditional supply expansion. Data from the GRanD database.

Gleick, P. H.

2012-12-01

231

Receding Horizon Planning for Dubins Traveling Salesman Problems  

Microsoft Academic Search

In this paper we study the problem of finding the shortest global path of nonholonomic vehicles given a set of ordered waypoints. We represent the nonholonomic motion constraints using Dubins' model. Many approaches for this problem piece together smooth trajectories by considering the solution of consecutive two-point optimal trajectories, enforcing smoothness at waypoints by requiring continuity of the vehicle state

Xiang Ma; D. A. Castanon

2006-01-01

232

Towards Solving Weighted Graph Problems by Direct-Proportional Length-Based DNA Computing  

Microsoft Academic Search

Bio-molecular or DNA computing has emerged as an interdisciplinary field that draws together chemistry, molecular biology, computer science, and mathematics. From DNA computing point of view, it has been proven that it is possible to solve weighted graph problems such as Traveling Salesman Problem (TSP) and shortest path problem by exploiting some characteristics of DNA. Those characteristics are length, concentration,

Zuwairie Ibrahim

233

Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems  

Microsoft Academic Search

This paper considers the problem of designing fast, approx- imate, combinatorial algorithms for multicommodity flows and other fractional packing problems. We provide a dif- ferent approach to these problems which yields faster and much simpler algorithms. Our approach also allows us to substitute shortest path computations for min-cost flow computations in computing maximum concurrent flow and min-cost multicommodity flow; this

Naveen Garg; Jochen Könemann

1998-01-01

234

Visualization of P-T Paths Derived From Numerical Thermomechanical Experiments: new Insights Into Geodynamic Problems  

NASA Astrophysics Data System (ADS)

The pressure (P)-temperature (T)-time (t) path of a rock is a direct record of its movement within the Earth's interior. Thus P-T-t paths are powerful tools for understanding geodynamic processes, and in the last 25 years many P-T-t paths have been worked out for rocks of the crust and upper mantle. Although one-dimensional modelling of P-T-t paths during regional metamorphism (e.g., [1]) has allowed many important features of the P-T-t evolution of metamorphic rocks to be explained, and the necessary further progress can be achieved with 2D and 3D numerical approaches (e.g., [2-5]), the majority of numerical studies on geodynamic processes at present do not specifically address the details of P-T-t trajectories. Thus, the huge amount of empirical data available on the P-T-t evolution of crustal and mantle rocks is at present not adequately used to check and interactively optimize numerical models of geodynamic processes. This is especially true in those geodynamic settings where rocks must evolve contrasting P-T-t trajectories within the same rock complex (e.g., [3-4]). We suggest that there is a general major problem in visualizing the results of numerical geodynamic modelling in terms of the P-T-t evolution of the rocks involved. We have developed a user-friendly dynamic visualisation and animation technique to allow direct interactive comparison between P-T-t paths and numerical experiments of different geodynamic situations. In addition, we have implemented a new, robust Gibbs energy minimization approach to allow petrologically oriented internally consistent thermodynamic data bases to be used as independent constraints on P-T-t trajectories (e.g., [6]). References: [1] England, PC and AB Thompson, J. Petrol., 25, 894-928, 1984; [2] Peacock, S, Tectonics, 9, 1197-1211, 1990; [3] Gerya, TV, LL Perchuk, DD van Reenen and CA Smit, J. Geodynamics, 30, 17-35, 2000; [4] Willner AP, E Sebazungu, TV Gerya, WV Maresch and A Krohe, J. Geodynamics, 33, 281-314, 2002; [5] Beaumont, C, RA Jamieson, MH Nguyen and B Lee, Nature, 414, 738-742, 2001; [6] Gerya, TV, LL Perchuk, WV Maresch, AP Willner, DD Van Reenen, and CA Smit, Eur. J. Mineralogy, 14, 687-699.

Maresch, W.; Gerya, T.

2002-12-01

235

Shortest Path Search in Multi-Representation Street Databases  

Microsoft Academic Search

The fact that mobile users of location-based services (LBS) have to be able to go anywhere on earth without changing the application\\u000a brings up a major requirement: there has to be one global platform that provides a transborder and continuous access to the\\u000a information necessary for this kind of information systems — and the most important information source for location-based

Steffen Volz

2007-01-01

236

Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality  

Microsoft Academic Search

Using computer databases of scientific papers in physics, biomedical research, and computer science, we have constructed networks of collaboration between scientists in each of these disciplines. In these networks two scientists are considered connected if they have coauthored one or more papers together. Here we study a variety of nonlocal statistics for these networks, such as typical distances between scientists

M. E. J. Newman

2001-01-01

237

Visibility-Polygon Search and Euclidean Shortest Paths  

Microsoft Academic Search

Consider a collection of disjoint polygons in the plane containing a total of n edges. We show how to build, in O(n2) time and space, a data structure from which in O(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the

Takao Asano; Tetsuo Asano; Leonidas J. Guibas; John Hershberger; Hiroshi Imai

1985-01-01

238

Shortest Paths in Stochastic Networks with Correlated Link Costs  

Microsoft Academic Search

Abstract. The objective is to minimize,expected travel time from any origin to a specific destination in a congestible network with correlated link costs. Each link is assumed,to bein,one of two,possible conditions. Conditional probability density functions for link travel times are assumed,known,for each condition. Conditions over the traversed links are taken into account for determining the optimal routing strategy for the

Y. Y. FAN; R. E. KALABA; J. E. MOORE

2004-01-01

239

Watershed Cuts: Thinnings, Shortest Path Forests, and Topological Watersheds  

Microsoft Academic Search

We recently introduced watershed cuts, a notion of watershed in edge-weighted graphs. In this paper, our main contribution is a thinning paradigm from which we derive three algorithmic watershed cut strategies: The first one is well suited to parallel implementations, the second one leads to a flexible linear-time sequential implementation, whereas the third one links the watershed cuts and the

Jean Cousty; Gilles Bertrand; Laurent Najman; Michel Couprie

2010-01-01

240

Membrane Boundary Extraction Using a Circular Shortest Path Technique  

Microsoft Academic Search

Membrane proteins represent over 50% of known drug targets. Accordingly, several widely used assays in the High Content Analysis area rely on quantitative measures of the translocation of proteins between intracellular organelles and the cell surface. In order to increase the sensitivity of these assays, one needs to measure the signal specifically along the membrane, requiring a precise segmentation of

Changming Sun; Pascal Vallotton; Dadong Wang; Jamie Lopez; Yvonne Ng; David James

2007-01-01

241

Fast shortest path distance estimation in large networks  

Microsoft Academic Search

In this paper we study approximate landmark-based meth- ods for point-to-point distance estimation in very large net- works. These methods involve selecting a subset of nodes as landmarks and computing offline the distances from each node in the graph to those landmarks. At runtime, when the distance between a pair of nodes is needed, it can be estimated quickly by

Michalis Potamias; Francesco Bonchi; Carlos Castillo; Aristides Gionis

2009-01-01

242

An O(logn)Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs  

Microsoft Academic Search

\\u000a In this paper, we study an approximation algorithm for the maximum edge-disjoint paths problem. In the maximum edge-disjoint\\u000a paths problem, we are given a graph and a collection of pairs of vertices, and the objective is to find the maximum number\\u000a of pairs that can be connected by edge-disjoint paths. We give an O(logn)-approximation algorithm for the maximum edge-disjoint paths

Ken-ichi Kawarabayashiand; Yusuke Kobayashi

2010-01-01

243

Going against the flow: finding the optimal path  

NASA Astrophysics Data System (ADS)

We consider the problem of finding the optimum path of a boat traversing a straight in a current. The path of the shortest time is found using the calculus of variations with the constraint that the boat must land directly opposite to its starting point. We compare the optimal trajectory with that where the boat's local orientation is always directed to the arrival point. When analytical solutions cannot be found we use numerical methods. The level of the exposition is suitable for advanced undergraduate students, graduate students and general physicists.

Talbot, Julian

2010-01-01

244

An Efficient Global Optimization Approach to Multi Robot Path Exploration Problem Using Hybrid Genetic Algorithm  

Microsoft Academic Search

This paper presents a novel scheme for global path exploration to multi robots environment using hybrid implementation of evolutionary heuristic. This scheme is used to find an optimal path for each mobile robot to move in a static environment expressed by a weighted graph with nodes and links. The interesting part of this scheme is that the chromosome structure is

K. S. Senthilkumar; K. K. Bharadwaj

2008-01-01

245

Closed-time-path functional formalism in curved spacetime: Application to cosmological back-reaction problems  

Microsoft Academic Search

We discuss the generalization to curved spacetime of a path-integral formalism of quantum field theory based on the sum over paths first going forward in time in the presence of one external source from an in vacuum to a state defined on a hypersurface of constant time in the future, and then backwards in time in the presence of a

E. Calzetta; B. L. Hu

1987-01-01

246

Computing paths and cycles in biological interaction graphs  

PubMed Central

Background Interaction graphs (signed directed graphs) provide an important qualitative modeling approach for Systems Biology. They enable the analysis of causal relationships in cellular networks and can even be useful for predicting qualitative aspects of systems dynamics. Fundamental issues in the analysis of interaction graphs are the enumeration of paths and cycles (feedback loops) and the calculation of shortest positive/negative paths. These computational problems have been discussed only to a minor extent in the context of Systems Biology and in particular the shortest signed paths problem requires algorithmic developments. Results We first review algorithms for the enumeration of paths and cycles and show that these algorithms are superior to a recently proposed enumeration approach based on elementary-modes computation. The main part of this work deals with the computation of shortest positive/negative paths, an NP-complete problem for which only very few algorithms are described in the literature. We propose extensions and several new algorithm variants for computing either exact results or approximations. Benchmarks with various concrete biological networks show that exact results can sometimes be obtained in networks with several hundred nodes. A class of even larger graphs can still be treated exactly by a new algorithm combining exhaustive and simple search strategies. For graphs, where the computation of exact solutions becomes time-consuming or infeasible, we devised an approximative algorithm with polynomial complexity. Strikingly, in realistic networks (where a comparison with exact results was possible) this algorithm delivered results that are very close or equal to the exact values. This phenomenon can probably be attributed to the particular topology of cellular signaling and regulatory networks which contain a relatively low number of negative feedback loops. Conclusion The calculation of shortest positive/negative paths and cycles in interaction graphs is an important method for network analysis in Systems Biology. This contribution draws the attention of the community to this important computational problem and provides a number of new algorithms, partially specifically tailored for biological interaction graphs. All algorithms have been implemented in the CellNetAnalyzer framework which can be downloaded for academic use at .

Klamt, Steffen; von Kamp, Axel

2009-01-01

247

Sinkhole intrusion in mobile ad hoc networks: The problem and some detection indicators  

Microsoft Academic Search

We analyze the “sinkhole” problem in the context of the Dynamic Source Routing (DSR) protocol for wireless mobile ad hoc networks (MANETs). The sinkhole effect is caused by attempts to draw all network traffic to malicious nodes that broadcast fake shortest path routing information. Two reliable indicators of sinkhole intrusion are proposed and analyzed. We will study how these sinkholes

H. Chris Tseng; Benjamin Jack Culpepper

2005-01-01

248

Methodology for Augmenting Existing Paths with Additional Parallel Transects  

SciTech Connect

Visual Sample Plan (VSP) is sample planning software that is used, among other purposes, to plan transect sampling paths to detect areas that were potentially used for munition training. This module was developed for application on a large site where existing roads and trails were to be used as primary sampling paths. Gap areas between these primary paths needed to found and covered with parallel transect paths. These gap areas represent areas on the site that are more than a specified distance from a primary path. These added parallel paths needed to optionally be connected together into a single path—the shortest path possible. The paths also needed to optionally be attached to existing primary paths, again with the shortest possible path. Finally, the process must be repeatable and predictable so that the same inputs (primary paths, specified distance, and path options) will result in the same set of new paths every time. This methodology was developed to meet those specifications.

Wilson, John E.

2013-09-30

249

Simulation of excited states and the sign problem in the path integral Monte Carlo method  

Microsoft Academic Search

An approach is presented to compute properties of excited states in path integral Monte Carlo simulations of quantum systems. The approach is based on the introduction of several images of the studied system which have the total wavefunction antisymmetric over permutations of these images, and a simulation of the whole system at low enough temperature. The success of the approach

Alexander P Lyubartsev

2005-01-01

250

A Capacitated Vehicle Routing Problem with Toll-by-Weight Rule  

Microsoft Academic Search

Most literature on min-cost network flow problems such as shortest path problem (SPP), traveling salesman problem (TSP), vehicle\\u000a routing problem (VRP), assumes that the rate of any arc is constant. However, this assumption may not be true for some real\\u000a applications occurring in China due to the toll-by-weight rule. Different from most toll rules, toll-by-weight allows the\\u000a charging rates on

Chenghao Shen; Hu Qin; Andrew Lim

251

Estimating Critical Path and Arc Probabilities in Stochastic Activity Networks.  

National Technical Information Service (NTIS)

This paper describes a new procedure for estimating parameters of a stochastic activity network of N arcs. The parameters include the probability that path m is the longest path, the probability that path m is the shortest path, the probability that arc i...

G. S. Fishman

1983-01-01

252

Proximity Problems and the Voronoi Diagram on a Rectilinear Plane with Rectangular Obstacles. (Reannouncement with New Availability Information).  

National Technical Information Service (NTIS)

We consider the following four problems for a set S of K points on a plane, equipped with the rectilinear metric and containing a set R of n disjoint rectangular obstacles (so that distance is measured by a shortest rectilinear path avoiding obstacles in ...

S. Guha I. Suzuki

1993-01-01

253

On the dynamic Markov-Dubins problem: From path planning in robotics and biolocomotion to computational anatomy  

NASA Astrophysics Data System (ADS)

Andrei Andreyevich Markov proposed in 1889 the problem (solved by Dubins in 1957) of finding the twice continuously differentiable (arc length parameterized) curve with bounded curvature, of minimum length, connecting two unit vectors at two arbitrary points in the plane. In this note we consider the following variant, which we call the dynamic Markov-Dubins problem (dM-D): to find the time-optimal C 2 trajectory connecting two velocity vectors having possibly different norms. The control is given by a force whose norm is bounded. The acceleration may have a tangential component, and corners are allowed, provided the velocity vanishes there. We show that for almost all the two vectors boundary value conditions, the optimization problem has a smooth solution. We suggest some research directions for the dM-D problem on Riemannian manifolds, in particular we would like to know what happens if the underlying geodesic problem is completely integrable. Path planning in robotics and aviation should be the usual applications, and we suggest a pursuit problem in biolocomotion. Finally, we suggest a somewhat unexpected application to "dynamic imaging science". Short time processes (in medicine and biology, in environment sciences, geophysics, even social sciences?) can be thought as tangent vectors. The time needed to connect two processes via a dynamic Markov-Dubins problem provides a notion of distance. Statistical methods could then be employed for classification purposes using a training set.

Castro, Alex Lúcio; Koiller, Jair

2013-01-01

254

A Discrete Differential Evolution Approach with Local Search for Traveling Salesman Problems  

Microsoft Academic Search

\\u000a Combinatorial optimization problems are very commonly seen in scientific research and practical applications. Traveling Salesman\\u000a Problem (TSP) is one nonpolynomial-hard combinatorial optimization problem. It can be describe as follows: a salesman, who\\u000a has to visit clients in different cities, wants to find the shortest path starting from his home city, visiting every city\\u000a exactly once and ending back at the

João Guilherme Sauer; Leandro dos Santos Coelho; Viviana Cocco Mariani; Luiza de Macedo Mourelle; Nadia Nedjah

255

OPTIMAL DESIGN OF STATIONARY FLOW PROBLEMS BY PATH-FOLLOWING INTERIOR-POINT METHODS  

Microsoft Academic Search

We consider the numerical solution of structural optimization problems in CFD where the state variables are supposed to satisfy a linear or nonlinear Stok es system and the design variables are subject to bilateral pointwise constraints. Within a primal-dual setting, we suggest an all-at-once approach based on interior-point methods. The discretization is taken care of by Taylor-Hood elements with respect

HARBIR ANTIL; RONALD H. W. HOPPE; CHRISTOPHER LINSENMANN

256

Path-integral-expanded-ensemble Monte Carlo method in treatment of the sign problem for fermions.  

PubMed

Expanded-ensemble Monte Carlo method with Wang-Landau algorithm was used for calculations of the ratio of partition functions for classes of permutations in the problem of several interacting quantum particles (fermions) in an external field. Simulations for systems consisting of 2 up to 7 interacting particles in harmonic or Coulombic field were performed. The presented approach allows one to carry out calculations for low enough temperatures that makes it possible to extract data for the ground-state energy and low-temperature thermodynamics. PMID:20365297

Voznesenskiy, M A; Vorontsov-Velyaminov, P N; Lyubartsev, A P

2009-12-01

257

The Role of Youth Problem Behaviors in the Path From Child Abuse and Neglect to Prostitution: A Prospective Examination.  

PubMed

Behaviors beginning in childhood or adolescence may mediate the relationship between childhood maltreatment and involvement in prostitution. This paper examines five potential mediators: early sexual initiation, running away, juvenile crime, school problems, and early drug use. Using a prospective cohort design, abused and neglected children (ages 0-11) with cases processed during 1967-1971 were matched with non-abused, non-neglected children and followed into young adulthood. Data are from in-person interviews at approximate age 29 and arrest records through 1994. Structural Equation Modeling tested path models. Results indicated that victims of child abuse and neglect were at increased risk for all problem behaviors, except drug use. In the full model, only early sexual initiation remained significant as a mediator in the pathway from child abuse and neglect to prostitution. Findings were generally consistent for physical and sexual abuse and neglect. These findings suggest that interventions to reduce problem behaviors among maltreated children may also reduce their risk for prostitution later in life. PMID:20186260

Wilson, Helen W; Widom, Cathy Spatz

2010-01-01

258

The Role of Youth Problem Behaviors in the Path From Child Abuse and Neglect to Prostitution: A Prospective Examination  

PubMed Central

Behaviors beginning in childhood or adolescence may mediate the relationship between childhood maltreatment and involvement in prostitution. This paper examines five potential mediators: early sexual initiation, running away, juvenile crime, school problems, and early drug use. Using a prospective cohort design, abused and neglected children (ages 0–11) with cases processed during 1967–1971 were matched with non-abused, non-neglected children and followed into young adulthood. Data are from in-person interviews at approximate age 29 and arrest records through 1994. Structural Equation Modeling tested path models. Results indicated that victims of child abuse and neglect were at increased risk for all problem behaviors, except drug use. In the full model, only early sexual initiation remained significant as a mediator in the pathway from child abuse and neglect to prostitution. Findings were generally consistent for physical and sexual abuse and neglect. These findings suggest that interventions to reduce problem behaviors among maltreated children may also reduce their risk for prostitution later in life.

Wilson, Helen W.; Widom, Cathy Spatz

2009-01-01

259

Intelligent Recommender System Using Shopper's Path and Purchase Analysis  

Microsoft Academic Search

Shoppers having a predefined shopping list usually follow the shortest path through a supermarket or store in order to make their purchases. This paper aims to study customer behaviour of such shoppers with respect to two aspects: (1) the path followed through the store to make those purchases. (2) the average path length to make those purchases. The paper also

Anala A Pandit; Jyot Talreja; M. Agrawal; Deepak Prasad; Swati Baheti; G. Khalsa

2010-01-01

260

A Linear Algorithm for the Pos\\/Neg-Weighted 1Median Problem on a Cactus  

Microsoft Academic Search

The 1-median problem on a network asks for a vertex minimizing the sum of the weighted shortest path distances from itself\\u000a to all other vertices, each associated with a certain positive weight. We allow fornegative weights as well and devise an exact algorithm for the resulting ‘pos\\/neg-weighted’ problem defined on a cactus. The algorithm\\u000a visits every vertex just once and

Rainer E. Burkard; Jakob Krarup

1998-01-01

261

The Convex-Hull-and-Line Traveling Salesman Problem: A Solvable Case  

Microsoft Academic Search

We solve the special case of the Euclidean Traveling Salesman Problem wheren \\\\Gamma m cities lie on the boundary of the convex hull of all n cities, and the otherm cities lie on a line segment inside this convex hull by an algorithm whichneeds O(mn) time and O(n) space.Keywords: Euclidean Traveling Salesman Problem, shortest path, well-solvablecase, polynomial time algorithm.12 The

Vladimir G. Deineko; René Van Dal; Günter Rote

1994-01-01

262

Optimal parallel algorithms for problems modeled by a family of intervals  

NASA Technical Reports Server (NTRS)

A family of intervals on the real line provides a natural model for a vast number of scheduling and VLSI problems. Recently, a number of parallel algorithms to solve a variety of practical problems on such a family of intervals have been proposed in the literature. Computational tools are developed, and it is shown how they can be used for the purpose of devising cost-optimal parallel algorithms for a number of interval-related problems including finding a largest subset of pairwise nonoverlapping intervals, a minimum dominating subset of intervals, along with algorithms to compute the shortest path between a pair of intervals and, based on the shortest path, a parallel algorithm to find the center of the family of intervals. More precisely, with an arbitrary family of n intervals as input, all algorithms run in O(log n) time using O(n) processors in the EREW-PRAM model of computation.

Olariu, Stephan; Schwing, James L.; Zhang, Jingyuan

1992-01-01

263

Path Clearance  

Microsoft Academic Search

In military scenarios, agents (i.e., troops of soldiers, convoys, and unmanned vehicles) may often have to traverse environments with only a limited intelligence about the locations of adversaries. We study a particular instance of this problem that we refer to as path clearance problem.This article presents a survey of our work on scalable and suitable for real-time use approaches to

Maxim Likhachev; Anthony Stentz

2009-01-01

264

Information Spread of Emergency Events: Path Searching on Social Networks  

PubMed Central

Emergency has attracted global attentions of government and the public, and it will easily trigger a series of serious social problems if it is not supervised effectively in the dissemination process. In the Internet world, people communicate with each other and form various virtual communities based on social networks, which lead to a complex and fast information spread pattern of emergency events. This paper collects Internet data based on data acquisition and topic detection technology, analyzes the process of information spread on social networks, describes the diffusions and impacts of that information from the perspective of random graph, and finally seeks the key paths through an improved IBF algorithm. Application cases have shown that this algorithm can search the shortest spread paths efficiently, which may help us to guide and control the information dissemination of emergency events on early warning.

Hu, Hongzhi; Wu, Tunan

2014-01-01

265

Path similarity skeleton graph matching.  

PubMed

This paper presents a novel framework to for shape recognition based on object silhouettes. The main idea is to match skeleton graphs by comparing the shortest paths between skeleton endpoints. In contrast to typical tree or graph matching methods, we completely ignore the topological graph structure. Our approach is motivated by the fact that visually similar skeleton graphs may have completely different topological structures. The proposed comparison of shortest paths between endpoints of skeleton graphs yields correct matching results in such cases. The skeletons are pruned by contour partitioning with Discrete Curve Evolution, which implies that the endpoints of skeleton branches correspond to visual parts of the objects. The experimental results demonstrate that our method is able to produce correct results in the presence of articulations, stretching, and occlusion. PMID:18550909

Bai, Xiang; Latecki, Longin Jan

2008-07-01

266

Limited path percolation in complex networks.  

PubMed

We study the stability of network communication after removal of a fraction q=1-p of links under the assumption that communication is effective only if the shortest path between nodes i and j after removal is shorter than al(ij)(a> or =1) where l(ij) is the shortest path before removal. For a large class of networks, we find analytically and numerically a new percolation transition at p(c)=(kappa(0)-1)((1-a)/a), where kappa(0) [triple bond] / and k is the node degree. Above p(c), order N nodes can communicate within the limited path length al(ij), while below p(c), N(delta) (delta<1) nodes can communicate. We expect our results to influence network design, routing algorithms, and immunization strategies, where short paths are most relevant. PMID:17995444

López, Eduardo; Parshani, Roni; Cohen, Reuven; Carmi, Shai; Havlin, Shlomo

2007-11-01

267

A new graph model and algorithms for consistent superstring problems.  

PubMed

Problems related to string inclusion and non-inclusion have been vigorously studied in diverse fields such as data compression, molecular biology and computer security. Given a finite set of positive strings and a finite set of negative strings , a string ? is a consistent superstring if every positive string is a substring of ? and no negative string is a substring of ?. The shortest (resp. longest) consistent superstring problem is to find a string ? that is the shortest (resp. longest) among all the consistent superstrings for the given sets of strings. In this paper, we first propose a new graph model for consistent superstrings for given and . In our graph model, the set of strings represented by paths satisfying some conditions is the same as the set of consistent superstrings for and . We also present algorithms for the shortest and the longest consistent superstring problems. Our algorithms solve the consistent superstring problems for all cases, including cases that are not considered in previous work. Moreover, our algorithms solve in polynomial time the consistent superstring problems for more cases than the previous algorithms. For the polynomially solvable cases, our algorithms are more efficient than the previous ones. PMID:24751868

Na, Joong Chae; Cho, Sukhyeun; Choi, Siwon; Kim, Jin Wook; Park, Kunsoo; Sim, Jeong Seop

2014-01-01

268

Optimal Terrain Construction Problems and Applications in Intensity-Modulated Radiation Therapy  

Microsoft Academic Search

In this paper we study several rectilinear terrain construction\\u000a problems, which model the leaf sequencing problems in\\u000a intensity-modulated radiation therapy (IMRT).\\u000a We present a novel unified approach\\u000a based on geometric techniques for solving these terrain\\u000a construction problems. Our ideas include formulating the terrain\\u000a construction problems as computing shortest paths in a weighted directed\\u000a graph and building the graph by computing

Danny Z. Chen; Xiaobo Sharon Hu; Shuang Luan; Xiaodong Wu; Cedric X. Yu

2005-01-01

269

Fast distributed and parallel algorithms for data network control problems  

SciTech Connect

Analysis of existing algorithms, as well as the development and analysis of new algorithms/techniques for solving network control problems are presented. First, an upper bound for the time complexity of the path formulated gradient projection algorithm (for solving the optimal routing problem in large data networks) is derived. The complexity bound is expressed in terms of the size of the network and the total amount of traffic demand. Also, a new distributed shortest path algorithm is developed for a class of hierarchically structured data networks. The time complexity of this new algorithm is generically better than any known distributed shortest path algorithm. Next, the method of aggregation/disaggregation is applied to the gradient projection algorithm and is shown to have the potential of speeding up the rate of convergence. Finally, a novel parallel algorithm is developed for solving the multistage optimization problem. It is shown that this new parallel algorithm achieves a better time complexity than the standard dynamic programming approach of solving the multistage optimization problem.

Antonio, J.K.

1989-01-01

270

Fast marching methods for the continuous traveling salesman problem  

SciTech Connect

We consider a problem in which we are given a domain, a cost function which depends on position at each point in the domain, and a subset of points ('cities') in the domain. The goal is to determine the cheapest closed path that visits each city in the domain once. This can be thought of as a version of the Traveling Salesman Problem, in which an underlying known metric determines the cost of moving through each point of the domain, but in which the actual shortest path between cities is unknown at the outset. We describe algorithms for both a heuristic and an optimal solution to this problem. The order of the heuristic algorithm is at worst case M * N logN, where M is the number of cities, and N the size of the computational mesh used to approximate the solutions to the shortest paths problems. The average runtime of the heuristic algorithm is linear in the number of cities and O(N log N) in the size N of the mesh.

Andrews, J.; Sethian, J.A.

2008-12-01

271

Multiple Waypoint Path Planning for a Mobile Robot using Genetic Algorithms  

Microsoft Academic Search

This investigation developed a MATLAB program, based on genetic algorithms that generated an optimal (shortest distance) path plan for a mobile robot to visit all of the specified waypoints without colliding with the known obstacles. The designed genetic algorithm path planner was shown to accomplish this task and produce superior results when compared against a full search path planner. Next,

Trevor Davies; A. Jnifene

2006-01-01

272

Optimal paths for a car that goes both forwards and backwards  

Microsoft Academic Search

The path taken by a car with a given minimum turning radius has a lower bound on its radius of curvature at each point, but the path has cusps if the car shifts into or out of reverse gear. What is the shortest such path a car can travel between two points if its starting and ending directions are specified?

J. A. Reeds; L. A. Shepp

1990-01-01

273

Time calibration of a PT-path from the Western Tauern Window, Eastern Alps: the problem of closure temperatures  

Microsoft Academic Search

New Hornblende K-Ar and 39Ar-40Ar and mica Rb-Sr and K-Ar ages are used to place specific timemarks on a well-constrained pressure-temperature path for the late Alpine metamorphism in the Western Tauern Window. After identification of excess 40Ar, the closure behavior of Ar in hornblende is compared with that of Sr and Ar in phengite and biotite. Samples were collected in

F. Blanckenburg; I. M. Villa; H. Baur; G. Morteani; R. H. Steiger

1989-01-01

274

Planning multiple paths with evolutionary speciation  

Microsoft Academic Search

This paper demonstrates a new approach to multidimensional path planning that is based on multiresolution path representation, where explicit configuration space computation is not required, and incorporates an evolutionary algorithm for solving the multimodal optimization problem, generating multiple alternative paths simultaneously. The multiresolution path representation reduces the expected search length for the path-planning problem and accordingly reduces the overall computational

Cem Hocaoglu; Arthur C. Sanderson

2001-01-01

275

Drinking and desired self-images: path models of self-image goals, coping motives, heavy-episodic drinking, and alcohol problems.  

PubMed

Coping motives for drinking initiate alcohol-related problems. Interpersonal goals, which powerfully influence affect, could provide a starting point for this relation. Here we tested effects of self-image goals (which aim to construct and defend desired self-views) and compassionate goals (which aim to support others) on heavy-episodic drinking and alcohol-related problems. Undergraduate drinkers (N=258) completed measures of self-image and compassionate goals in academics and friendships, coping and enhancement drinking motives, heavy-episodic drinking, and alcohol-related problems in a cross-sectional design. As predicted, self-image goals, but not compassionate goals, positively related to alcohol-related problems. Path models showed that self-image goals relate to coping motives, but not enhancement motives; coping motives then relate to heavy-episodic drinking, which in turn relate to alcohol-related problems. Self-image goals remained a significant predictor in the final model, which accounted for 34% of the variance in alcohol-related problems. These findings indicate that self-image goals contribute to alcohol-related problems in college students both independently and through coping motives. Interventions can center on reducing self-image goals and their attendant negative affect. PMID:19586150

Moeller, Scott J; Crocker, Jennifer

2009-06-01

276

Drinking and Desired Self-Images: Path Models of Self-Image Goals, Coping Motives, Heavy-Episodic Drinking, and Alcohol Problems  

PubMed Central

Coping motives for drinking initiate alcohol-related problems. Interpersonal goals, which powerfully influence affect, could provide a starting point for this relation. Here we tested effects of self-image goals (which aim to construct and defend desired self-views) and compassionate goals (which aim to support others) on heavy-episodic drinking and alcohol-related problems. Undergraduate drinkers (N=258) completed measures of self-image and compassionate goals in academics and friendships, coping and enhancement drinking motives, heavy-episodic drinking, and alcohol-related problems in a cross-sectional design. As predicted, self-image goals, but not compassionate goals, positively related to alcohol-related problems. Path models showed that self-image goals relate to coping motives, but not enhancement motives; coping motives then relate to heavy-episodic drinking, which in turn relate to alcohol-related problems. Self-image goals remained a significant predictor in the final model, which accounted for 34% of the variance in alcohol-related problems. These findings indicate that self-image goals contribute to alcohol-related problems in college students both independently and through coping motives. Interventions can center on reducing self-image goals and their attendant negative affect.

Moeller, Scott J.; Crocker, Jennifer

2009-01-01

277

Steiner's Problem in Graphs and Its Implications.  

National Technical Information Service (NTIS)

A graph theoretic version of Steiner's problem in plane geometry is described. An approach for solving the problem, related to Melzak's solution to Steiner's problem, is presented. The problems of finding shortest route and minimal spanning tree in graphs...

S. L. Hakimi

1970-01-01

278

Air Vehicle Path Planning.  

National Technical Information Service (NTIS)

This dissertation explores optimal path planning for air vehicles. An air vehicle exposed to illumination by a tracking radar is considered and the problem of determining an optimal planar trajectory connecting two prespecified points is addressed. An ana...

J. M. Hebert

2001-01-01

279

Energy efficient dynamic shortest path routing in wireless Ad hoc sensor networks using genetic algorithm  

Microsoft Academic Search

Wireless sensor networks are catching up as the primary mode for monitoring and collecting data in physically challenging environments. They find applications in various fields varying from environment monitoring, military applications to monitoring patients in hospitals. The constraints due to their inherent features make routing in wireless sensor networks a big challenge. This paper covers Genetic algorithm (GA) based simple

R. Nallusamy; K. Duraiswamy; D. Ayya Muthukumar; C. Sathiyakumar

2010-01-01

280

A Posture Scheduling Algorithm Using Constrained Shortest Path to Prevent Pressure Ulcers  

Microsoft Academic Search

Pressure ulcer is a severe threat for immobilized and peripheral neuropathic patients such as bed-ridden, elderly, and diabetics. Once developed, the complication of pressure ulcer causes pain, suffering, and longer hospitalization for the patients. Additionally, pressure ulcer management imposes a serious burden on the health care providers. The optimal strategy to deal with pressure ulcers is prevention. The current standard

S. Ostadabbas; R. Yousefi; M. Nourani; M. Faezipour; L. Tamil; M. Pompeo

2011-01-01

281

Shortest-Path Network Analysis Is a Useful Approach toward Identifying Genetic Determinants of Longevity  

Microsoft Academic Search

Not Available Bibtex entry for this abstract Preferred format for this abstract (see Preferences) Find Similar Abstracts: Use: Authors Title Return: Query Results Return items starting with number Query Form Database: Astronomy Physics arXiv e-prints

J. R. Managbanag; Tarynn M. Witten; Danail Bonchev; Lindsay A. Fox; Mitsuhiro Tsuchiya; Brian K. Kennedy; Matt Kaeberlein; Ben Lehner

2008-01-01

282

Dynamic Maintenance Versus Swapping: An Experimental Study on Shortest Paths Trees  

Microsoft Academic Search

Given a spanning tree T of a 2-edge connected, weighted graph G, a swap edge for a failing edge e in T is an edge é of G reconnecting\\u000a the two subtrees of T created bythe removal of e. A best swap edge is a swap edge enjoying the additional property of optimizing\\u000a the swap, with respect to a given

Guido Proietti

2000-01-01

283

The shortest path from the surface to the nucleus: RBP-Jkappa\\/Su(H) transcription factor  

Microsoft Academic Search

Communication between cell surface receptors and nuclear transcription factors is of primary importance to multicellular organisms. Since there are numerous molecules involved in this process, their mutual interaction forms complex networks of informational regulation, which is still under extensive investigation. The RBP-J transcription factor interacts directly with the Notch receptor involved in cell lineage commitment, implicating the presence of a

Tasuku Honjo

1996-01-01

284

GPS-enabled mobiles for learning shortest paths: a pilot study  

Microsoft Academic Search

Recent GPS-enabled mobile phones provide a rich and novel platform for exploring new kinds of educational software. Moreover, powerful high-level programming languages such as Python allow rapid development of learning tools that take advantage of mobile technology. This paper reports on a recent pilot study using mobile phones as situated learning tools. The study focused on expressing Dijkstra's algorithm for

Jason J. Holdsworth; Siu Man Lui

2009-01-01

285

Shortest paths on 3-D simple Lie groups with nonholonomic constraint  

Microsoft Academic Search

In this paper we study the Carnot-Caratheodory metrics on SU(2) ¿ S3, SO(3) and SL(2) induced by their Cartan decomposition and by the Killing form. Besides computing explicitly geodesics and conjugate loci, we compute the cut loci (globally) and we give the expression of the Carnot-Caratheodory distance as the inverse of an elementary function. For SU(2) the cut locus is

Ugo V. Boscain; Francesco Rossi

2008-01-01

286

Approximate Bounds and Expressions for the Link Utilization of Shortest-Path Multicast Network Traffic  

Microsoft Academic Search

Multicast network traffic is information with one source node, but many destination nodes. Rather than setting up individual connections between the source node and each destination node, or broadcasting the information to the entire network, multicasting efficiently exploits link capacity by allowing the source node to transmit a small number of copies of the information to mutually-exclusive groups of destination

Borislav H. Simov; Srini B. Tridandapani; Michael S. Borella

1999-01-01

287

Clustering incorporating shortest paths identifies relevant modules in functional interaction networks  

Microsoft Academic Search

Many biological systems can be modeled as networks. Hence, network analysis is of increasing importance to systems biology. We describe an evolutionary algorithm for selecting clusters of nodes within a large network based upon network topology together with a measure of the relevance of nodes to a set of independently identified genes of interest. We apply the algorithm to a

Jennifer Hallinan; Matthew R. Pocock; Stephen G. Addinall; David A. Lydall; Anil Wipat

2009-01-01

288

Hardware\\/Software Integration for FPGA-based All-Pairs Shortest-Paths  

Microsoft Academic Search

Field-Programmable Gate Arrays (FPGAs) are be- ing employed in high performance computing systems owing to their potential to accelerate a wide variety of long-running routines. Parallel FPGA-based de- signs often yield a very high speedup. Applications us- ing these designs on reconfigurable supercomputers in- volve software on the system managing computation on the FPGA. To extract maximum performance from an

Uday Bondhugula; Ananth Devulapalli; James Dinan; Joseph Fernando; Pete Wyckoff; Eric Stahlberg; P. Sadayappan

2006-01-01

289

Genetic regulatory networks established by shortest path algorithm and conditional probabilities for ovarian carcinoma microarray data  

Microsoft Academic Search

In the cancer research recently, it still doesn't have a definitive conclusion for the regulatory mechanisms of tumorigenesis and metastasis. But different genes have different biological functions, and these functions with interactions between genes play an important key in gene regulatory networks. Microarray is a tool most commonly used in the disease research, and scientists usually use that the feature

Meng-Hsiun Tsai; Hsiao-Han Ko; Sheng-Chuan Chiu

2010-01-01

290

From the Cover: Transitive functional annotation by shortest-path analysis of gene expression data  

Microsoft Academic Search

Current methods for the functional analysis of microarray gene expression data make the implicit assumption that genes with similar expression profiles have similar functions in cells. However, among genes involved in the same biological pathway, not all gene pairs show high expression similarity. Here, we propose that transitive expression similarity among genes can be used as an important attribute to

Xianghong Zhou; Ming-Chih J. Kao; Wing Hung Wong

2002-01-01

291

Hardware\\/Software Codesign for All-Pairs Shortest-Paths on a Reconfigurable Supercomputer  

Microsoft Academic Search

Rapid advances in VLSI technology have led to Field- Programmable Gate Arrays (FPGAs) being employed in High Performance Computing systems. Applications using FPGAs on reconfigurable supercomputers involve software on the system managing computation on the reconfigurable hardware. To extract maximum benefits from a parallel FPGA kernel at the application level, it becomes crucial to minimize data movement costs on the

Uday Bondhugula; Ananth Devulapalli; James Dinan; Joseph Fernando; Pete Wyckoff; Eric Stahlberg; P. Sadayappan

292

Real-time endovascular guidewire position simulation using shortest path algorithms  

Microsoft Academic Search

Purpose  Treatment of vascular disease often involves endovascular interventions which use the vascular system for delivering treatment\\u000a devices via a previously inserted guidewire to the diseased site. Previous studies show relative reproducibility of guidewire\\u000a position after insertion, indicating that the guidewire position is constrained and could be represented by an energy minimization\\u000a approach. Such representation would support the surgeon’s decision process

Sebastian Schafer; Vikas Singh; Peter B. Noël; Alan M. Walczak; Jinhui Xu; Kenneth R. Hoffmann

2009-01-01

293

A Dynamic Shortest Path Algorithm Using Multi-Step Ahead Link Travel Time Prediction  

Microsoft Academic Search

Route guidance systems provide motorists with step-by-step instructions on how to get from any origin to any destination in a network. The systems calculate the best route from a user-supplied origin to destination, based on each link travel time on the network. Most studies on the route guidance development have been carried out based on only one-step ahead prediction of

Young-Ihn Lee; Seungjae Lee; Shinhae Lee; Jeunggyu Chon

2004-01-01

294

Multiresolution path planning for mobile robots  

Microsoft Academic Search

The problem of automatic collision-free path planning is central to mobile robot applications. An approach to automatic path planning based on a quadtree representation is presented. Hierarchical path-searching methods are introduced, which make use of this multiresolution representation, to speed up the path planning process considerably. The applicability of this approach to mobile robot path planning is discussed.

S. Kambhampati; L. S. Davis

1986-01-01

295

The Role of Youth Problem Behaviors in the Path from Child Abuse and Neglect to Prostitution: A Prospective Examination  

ERIC Educational Resources Information Center

Behaviors beginning in childhood or adolescence may mediate the relationship between childhood maltreatment and involvement in prostitution. This paper examines 5 potential mediators: early sexual initiation, running away, juvenile crime, school problems, and early drug use. Using a prospective cohort design, abused and neglected children (ages…

Wilson, Helen W.; Widom, Cathy Spatz

2010-01-01

296

Adaptive Path Following Primal Dual Interior Point Methods for Shape Optimization of Linear and Nonlinear Stokes Flow Problems  

Microsoft Academic Search

Summary. We are concerned with structural optimization problems in CFD where the state variables are supposed to satisfy a linear or nonlinear Stokes system and the design variables are subject to bilateral pointwise constraints. Within a primal- dual setting, we suggest an all-at-once approach based on interior-point methods. The discretization is taken care of by Taylor-Hood elements with respect to

Ronald H. W. Hoppe; Christopher Linsenmann; Harbir Antil

2007-01-01

297

Open path measurements of carbon dioxide and water vapor under foggy conditions - technical problems, approaches and effects on flux measurements and budget calculations  

NASA Astrophysics Data System (ADS)

To estimate carbon dioxide or water vapor fluxes with the Eddy Covariance method high quality data sets are necessary. Under foggy conditions this is challenging, because open path measurements are influenced by the water droplets that cross the measurement path as well as deposit on the windows of the optical path. For the LI-7500 the deposition of droplets on the window results in an intensity reduction of the infrared beam. To keep the strength of the infrared beam under these conditions, the energy is increased. A measure for the increased energy is given by the AGC value (Automatic Gain Control). Up to a AGC threshold value of 70 % the data from the LI-7500 is assumed to be of good quality (personal communication with LICOR). Due to fog deposition on the windows, the AGC value rises above 70 % and stays there until the fog disappears and the water on the windows evaporates. To gain better data quality during foggy conditions, a blower system was developed that blows the deposited water droplets off the window. The system is triggered if the AGC value rises above 70 %. Then a pneumatic jack will lift the blower system towards the LI-7500 and the water-droplets get blown off with compressed air. After the AGC value drops below 70 %, the pneumatic jack will move back to the idle position. Using this technique showed that not only the fog droplets on the window causing significant problems to the measurement, but also the fog droplets inside the measurement path. Under conditions of very dense fog the measured values of carbon dioxide can get unrealistically high, and for water vapor, negative values can be observed even if the AGC value is below 70 %. The negative values can be explained by the scatter of the infrared beam on the fog droplets. It is assumed, that different types of fog droplet spectra are causing the various error patterns observed. For high quality flux measurements, not only the AGC threshold value of 70 % is important, but also the fluctuation of the AGC value in a flux averaging interval. Such AGC value fluctuations can cause severe jumps in the concentration measurements that can hardly be corrected for. Results of fog effects on the LI-7500 performance and its consequences for flux measurements and budget calculations will be presented.

El-Madany, T.; Griessbaum, F.; Maneke, F.; Chu, H.-S.; Wu, C.-C.; Chang, S. C.; Hsia, Y.-J.; Juang, J.-Y.; Klemm, O.

2010-07-01

298

The Discrete Geodesic Problem  

Microsoft Academic Search

We present an algorithm for determining the shortest path between a source and a destination on an arbitrary (possibly nonconvex) polyhedral surface. The path is constrained to lie on the surface, and distances are measured according to the Euclidean metric. Our algorithm runs in time O(n log n) and requires O(n2) space, where n is the number ofedges ofthe surface.

Joseph S. B. Mitchell; David M. Mount; Christos H. Papadimitriou

1987-01-01

299

Tunable path centrality: Quantifying the importance of paths in networks  

NASA Astrophysics Data System (ADS)

Centrality is a fundamental measure in network analysis. Specifically, centrality of a path describes the importance of the path with respect to the remaining part of the network. In this paper, we propose a tunable path centrality (TPC) measure, which quantifies the centrality of a path by integrating the path degree (PD) (number of neighbors of the path) and the path bridge (PB) (number of bridges in the path) with a control parameter ?. Considering the complexity of large-scale and dynamical topologies of many real-world networks, both PD and PB are computed with only the local topological structure of a path. We demonstrate the distribution of the three path centralities (TPC, PD and PB) in computer-generated networks and real-world networks. Furthermore, we apply the three path centralities to the network fragility problem, and exploit the distribution of the optimal control parameter ? through simulation and analysis. Finally, the simulation results show that generally TPC is more efficient than PD and PB in the network fragility problem. These path centralities are also applicable in many other network problems including spread, control, prediction and so on.

Pu, Cun-Lai; Cui, Wei; Yang, Jian

2014-07-01

300

Fracturing the optimal paths.  

PubMed

Optimal paths play a fundamental role in numerous physical applications ranging from random polymers to brittle fracture, from the flow through porous media to information propagation. Here for the first time we explore the path that is activated once this optimal path fails and what happens when this new path also fails and so on, until the system is completely disconnected. In fact many applications can also be found for this novel fracture problem. In the limit of strong disorder, our results show that all the cracks are located on a single self-similar connected line of fractal dimension D(b) approximately = 1.22. For weak disorder, the number of cracks spreads all over the entire network before global connectivity is lost. Strikingly, the disconnecting path (backbone) is, however, completely independent on the disorder. PMID:20366106

Andrade, J S; Oliveira, E A; Moreira, A A; Herrmann, H J

2009-11-27

301

Curved paths in raptor flight: Deterministic models.  

PubMed

Two deterministic models for flight of Peregrine Falcons and possibly other raptors as they approach their prey are examined mathematically. Both models make two assumptions. The first, applicable to both models, is that the angle of sight between falcon and prey is constant, consistent with observations that the falcon keeps its head straight during flight and keeps on course by use of the deep foveal region in its eye which allows maximum acuity at an angle of sight of about 45 degrees . The second assumption for the first model (conical spiral), is that the initial direction of flight determines the overall path. For the second model (flight constrained to a tilted plane), a parameter that fixes the orientation of the plane is required. A variational calculation also shows that the tilted plane flight path is the shortest total path, and, consequently, the conical spiral is another shortest total path. Numerical calculations indicate that the flight paths for the two models are very similar for the experimental conditions under which observations have been made. However, the angles of flight and bank differ significantly. More observations are needed to investigate the applicability of the two models. PMID:16757000

Lorimer, John W

2006-10-21

302

Optimization of the measuring path on a coordinate measuring machine using genetic algorithms  

Microsoft Academic Search

Stamping dies, car bodies, turbine blades and other machine parts with curved surfaces are usually verified on coordinate measuring machines (CMMs). This is a time-consuming process with low productivity. This paper suggests genetic algorithms to optimize the measuring path on CMMs. The measuring head of a CMM can be considered as a traveling salesperson. To find the shortest measuring path

Liangsheng Qu; Guanhua Xu; Guohua Wang

1998-01-01

303

Mobile transporter path planning  

NASA Technical Reports Server (NTRS)

The use of a genetic algorithm (GA) for solving the mobile transporter path planning problem is investigated. The mobile transporter is a traveling robotic vehicle proposed for the space station which must be able to reach any point of the structure autonomously. Elements of the genetic algorithm are explored in both a theoretical and experimental sense. Specifically, double crossover, greedy crossover, and tournament selection techniques are examined. Additionally, the use of local optimization techniques working in concert with the GA are also explored. Recent developments in genetic algorithm theory are shown to be particularly effective in a path planning problem domain, though problem areas can be cited which require more research.

Baffes, Paul; Wang, Lui

1990-01-01

304

Tornado Paths  

NSDL National Science Digital Library

This website catalogs all the tornado paths in the United States since 1950. The tornado path data is overlaid onto a Google Maps base for easy browsing and manipulation of the map view. Clicking on individual tornados provides the user with information such as its Fujita rating, the amount of damage caused by the tornado, the size of the path that the tornado made, and the length of time the tornado was on the ground.

Samson, Perry; Michigan, University O.

305

New Sufficient Conditions for Hamiltonian Paths  

PubMed Central

A Hamiltonian path in a graph is a path involving all the vertices of the graph. In this paper, we revisit the famous Hamiltonian path problem and present new sufficient conditions for the existence of a Hamiltonian path in a graph.

Kaykobad, M.

2014-01-01

306

OSL—optimal single-loop guide paths for AGVS  

Microsoft Academic Search

This study deals with the Automated Guided Vehicle System guide path design problem. We suggest a single closed loop guide path layout configuration as an alternative to conventional but more complex guide path designs. The benefits of using a simple guide path versus more complicated guide paths are discussed. A procedure for designing an optimal single loop guide path for

J. M. A. TANCHOCOf; DAVID SINRIECH

1992-01-01

307

Quantum Path Interferences in High-Order Harmonic Generation  

SciTech Connect

We have investigated the intensity dependence of high-order harmonic generation in argon when the two shortest quantum paths contribute to the harmonic emission. For the first time to our knowledge, experimental conditions were found to clearly observe interference between these two quantum paths that are in excellent agreement with theoretical predictions. This result is a first step towards the direct experimental characterization of the full single-atom dipole moment and demonstrates an unprecedented accuracy of quantum path control on an attosecond time scale.

Zaier, A.; Holler, M.; Guandalini, A.; Schapper, F.; Biegert, J.; Gallmann, L.; Keller, U.; Wyatt, A. S.; Monmayrant, A.; Walmsley, I. A.; Cormier, E.; Auguste, T.; Caumes, J. P.; Salieres, P. [Physics Department, ETH Zurich, CH-8093 Zurich (Switzerland); Clarendon Laboratory, Parks Road, Oxford OX1 3PU (United Kingdom); CELIA, CNRS-CEA-Universite Bordeaux1, 351 cours de la liberation, 33405 Talence (France); Service des Photons, Atomes et Molecules, CEA-Saclay, 91191 Gif-sur-Yvette (France)

2008-04-11

308

Geometry of optimal path hierarchies  

NASA Astrophysics Data System (ADS)

We investigate the hierarchy of optimal paths in a disordered landscape, based on the best path, the second best path and so on in terms of an energy. By plotting each path at a height according to its energy above some zero level, a landscape appears. This landscape is self-affine and controlled by two Hurst exponents: the one controlling the height fluctuations is 1/3 and the one controlling the fluctuations of the equipotential lines in the landscape is 2/3. These two exponents correspond to the exponents controlling energy and shape fluctations in the directed polymer problem. We furthermore find that the density of spanning optimal paths scale as the length of the paths to -2/3 and the histogram of energy differences between consecutive paths scale as a power law in the difference size with exponent -2.5.

Talon, Laurent; Auradou, Harold; Pessel, Marc; Hansen, Alex

2013-08-01

309

Randomized path coloring on binary trees  

Microsoft Academic Search

Motivated by the problem of WDM routing in all-optical networks, we study the following NP-hard problem. We are given a directed binary tree T and a set R of directed paths on T. We wish to assign colors to paths of R, in such way that no two paths that share a directed arc of T are assigned the same

Vincenzo Auletta; Ioannis Caragiannis; Christos Kaklamanis; Pino Persiano

2002-01-01

310

Sampling diffusive transition paths.  

PubMed

The authors address the problem of sampling double-ended diffusive paths. The ensemble of paths is expressed using a symmetric version of the Onsager-Machlup formula, which only requires evaluation of the force field and which, upon direct time discretization, gives rise to a symmetric integrator that is accurate to second order. Efficiently sampling this ensemble requires avoiding the well-known stiffness problem associated with the sampling of infinitesimal Brownian increments of the path, as well as a different type of stiffness associated with the sampling of the coarse features of long paths. The fine-feature sampling stiffness is eliminated with the use of the fast sampling algorithm, and the coarse-feature sampling stiffness is avoided by introducing the sliding and sampling (S&S) algorithm. A key feature of the S&S algorithm is that it enables massively parallel computers to sample diffusive trajectories that are long in time. The authors use the algorithm to sample the transition path ensemble for the structural interconversion of the 38-atom Lennard-Jones cluster at low temperature. PMID:17444696

Miller, Thomas F; Predescu, Cristian

2007-04-14

311

Multiresolution Path Planning for Mobile Robots.  

National Technical Information Service (NTIS)

The problem of automatic collision-free path planning is central to mobile robot applications. This report presents an approach to automatic two dimensional path planning based on a quadtree representation. (A quadtree is a recursive decomposition of a 2-...

S. Kambhampati L. S. Davis

1985-01-01

312

Path Finder  

NSDL National Science Digital Library

Finding certain files on a computer can be an onerous chore from time to time, and Path Finder is a good solution for anyone who's been bedeviled by such a task. The application includes a dual pane browser, cut and paste support, and a website that includes an interactive tour through its other features. This version of Path Finder is compatible with systems running Mac OS X 10.5 and newer. Also, this is a 30-day free trial version, and a full paid license is required after that point.

313

Data Generation for Path Testing  

Microsoft Academic Search

We present two stochastic search algorithms for generating test cases that execute specified paths in a program. The two algorithms are: a simulated annealing algorithm (SA), and a genetic algorithm (GA). These algorithms are based on an optimization formulation of the path testing problem which include both integer- and real-value test cases. We empirically compare the SA and GA algorithms

Nashat Mansour; Miran Salame

2004-01-01

314

Analysis of Crossing Path Crashes.  

National Technical Information Service (NTIS)

This report defines the problem of crossing path crashes in the United States. This crash type involves one moving vehicle that cuts across the path of another when their initial approach comes from either lateral or opposite directions and they typically...

W. G. Najm J. D. Smith D. L. Smith

2001-01-01

315

Challenging of path planning algorithms for autonomous robot in known environment  

NASA Astrophysics Data System (ADS)

Most of the mobile robot path planning is estimated to reach its predetermined aim through the shortest path and avoiding the obstacles. This paper is a survey on path planning algorithms of various current research and existing system of Unmanned Ground Vehicles (UGV) where their challenging issues to be intelligent autonomous robot. The focuses are some short reviews on individual papers for UGV in the known environment. Methods and algorithms in path planning for the autonomous robot had been discussed. From the reviews, we obtained that the algorithms proposed are appropriate for some cases such as single or multiple obstacles, static or movement obstacle and optimal shortest path. This paper also describes some pros and cons for every reviewed paper toward algorithms improvement for further work.

Farah, R. N.; Irwan, N.; Zuraida, Raja Lailatul; Shaharum, Umairah; Hanafi@Omar, Hafiz Mohd

2014-06-01

316

The Travelling Salesman Problem  

NSDL National Science Digital Library

The Traveling Salesman Problem is one of the most intensively studied problems in computational mathematics. These pages are devoted to the history, applications, and current research of this challenge of finding the shortest route visiting each member of a collection of locations and returning to your starting point.

Cook, William

317

Path ensembles and path sampling in nonequilibrium stochastic systems.  

PubMed

Markovian models based on the stochastic master equation are often encountered in single molecule dynamics, reaction networks, and nonequilibrium problems in chemistry, physics, and biology. An efficient and convenient method to simulate these systems is the kinetic Monte Carlo algorithm which generates continuous-time stochastic trajectories. We discuss an alternative simulation method based on sampling of stochastic paths. Utilizing known probabilities of stochastic paths, it is possible to apply Metropolis Monte Carlo in path space to generate a desired ensemble of stochastic paths. The method is a generalization of the path sampling idea to stochastic dynamics, and is especially suited for the analysis of rare paths which are not often produced in the standard kinetic Monte Carlo procedure. Two generic examples are presented to illustrate the methodology. PMID:17867733

Harland, Ben; Sun, Sean X

2007-09-14

318

Term Paths  

NSDL National Science Digital Library

Students follow several pathways using anatomical directions on a simulated "body" produced from a copy of a school building's fire evacuation plan. The main hallways are designated as major blood vessels and the various areas of the school, the head, chest, abdomen, etc. Students complete several pathways using anatomical terms as directions. For example, one of my paths begins, "Ex- ot-, ad- superior, ecto- derm-, peri-frontal, circum- rhino-, " which loosely means, exit the ear, go to the superior region, outside the skin, around the frontal region, around the nose. At the end of each path I leave a clue that lets me know the students actually made it. The combined clues form a sentence.

Cynthia Ann Radle (McCullough High School REV)

1995-06-30

319

Feynman path integrals in the young double-slit experiment  

Microsoft Academic Search

An estimate for the value of the nonlinear interference term in the Young double-slit experiment is found using the Feynman path-integral method. In our time-dependent calculation the usual interference term becomes multiplied by 1+e withe proportional to cos(2m? L\\/ hT), where ? is the distance between the two slits (holes) andL is the length of the shortest trajectory of electrons

H. Yabuki

1986-01-01

320

Feynman Path Integrals in the Young Double-Slit Experiment  

NASA Astrophysics Data System (ADS)

An estimate for the value of the nonlinear interference term in the Young double-slit experiment is found using the Feynman path-integral method. In our time-dependent calculation the usual interference term becomes multiplied by 1+ e with e proportional to cos(2 m? L/ ? T), where ? is the distance between the two slits (holes) and L is the length of the shortest trajectory of electrons between the source and the observation point.

Yabuki, H.

1986-02-01

321

Feynman path integrals in the young double-slit experiment  

SciTech Connect

An estimate for the value of the nonlinear interference term in the Young double-slit experiment is found using the Feynman path-integral method. In our time-dependent calculation the usual interference term becomes multiplied by 1 + e with e proportional to cos(2mlambdaL//eta/T), where lambda is the distance between the two slits (holes) and L is the length of the shortest trajectory of electrons between the source and the observation point.

Yabuki, H.

1986-02-01

322

Path diversity for enhanced media streaming  

Microsoft Academic Search

Media streaming over best effort packet networks such as the Internet is quite challenging because of the dynamic and unpredictable available bandwidth, loss rate, and delay. Recently, streaming over multiple paths to provide path diversity has emerged as an approach to help overcome these problems. This article provides an overview of the benefits and use of path diversity for media

John G. Apostolopoulos; Mitchell D. Trott

2004-01-01

323

Path Integral Analyses of the Hydrogen Atom  

Microsoft Academic Search

The path integral analysis of the hydrogen atom problem are presented in this dissertation. The Green's function for the hydrogen atom is calculated exactly by path integration. The scattering phase shifts are also expressed in terms of path integrals and evaluated for the Coulomb potential with or without additional modifying potentials. First, the hydrogen atom in two dimensions is treated

Roger Chung Chor Ho

1982-01-01

324

Path integral analyses of the hydrogen atom  

Microsoft Academic Search

The path integral analysis of the hydrogen atom problem are presented in this dissertation. The Green's function for the hydrogen atom is calculated exactly by the path integration. The scattering phase shifts are also expressed in terms of path integrals and evaluated for the Coulomb potential with or without additional modifying potentials. First, the hydrogen atom in two dimensions is

1982-01-01

325

Path planning using a tangent graph for mobile robots among polygonal and curved obstacles  

SciTech Connect

This article proposes a tangent graph for path planning of mobile robots among obstacles with a general boundary. The tangent graph is defined on the basis of the locally shortest path. It has the same data structure as the visibility graph, but its nodes represent common tangent points on obstacle boundaries, and its edges correspond to collision-free common tangents between the boundaries and convex boundary segments between the tangent points. The tangent graph requires O(K[sup 2]) memory, where K denotes the total number of convex segments of the obstacle boundaries. The tangent graph includes all locally shortest paths and is capable of coping with path planning not only among polygonal obstacles but also among curved obstacles.

Liu, Yun-Hui; Arimoto, Suguru (Univ. of Tokyo (Japan))

1992-08-01

326

Reaction path study of helix formation in tetrapeptides: Effect of side chains  

Microsoft Academic Search

A computational protocol to calculate steepest descent paths in flexible molecules is discussed in detail. The algorithm does not use second derivatives and related matrices, and is therefore suitable for large systems. The shortest reaction coordinate from the helix to the extended chain conformation is calculated for a series of different tetrapeptides. The formation of a helical turn is investigated

Chyung Choi; Ron Elber

1991-01-01

327

TIME-OPTIMAL PATHS FOR LATERAL NAVIGATION OF AN AUTONOMOUS UNDERACTUATED AIRSHIP  

Microsoft Academic Search

This paper deals with a characterization of the shortest paths for lateral navigation of an autonomous underactuated airship taking into account its dynamics and actuator limitations. The initial and terminal positions are given. We would like to specify the control forces that steer the unmanned aerial vehicle to the given terminal position requiring the minimal time for lateral navigation. The

Salim Hima; Yasmina Bestaoui

328

Output-Sensitive Reporting of Disjoint Paths  

Microsoft Academic Search

A k-path query on a graph consists of computing k vertex-disjoint paths between two givenvertices of the graph, whenever they exist. In this paper, we study the problem of performingk-path queries, with k 3, in a graph G with n vertices. We denote with ` the total length ofthe paths reported. For k 3, we present an optimal data structure

Giuseppe Di Battista; Roberto Tamassia; Luca Vismara

1999-01-01

329

Path Planning Control.  

National Technical Information Service (NTIS)

Viewgraphs on path planning control are presented. Topics covered include: model based path planning; sensor based path planning; hybrid path planning; proximity sensor array; and applications for fuzzy logic.

M. Mcroberts

1990-01-01

330

Path planning control  

NASA Technical Reports Server (NTRS)

Viewgraphs on path planning control are presented. Topics covered include: model based path planning; sensor based path planning; hybrid path planning; proximity sensor array; and applications for fuzzy logic.

Mcroberts, Malcolm

1990-01-01

331

Randomized path coloring on binary trees  

Microsoft Academic Search

Motivated by the problem of WDM routing in all-optical networks, we study the following NP-hard problem. We are given a di- rected binary tree T and a set R of directed paths on T.W e wish to assign colors to paths in R, in such a way that no two paths that share ad irected arc ofT are assigned the

Vincenzo Auletta; Ioannis Caragiannis; Christos Kaklamanis; Pino Persiano

2000-01-01

332

Calculating Least Risk Paths in 3d Indoor Space  

NASA Astrophysics Data System (ADS)

Over the last couple of years, research on indoor environments has gained a fresh impetus; more specifically applications that support navigation and wayfinding have become one of the booming industries. Indoor navigation research currently covers the technological aspect of indoor positioning and the modelling of indoor space. The algorithmic development to support navigation has so far been left mostly untouched, as most applications mainly rely on adapting Dijkstra's shortest path algorithm to an indoor network. However, alternative algorithms for outdoor navigation have been proposed adding a more cognitive notion to the calculated paths and as such adhering to the natural wayfinding behaviour (e.g. simplest paths, least risk paths). These algorithms are currently restricted to outdoor applications. The need for indoor cognitive algorithms is highlighted by a more challenged navigation and orientation due to the specific indoor structure (e.g. fragmentation, less visibility, confined areas…). As such, the clarity and easiness of route instructions is of paramount importance when distributing indoor routes. A shortest or fastest path indoors not necessarily aligns with the cognitive mapping of the building. Therefore, the aim of this research is to extend those richer cognitive algorithms to three-dimensional indoor environments. More specifically for this paper, we will focus on the application of the least risk path algorithm of Grum (2005) to an indoor space. The algorithm as proposed by Grum (2005) is duplicated and tested in a complex multi-storey building. The results of several least risk path calculations are compared to the shortest paths in indoor environments in terms of total length, improvement in route description complexity and number of turns. Several scenarios are tested in this comparison: paths covering a single floor, paths crossing several building wings and/or floors. Adjustments to the algorithm are proposed to be more aligned to the specific structure of indoor environments (e.g. no turn restrictions, restricted usage of rooms, vertical movement) and common wayfinding strategies indoors. In a later stage, other cognitive algorithms will be implemented and tested in both an indoor and combined indoor-outdoor setting, in an effort to improve the overall user experience during navigation in indoor environments.

Vanclooster, A.; De Maeyer, Ph.; Fack, V.; Van de Weghe, N.

2013-08-01

333

Route choices of transport bicyclists: a comparison of actually used and shortest routes  

PubMed Central

Background Despite evidence that environmental features are related to physical activity, the association between the built environment and bicycling for transportation remains a poorly investigated subject. The aim of the study was to improve our understanding of the environmental determinants of bicycling as a means of transportation in urban European settings by comparing the spatial differences between the routes actually used by bicyclists and the shortest possible routes. Methods In the present study we examined differences in the currently used and the shortest possible bicycling routes, with respect to distance, type of street, and environmental characteristics, in the city of Graz, Austria. The objective measurement methods of a Global Positioning System (GPS) and a Geographic Information System (GIS) were used. Results Bicycling routes actually used were significantly longer than the shortest possible routes. Furthermore, the following attributes were also significantly different between the used route compared to the shortest possible route: Bicyclists often used bicycle lanes and pathways, flat and green areas, and they rarely used main roads and crossings. Conclusion The results of the study support our hypothesis that bicyclists prefer bicycle pathways and lanes instead of the shortest possible routes. This underlines the importance of a well-developed bicycling infrastructure in urban communities.

2014-01-01

334

Global Path Planning Approach for Redundant Manipulators.  

National Technical Information Service (NTIS)

A new approach for global path planning of redundant manipulators is proposed. It poses the path planning problem as a finite time nonlinear control problem. The solution is found by a Newton-Raphson type algorithm. This technique is capable of handling v...

S. Seereeram J. Wen

1993-01-01

335

Finding Regular Simple Paths in Graph Databases  

Microsoft Academic Search

We consider the following problem: given a labelled directed graph and a regular expression , find all pairs of nodes connected by a simple path such that theconcatenation of the labels along the path satisfies . The problem is motivated by the observation that many recursive queries in relational databases can be expressed in this form, and by the implementation

Alberto O. Mendelzon; Peter T. Wood

1989-01-01

336

UAV Path Planning for Passive Emitter Localization  

Microsoft Academic Search

A path planning algorithm is presented for uninhabited aerial vehicles (UAVs) trying to geolocate an emitter using passive payload sensors. The objective is to generate a sequence of waypoints for each vehicle that minimizes localization uncertainty. The path planning problem is cast as a nonlinear programming problem using an approximation of the Fisher information matrix (FIM) and solved at successive

Kutluyil Dogancay

2012-01-01

337

Maintaining Incremental Optimality When Building Shortest Euclidean Tours.  

National Technical Information Service (NTIS)

Reported upon are experimental runs of an algorithm designed to incremental optimality when building tours for the Euclidean traveling salesman problem. Unlike the Lin-Kernighan edge eschange or Padberg-Rinaldi branch-and-cut techniques which begin with s...

T. M. Cronin

1990-01-01

338

The discrete geodesic problem  

SciTech Connect

The authors present an algorithm for determining the shortest path between a source and a destination on an arbitrary (possibly nonconvex) polyhedral surface. The path is constrained to lie on the surface, and distances are measured according to the Euclidean metric. The algorithm runs in time O(n/sup 2/ log n) and requires O(n/sup 2/) space, where n is the number of edges of the surface. After running the algorithm, the distance from the source to any other destination may be determined using standard techniques in time O(log n) by locating the destination in the subdivision created by the algorithm. The actual shortest path from the source to a destination can be reported in time O(kappa+log n), where kappa is the number of faces crossed by the path. The algorithm generalizes to the case of multiple source points to build the Voronoi diagram on the surface, where n is now the maximum of the number of vertices and the number of sources.

Mitchell, J.S.B.; Mount, D.M.; Papadimitriou, C.H.

1987-08-01

339

Processor Would Find Best Paths On Map  

NASA Technical Reports Server (NTRS)

Proposed very-large-scale integrated (VLSI) circuit image-data processor finds path of least cost from specified origin to any destination on map. Cost of traversal assigned to each picture element of map. Path of least cost from originating picture element to every other picture element computed as path that preserves as much as possible of signal transmitted by originating picture element. Dedicated microprocessor at each picture element stores cost of traversal and performs its share of computations of paths of least cost. Least-cost-path problem occurs in research, military maneuvers, and in planning routes of vehicles.

Eberhardt, Silvio P.

1990-01-01

340

NUMERICAL INTEGRATION OF THE FEYNMAN PATH INTEGRAL FOR RADIATIVE TRANSPORT  

Microsoft Academic Search

The radiative transport problem is cast in integral form using a transport kernel. The transport kernel has an explicit representation in terms of a Feynman Path Integral over all paths between selected points in a volume. This representation is setup in detail. Numerical evaluation of this Path Integral is formulated with a Frenet-Serret based procedure for generating valid random paths,

Jerry Tessendorf

2009-01-01

341

Continuous-curvature path planning for car-like vehicles  

Microsoft Academic Search

We consider path planning for a car-like vehicle. Previous solutions to this problem computed paths made up of circular arcs connected by tangential line segments. Such paths have a discontinuous curvature profile. Accordingly a vehicle following such a path has to stop at each curvature discontinuity in order to re-orientate its front wheels. To remove this limitation, we add a

A. Scheuer; Th. Fraichard

1997-01-01

342

Multilevel Path Planning for Nonholonomic Robots Using Semiholonomic Subsystems  

Microsoft Academic Search

We present a new and complete multilevel approachfor solving path- planning problems for nonholonomic robots. At the first level, a path is found that disrespects (some of) the nonholonomic constraints. At each of the next levels, a new path is generated by transformation of the path generated at the previous level. The transformation is such that more nonholonomic constraints are

Sepanta Sekhavat; Petr Svestka; Jean-Paul Laumond; Mark H. Overmars

1998-01-01

343

Analyzing the applicability of the least risk path algorithm in indoor space  

NASA Astrophysics Data System (ADS)

Over the last couple of years, applications that support navigation and wayfinding in indoor environments have become one of the booming industries. However, the algorithmic support for indoor navigation has so far been left mostly untouched, as most applications mainly rely on adapting Dijkstra's shortest path algorithm to an indoor network. In outdoor space, several alternative algorithms have been proposed adding a more cognitive notion to the calculated paths and as such adhering to the natural wayfinding behavior (e.g. simplest paths, least risk paths). The need for indoor cognitive algorithms is highlighted by a more challenged navigation and orientation due to the specific indoor structure (e.g. fragmentation, less visibility, confined areas…). Therefore, the aim of this research is to extend those richer cognitive algorithms to three-dimensional indoor environments. More specifically for this paper, we will focus on the application of the least risk path algorithm of Grum (2005) to an indoor space. The algorithm as proposed by Grum (2005) is duplicated and tested in a complex multi-story building. Several analyses compare shortest and least risk paths in indoor and in outdoor space. The results of these analyses indicate that the current outdoor least risk path algorithm does not calculate less risky paths compared to its shortest paths. In some cases, worse routes have been suggested. Adjustments to the original algorithm are proposed to be more aligned to the specific structure of indoor environments. In a later stage, other cognitive algorithms will be implemented and tested in both an indoor and combined indoor-outdoor setting, in an effort to improve the overall user experience during navigation in indoor environments.

Vanclooster, A.; Viaene, P.; Van de Weghe, N.; Fack, V.; De Maeyer, Ph.

2013-11-01

344

The Length of the Shortest Telomere as the Major Determinant of the Onset of Replicative Senescence  

PubMed Central

The absence of telomerase in many eukaryotes leads to the gradual shortening of telomeres, causing replicative senescence. In humans, this proliferation barrier constitutes a tumor suppressor mechanism and may be involved in cellular aging. Yet the heterogeneity of the senescence phenotype has hindered the understanding of its onset. Here we investigated the regulation of telomere length and its control of senescence heterogeneity. Because the length of the shortest telomeres can potentially regulate cell fate, we focus on their dynamics in Saccharomyces cerevisiae. We developed a stochastic model of telomere dynamics built on the protein-counting model, where an increasing number of protein-bound telomeric repeats shift telomeres into a nonextendable state by telomerase. Using numerical simulations, we found that the length of the shortest telomere is well separated from the length of the others, suggesting a prominent role in triggering senescence. We evaluated this possibility using classical genetic analyses of tetrads, combined with a quantitative and sensitive assay for senescence. In contrast to mitosis of telomerase-negative cells, which produces two cells with identical senescence onset, meiosis is able to segregate a determinant of senescence onset among the telomerase-negative spores. The frequency of such segregation is in accordance with this determinant being the length of the shortest telomere. Taken together, our results substantiate the length of the shortest telomere as being the key genetic marker determining senescence onset in S. cerevisiae.

Xu, Zhou; Duc, Khanh Dao; Holcman, David; Teixeira, Maria Teresa

2013-01-01

345

Mechanics of the crack path formation  

NASA Technical Reports Server (NTRS)

A detailed analysis of experimentally obtained curvilinear crack path trajectories formed in a heterogeneous stress field is presented. Experimental crack path trajectories were used as data for numerical simulations, recreating the actual stress field governing the development of the crack path. Thus, the current theories of crack curving and kinking could be examined by comparing them with the actual stress field parameters as they develop along the experimentally observed crack path. The experimental curvilinear crack path trajectories were formed in the tensile specimens with a hole positioned in the vicinity of a potential crack path. The numerical simulation, based on the solution of equivalent boundary value problems with the possible perturbations of the crack path, is presented here.

Rubinstein, Asher A.

1989-01-01

346

Mechanics of the crack path formation  

NASA Technical Reports Server (NTRS)

A detailed analysis of experimentally obtained curvilinear crack path trajectories formed in a heterogeneous stress field is presented. Experimental crack path trajectories were used as data for the numerical simulations, recreating the actual stress field governing the development of the crack path. Thus, the current theories of crack curving and kinking could be examined by comparing them with the actual stress field parameters as they develop along the experimentally observed crack path. The experimental curvilinear crack path trajectories were formed in the tensile specimens with a hole positioned in the vicinity of a potential crack path. The numerical simulation, based on the solution of equivalent boundary value problems with the possible perturbations of the crack path, is presented.

Rubinstein, Asher A.

1991-01-01

347

The mixture problem in computer mapping of terrain: Improved techniques for establishing spectral signature, atmospheric path radiance, and transmittance. [in Colorado  

NASA Technical Reports Server (NTRS)

The results of LANDSAT and Skylab research programs on the effects of the atmosphere on computer mapping of terrain include: (1) the concept of a ground truth map needs to be drastically revised; (2) the concept of training areas and test areas is not as simple as generally thought because of the problem of pixels that represent a mixture of terrain classes; (3) this mixture problem needs to be more widely recognized and dealt with by techniques of calculating spectral signatures of mixed classes, or by other methods; (4) atmospheric effects should be considered in computer mapping of terrain and in monitoring changes; and (5) terrain features may be used as calibration panels on the ground, from which atmospheric conditions can be determined and monitored. Results are presented of a test area in mountainous terrain of south-central Colorado for which an initial classification was made using simulated mixture-class spectral signatures and actual LANDSAT-1-MSS data.

Smedes, H. W.; Hulstrom, R. L.; Ranson, K. J.

1975-01-01

348

A hybrid genetic algorithm for the weight setting problem in OSPF\\/ISIS routing  

Microsoft Academic Search

Intradomain traffic engineering aims to make more effi- cient use of network resources within an autonomous system. Interior Gateway Protocols such as OSPF (Open Shortest Path First) and IS-IS (Intermediate System- Intermediate System) are commonly used to select the paths along which traffic is routed within an autonomous system. These routing protocols direct traffic based on link weights assigned by

Luciana S. Buriol; Mauricio G. C. Resende; Celso C. Ribeiro; Mikkel Thorup

2005-01-01

349

A Genetic Algorithm for the Weight Setting Problem in OSPF Routing  

Microsoft Academic Search

With the growth of the Internet, Internet Service Providers (ISPs) try to meet the increasing trac demand with new technology and improved utilization of existing resources. Routing of data packets can aect network utilization. Packets are sent along network paths from source to destination following a protocol. Open Shortest Path First (OSPF) is the most commonly used intra-domain Internet routing

M. Ericsson; Mauricio G. C. Resende; Panos M. Pardalos

2002-01-01

350

Randomized Query Processing in Robot Path Planning  

Microsoft Academic Search

The subject of this paper is the analysis of a randomized preprocessing scheme that has been used for query processing in robot path planning. The attractiveness of the scheme stems from its general applicability to virtually any path-planning problem, and its empirically observed success. In this paper we initiate a theoretical basis for explaining this empirical success. Under a simple

Lydia E. Kavraki; Jean-claude Latombe; Rajeev Motwani; Prabhakar Raghavan

1998-01-01

351

Outdoor Path Labeling Using Polynomial Mahalanobis Distance  

Microsoft Academic Search

Autonomous robot navigation in outdoor environ- ments remains a challenging and unsolved problem. A key issue is our ability to identify safe or navigable paths far enough ahead of the robot to allow smooth trajectories at acceptable speeds. Colour or texture-based labeling of safe path regions in image sequences is one way to achieve this far field prediction. A challenge

Gregory Z. Grudic; Jane Mulligan

2006-01-01

352

Finding a simple path with multiple must-include nodes  

Microsoft Academic Search

This paper presents an algorithm to find a simple path in the given network with multiple must-include nodes in the path. The problem of finding a path with must-include node(s) can be easily found in some special cases. However, in general, including multiple nodes in the simple path has been shown to be NP-Complete. This problem may arise in network

Hars Vardhan; Shreejith Billenahalli; Wanjun Huang; Miguel Razo; Arularasi Sivasankaran; Limin Tang; Paolo Monti; Marco Tacca; Andrea Fumagalli

2009-01-01

353

Maximum Flux Transition Paths of Conformational Change.  

PubMed

Given two metastable states A and B of a biomolecular system, the problem is to calculate the likely paths of the transition from A to B. Such a calculation is more informative and more manageable if done for a reduced set of collective variables chosen so that paths cluster in collective variable space. The computational task becomes that of computing the "center" of such a cluster. A good way to define the center employs the concept of a committor, whose value at a point in collective variable space is the probability that a trajectory at that point will reach B before A. The committor "foliates" the transition region into a set of isocommittors. The maximum flux transition path is defined as a path that crosses each isocommittor at a point which (locally) has the highest crossing rate of distinct reactive trajectories. This path is based on the same principle as the minimum resistance path of Berkowitz et al (1983), but it has two advantages: (i) the path is invariant with respect to a change of coordinates in collective variable space and (ii) the differential equations that define the path are simpler. It is argued that such a path is nearer to an ideal path than others that have been proposed with the possible exception of the finite-temperature string method path. To make the calculation tractable, three approximations are introduced, yielding a path that is the solution of a nonsingular two-point boundary-value problem. For such a problem, one can construct a simple and robust algorithm. One such algorithm and its performance is discussed. PMID:20890401

Zhao, Ruijun; Shen, Juanfang; Skeel, Robert D

2010-08-10

354

The shortest-graph method for calculation of the pair-correlation function in crystalline systems  

NASA Astrophysics Data System (ADS)

A new method for approximate calculation of the pair correlation function g(r) is proposed for crystalline systems of identical particles with isotropic interactions. The main idea of the method is to account for the relative delocalization of each node in g(r) by using only the shortest lattice graph between the given points, thus neglecting smaller contributions from other (non-shortest) graphs. By employing the Lennard-Jones and Yukawa crystalline systems as representative examples, it is shown that the proposed approach yields very good agreement with the results of molecular dynamics simulations up to the melting line. The approach can be useful in approximating the structure of simple crystals (in particular, of crystalline colloids and plasma crystals), and can also be generalized for systems with anisotropic interactions.

Yurchenko, Stanislav O.

2014-04-01

355

Path planning using a potential field representation  

Microsoft Academic Search

An approach to two-dimensional as well as three-dimensional findpath problems that divides each problem into two steps is presented. Rough paths are found based only on topological information. This is accomplished by assigning to each obstacle an artificial potential similar to electrostatic potential to prevent the moving object from colliding with the obstacles, and then locating minimum-potential valleys. The paths

Yong Koo Hwang; Narendra Ahuja

1988-01-01

356

Path Planning Through Variational Dynamic Programming  

Microsoft Academic Search

The path planning problem, i.e., the geometrical problem of finding a collision-free pathbetween two given configurations of a robot moving among obstacles, has been studied bymany authors in recent years. Several complete algorithms exist for robots with few degreesof freedom (DOF), but they are intractable for more than 4 DOF. In order to tackle problems inhigher dimensions, several heuristic approaches

Jérôme Barraquand; Pierre Ferbach

1994-01-01

357

Path integral analyses of the hydrogen atom  

SciTech Connect

The path integral analysis of the hydrogen atom problem are presented in this dissertation. The Green's function for the hydrogen atom is calculated exactly by the path integration. The scattering phase shifts are also expressed in terms of path integrals and evaluated for the Coulomb potential with or without additional modifying potentials. First, the hydrogen atom in two dimensions is treated by path integration in parabolic coordinates. Feynman's path integral for the hydrogen atom in R/sup 2/, which cannot be directly integrated, is reduced to the exactly solvable path integral for an oscillator in R/sup 2/. The reduction procedure consists of the path-dependent time rescaling and the Levi-Civita transformation from Cartesian to parabolic coordinates. A path-dependent scaling of the global time and a nonlinear transformation of global coordinated are not necessarily valid in a path integral. Therefore, the reduction procedure is applied to each well-defined short time integral. The two-dimensional problem is studied by both the Lagrangian and the Hamiltonian path integral. The exact results are obtained for the Green's function and the energy spectrum of the hydrogen atom in R/sup 2/. The reduction procedure is then generalized to solve the hydrogen atom in three dimensions. The same time scaling is adopted. Since the three-dimensional counterpart of the Levi-Cavita transformation does not exist, the Kustaanheimo-Steifel transformation, which maps Cartesian variables in R/sup 3/ into Cartesian variables in R/sup 4/, is modified to transform the Coulomb path integral into an oscillator in R/sup 4/. An extra dimension introduced for the transformation is eliminated after path integration. The Green's function and the energy spectrum are found for the hydrogen atom in R/sup 3/.

Ho, R.C.C.

1982-01-01

358

Planning Paths of Complete Coverage of an Unstructured Environment by a Mobile Robot  

Microsoft Academic Search

Much of the focus of the research effort in path planning for mobile robots has centred on the problem of finding a path from a start location to a goal location, while minimising one or more parameters such as length of path, energy consumption or journey time. A path of complete coverage is a planned path in which a robot

A. Zelinsky; R. A. Jarvis; J. C. Byrne; S. Yuta

1993-01-01

359

DISCUSS: Critical Path Analysis  

NSDL National Science Digital Library

This module, by Barrie Baker and Neville Hunt of Coventry University, introduces critical path analysis and addresses the following topics: Networks, Critical paths, Floats, Activity-on-node (AON) networks. Excel spreadsheets are used to provide examples and exercises.

Baker, Barrie; Hunt, Neville

2009-04-23

360

Path planning for UAVs  

Microsoft Academic Search

In this paper, a two step path-planning algorithm for UAVs is proposed. The algorithm generates a stealthy path through a set of enemy radar sites of known location, and provides an intuitive way to trade-off stealth versus path length. In the first step, a suboptimal rough-cut path is generated through the radar sites by constructing and searching a graph based

S. A. Bortoff; E. Hartford

2000-01-01

361

Implementations of routing algorithms for transportation networks  

Microsoft Academic Search

We discuss the generalization of the point-to-point (and single-source) shortest path problem to instances where the shortest path must satisfy a formal language constraint. We describe theoretical and experimental results on a generalization of Dijkstra's algorithm to finding regular-language-constrained shortest paths. This algorithm forms a model for single-source shortest paths and point-to-point problems that generalizes several previously published algorithms for

Chris Barrett; Keith Bisset; Martin Holzer; Goran Konjevod; Madhav Marathe; Dorothea Wagnerk

362

Path Set Selection in Mobile Ad Hoc Networks  

Microsoft Academic Search

Topological changes in mobile ad hoc networks frequently render routing paths unusable. Such recurrent path failures have detrimental effects on the network ability to support QoS-driven services. A promising technique for addressing this problem is to use multiple redundant paths between the source and the destination. However while multipath routing algorithms can tolerate network failures well their failure resilience only

Panagiotis Papadimitratos; E. G. Sirer; Z. J. Haas

2002-01-01

363

Real-time randomized path planning for robot navigation  

Microsoft Academic Search

Mobile robots often must find a trajectory to another position in their environment, subject to constraints. This is the problem of planning a path through a continuous domain Rapidly-exploring random trees (RRTs) are a recently developed representation on which fast continuous domain path planners can be based. In this work, we build a path planning system based on RRTs that

James Bruce; M. Veloso

2002-01-01

364

Deterministic technique of path summation  

SciTech Connect

A numerical method, based on the Euclidean path integral formulation of quantum mechanics, to evaluate the ground state energy and wave function of a quantum system is discussed. The method is illustrated in one-dimensional cases, and then applied to a two-body system interacting through central and tensor potentials. A detailed discussion of the deuteron problem with a realistic nuclear potential is given.

Rosa-Clot, M.; Taddei, S. (Dipartimento di Fisica, Universita degli Studi di Firenze and Istituto Nazionale di Fisica Nucleare, Sezione di Firenze, Largo Enrico Fermi 2, I-50125, Firenze (Italy))

1994-08-01

365

A global path planning approach for redundant manipulators  

NASA Technical Reports Server (NTRS)

A new approach for global path planning of redundant manipulators is proposed. It poses the path planning problem as a finite time nonlinear control problem. The solution is found by a Newton-Raphson type algorithm. This technique is capable of handling various goal task descriptions as well as incorporating both joint and task space constraints. The algorithm has shown promising preliminary results in planning joint path sequences for 3R and 4R planar robots to meet Cartesian tip tracking and goal endpoint planning. It is robust with respect to local path planning problems such as singularity considerations and local minimum problems. Repetitive joint path solutions for cyclic end-effector tasks are also generated. Eventual goals of this work include implementation on full spatial robots, as well as provision of an interface for supervisory input to aid in path planning for more complex problems.

Seereeram, Sanjeev; Wen, J.

1993-01-01

366

Path Relaxation: Path Planning for a Mobile Robot  

Microsoft Academic Search

Path Relaxation is a method of planning safe paths around obstacles for mobile robots. It works in two steps: a global grid starch that finds a rough path, followed by a local relaxation step that adjusts each node on the path to lower the overall path cost. The representation used by Path Relaxation allows an explicit tradeoff among length of

Charles E. Thorpe; L. Matthies

1984-01-01

367

Output-Sensitive Reporting of Disjoint Paths (Extended Abstract)  

Microsoft Academic Search

A k-path query on a graph consists of computing k vertex-disjoint paths between two given vertices of the graph, whenever they exist. In this paper, we study the problem of performing k-path queries, with k 3, in a graph G with n vertices. We denote with l the total length of the paths reported. For k 3, we present an

Giuseppe Di Battista; Roberto Tamassia; Luca Vismara

1996-01-01

368

Breakdown of the Coherent State Path Integral: Two Simple Examples  

SciTech Connect

We show how the time-continuous coherent state path integral breaks down for both the single-site Bose-Hubbard model and the spin-path integral. Specifically, when the Hamiltonian is quadratic in a generator of the algebra used to construct coherent states, the path integral fails to produce correct results following from an operator approach. As suggested by previous authors, we note that the problems do not arise in the time-discretized version of the path integral.

Wilson, Justin H.; Galitski, Victor [Joint Quantum Institute and Condensed Matter Theory Center, Department of Physics, University of Maryland, College Park, Maryland 20742-4111 (United States)

2011-03-18

369

Flight Path Control Equipment for Producing Curved Flight Path Profiles with Microwave Landing Systems.  

National Technical Information Service (NTIS)

The characteristics of a flight path control instrument for producing curved approach profiles and guidance along these profiles are presented. For safety reasons, steep noise abatement approaches must be flown along curved profiles. The problems of flyab...

G. Schaenzer

1974-01-01

370

Coordinated path planning for multiple robots  

Microsoft Academic Search

We present a new approach to the multi-robot path planning problem, where a number of robots are to change their positions through feasible motions in the same static environment. Rather than the usual decoupled planning, we use a coordinated approach. As a result we can show that the method is probabilistically complete, that is, any solvable problem will be solved

Petr Svestka; Mark H. Overmars

1998-01-01

371

Model Checking Almost All Paths Can Be Less Expensive Than Checking All Paths  

Microsoft Academic Search

We compare the complexities of the following two model checking problems: checking whether a linear-time formula is satisfied\\u000a by all paths (which we call universal model checking) and checking whether a formula is satisfied by almost all paths (which\\u000a we call fair model checking here). For many interesting classes of linear-time formulas, both problems have the same complexity:\\u000a for instance,

Matthias Schmalz; Hagen Völzer; Daniele Varacca

2007-01-01

372

Continuous-Discrete Path Integral Filtering  

Microsoft Academic Search

A summary of the relationship between the Langevin equation,\\u000aFokker-Planck-Kolmogorov forward equation (FPKfe) and the Feynman path integral\\u000adescriptions of stochastic processes relevant for the solution of the\\u000acontinuous-discrete filtering problem is provided in this paper. The practical\\u000autility of the path integral formula is demonstrated via some nontrivial\\u000aexamples. Specifically, it is shown that the simplest approximation of the

Bhashyam Balaji

2009-01-01

373

UAV Path Planning Using Evolutionary Algorithms  

Microsoft Academic Search

Evolutionary Algorithms have been used as a viable candidate to solve path planning problems effectively and provide feasible\\u000a solutions within a short time. In this work a Radial Basis Functions Artificial Neural Network (RBF-ANN) assisted Differential\\u000a Evolution (DE) algorithm is used to design an off-line path planner for Unmanned Aerial Vehicles (UAVs) coordinated navigation\\u000a in known static maritime environments. A

Ioannis K. Nikolos; Eleftherios S. Zografos; Athina N. Brintaki

2007-01-01

374

A streamlined search algorithm for path modifications of a safe robot manipulator  

Microsoft Academic Search

In recent years, the interest in human-robot interactions has added a new dimension to the on-line path planning problem by\\u000a requiring a method that guarantees a risk-free path. This paper presents a streamlined search algorithm for fast path modification.\\u000a The algorithm is formulated as an optimization problem that evaluates alternative paths nearby each obstacle. Each path is\\u000a evaluated based on

Nima Najmaei; Mehrdad R. Kermani

2010-01-01

375

Exploring the Interaction of Geometry and Search in Path Planning.  

National Technical Information Service (NTIS)

This thesis addressed the problem of developing path planning algorithms that are both efficient and well-behaved. The authors proposed a novel approach in which the authors solve a path planning problem by finding and solving an appropriate abstraction o...

D. J. Zhu

1992-01-01

376

Path Following Robot.  

National Technical Information Service (NTIS)

Given a desired path to be followed by a Robot, a set of commands must be given to the Robot joint servos so that the Robot Tip, or Endpoint, can follow that path. These commands must be synchronized in time and scaled so as to maintain accuracy in the pr...

S. G. Goodway

1987-01-01

377

Advanced Physics: Path Integral  

NSDL National Science Digital Library

A cursor is shown in an x-y graph. The cursor can be dragged around the graph and its path is marked as it is moved. The data are sent to a DataTable which shows x, y, and the value of the path integral, F.dl.

Christian, Wolfgang; Belloni, Mario

2006-01-19

378

At-Least Version of the Generalized Minimum Spanning Tree Problem: Optimization Through Ant Colony System and Genetic Algorithms  

NASA Technical Reports Server (NTRS)

The At-Least version of the Generalized Minimum Spanning Tree Problem (L-GMST) is a problem in which the optimal solution connects all defined clusters of nodes in a given network at a minimum cost. The L-GMST is NPHard; therefore, metaheuristic algorithms have been used to find reasonable solutions to the problem as opposed to computationally feasible exact algorithms, which many believe do not exist for such a problem. One such metaheuristic uses a swarm-intelligent Ant Colony System (ACS) algorithm, in which agents converge on a solution through the weighing of local heuristics, such as the shortest available path and the number of agents that recently used a given path. However, in a network using a solution derived from the ACS algorithm, some nodes may move around to different clusters and cause small changes in the network makeup. Rerunning the algorithm from the start would be somewhat inefficient due to the significance of the changes, so a genetic algorithm based on the top few solutions found in the ACS algorithm is proposed to quickly and efficiently adapt the network to these small changes.

Janich, Karl W.

2005-01-01

379

Operational transfer path analysis  

NASA Astrophysics Data System (ADS)

One of the tools used to study the NVH behaviour of a system is the transfer path analysis. It aims to identify the operational forces and the propagation paths of the vibrations and is especially interesting in the case when the system is composed of different subsystems. The classical techniques identify the transfer paths when the system is disassembled. This way one eliminates flanking transfer paths. Yet it is very time-consuming and the boundary conditions are not correct anymore. The presented method makes it possible to identify the transfer paths without disassembling the system. The advantages are that the overall testing time is reduced and that the real boundary conditions are present. In this article the theory will be reviewed and it will be validated using data generated by finite element simulations.

De Sitter, Gert; Devriendt, Christof; Guillaume, Patrick; Pruyt, Erik

2010-02-01

380

Path Relaxation: Path Planning for a Mobile Robot.  

National Technical Information Service (NTIS)

Path Relaxation is a method of planning safe paths around obstacles for mobile robots. It works in two steps: a global grid search that finds a rough path, followed by a local relaxation step that adjusts each node on the path to lower the overall path co...

C. E. Thorpe

1984-01-01

381

A Path Algorithm for Constrained Estimation  

PubMed Central

Many least-square problems involve affine equality and inequality constraints. Although there are a variety of methods for solving such problems, most statisticians find constrained estimation challenging. The current article proposes a new path-following algorithm for quadratic programming that replaces hard constraints by what are called exact penalties. Similar penalties arise in l1 regularization in model selection. In the regularization setting, penalties encapsulate prior knowledge, and penalized parameter estimates represent a trade-off between the observed data and the prior knowledge. Classical penalty methods of optimization, such as the quadratic penalty method, solve a sequence of unconstrained problems that put greater and greater stress on meeting the constraints. In the limit as the penalty constant tends to ?, one recovers the constrained solution. In the exact penalty method, squared penalties!are replaced by absolute value penalties, and the solution is recovered for a finite value of the penalty constant. The exact path-following method starts at the unconstrained solution and follows the solution path as the penalty constant increases. In the process, the solution path hits, slides along, and exits from the various constraints. Path following in Lasso penalized regression, in contrast, starts with a large value of the penalty constant and works its way downward. In both settings, inspection of the entire solution path is revealing. Just as with the Lasso and generalized Lasso, it is possible to plot the effective degrees of freedom along the solution path. For a strictly convex quadratic program, the exact penalty algorithm can be framed entirely in terms of the sweep operator of regression analysis. A few well-chosen examples illustrate the mechanics and potential of path following. This article has supplementary materials available online.

Zhou, Hua; Lange, Kenneth

2013-01-01

382

An attempt of microwave CT system which discriminates the transmission path by means of time domain measurement.  

PubMed

A microwave-based computed tomography system was developed based on a method that uses time domain measurement to determine the shortest path of propagation components between two antennas. The method calculates shortest path of propagation components by examining mixer output DC components, delivering similar precision as chirp-pulse microwave computed tomography. Because post-mixer signal processing need only concerns DC currents, the effects of overshoot characteristics of baseband filters and the like are removed, simplifying measurement. System circuit composition is also simplified, lowering system costs. This paper provides a theoretical framework for the method, an S-parameter verification of the theory, and an experimental verification using a basic hardware construction. Results showed a restored image from the measurement data, indicating the utility of the method for microwave imaging. PMID:22255201

Tamura, Mutsumi; Ogawa, Takahiro; Miyakawa, Michio

2011-01-01

383

Generic Equations for Constructing Smooth Paths Along Circles and Tangent Lines With Application to Airport Ground Paths  

NASA Technical Reports Server (NTRS)

The primary purpose of this publication is to develop a mathematical model to describe smooth paths along any combination of circles and tangent lines. Two consecutive circles in a path are either tangent (externally or internally) or they appear on the same (lateral) or opposite (transverse) sides of a connecting tangent line. A path may start or end on either a segment or circle. The approach is to use mathematics common to robotics to design the path as a multilink manipulator. This approach allows a hierarchical view of the problem and keeps the notation manageable. A user simply specifies a few parameters to configure a path. Necessary and sufficient conditions automatically ensure the consistency of the inputs for a smooth path. Two example runway exit paths are given, and an angle to go assists in knowing when to switch from one path element to the next.

Barker, L. Keith

1998-01-01

384

Triaging the right patient to the right place in the shortest time.  

PubMed

Trauma systems have been successful in saving lives and preventing disability. Making sure that the right patient gets the right treatment in the shortest possible time is integral to this success. Most trauma systems have not fully developed trauma triage to optimize outcomes. For trauma triage to be effective, there must be a well-developed pre-hospital system with an efficient dispatch system and adequately resourced ambulance system. Hospitals must have clear designations of the level of service provided and agreed protocols for reception of patients. The response within the hospital must be targeted to ensure the sickest patients get an immediate response. To enable the most appropriate response to trauma patients across the system, a well-developed monitoring programme must be in place to ensure constant refinement of the clinical response. This article gives a brief overview of the current approach to triaging trauma from time of dispatch to definitive treatment. PMID:24961786

Cameron, P A; Gabbe, B J; Smith, K; Mitra, B

2014-08-01

385

Critical-Path-whitepaper  

Cancer.gov

NEGOTIATING THE CRITICAL PATH..................................................................................................7 SCIENTIFIC AND TECHNICAL DIMENSIONS ALONG THE CRITICAL PATH...................................9 A BETTER PRODUCT DEVELOPMENT TOOLKIT IS URGENTLY NEEDED ..................................11 TOOLS FOR ASSESSING SAFETY......................................................................................................16 Towards a Better Safety Toolkit................................................................................................17 Getting to the Right Safety Standards......................................................................................20 TOOLS FOR DEMONSTRATING MEDICAL UTILITY .......................................................................20 Towards a Better Effectiveness Toolkit ...................................................................................21 Getting to the Right Effectiveness Standards .........................................................................25 TOOLS FOR CHARACTERIZATION AND MANUFACTURING .........................................................25 Towards a Better Manufacturing Toolkit.................................................................................27 Getting to the Right Manufacturing Standards .......................................................................28 A PATH FORWARD .............................................................................................................................29 The Orphan Products Grant Program.

386

Practical path planning among movable obstacles  

SciTech Connect

Path planning among movable obstacles is a practical problem that is in need of a solution. In this paper an efficient heuristic algorithm that uses a generate-and-test paradigm: a good'' candidate path is hypothesized by a global planner and subsequently verified by a local planner. In the process of formalizing the problem, we also present a technique for modeling object interactions through contact. Our algorithm has been tested on a variety of examples, and was able to generate solutions within 10 seconds. 5 figs., 27 refs.

Chen, Pang C.; Hwang, Yong K.

1990-09-05

387

Using Dynamic Geometry Software to Convey Real-World Situations into the Classroom: The Experience of Student Mathematics Teachers with a Minimum Network Problem  

ERIC Educational Resources Information Center

As any ordinary person knows, the shortest distance between two points is a straight line. What, then, is the shortest distance between three points? Four points? The study reported in this article deals with the observed actions of Turkish student mathematics teachers as they were working with minimal network problems. Having analysed the…

Guven, Bulent

2008-01-01

388

Breast Contour Detection with Stable Paths  

NASA Astrophysics Data System (ADS)

Breast cancer conservative treatment (BCCT), due to its proven oncological safety, is considered, when feasible, the gold standard of breast cancer treatment. However, aesthetic results are heterogeneous and difficult to evaluate in a standardized way, due to the lack of reproducibility of the subjective methods usually applied. The objective assessment methods, considered in the past as being less capable of evaluating all aspects of BCCT, are nowadays being preferred to overcome the drawbacks of the subjective evaluation. A computer-aided medical system was recently developed to objectively and automatically evaluate the aesthetic result of BCCT. In this system, the detection of the breast contour on the patient's digital photograph is a necessary step to extract the features subsequently used in the evaluation process. In this paper an algorithm based on the shortest path on a graph is proposed to detect automatically the breast contour. The proposed method extends an existing semi-automatic algorithm for the same purpose. A comprehensive comparison with manually-drawn contours reveals the strength of the proposed method.

Cardoso, Jaime S.; Sousa, Ricardo; Teixeira, Luís F.; Cardoso, M. J.

389

Critical Path Method Reports.  

National Technical Information Service (NTIS)

The computer system for the Critical Path Method Reports consists of three programs. The programs are CPM Calculation, CPM Calendar Dating and CPM Time-Sequence Plot. The CPM Calculations Program is used for doing the arithmetic calculations associated wi...

R. C. Tennent

1964-01-01

390

Tortuous path chemical preconcentrator  

DOEpatents

A non-planar, tortuous path chemical preconcentrator has a high internal surface area having a heatable sorptive coating that can be used to selectively collect and concentrate one or more chemical species of interest from a fluid stream that can be rapidly released as a concentrated plug into an analytical or microanalytical chain for separation and detection. The non-planar chemical preconcentrator comprises a sorptive support structure having a tortuous flow path. The tortuosity provides repeated twists, turns, and bends to the flow, thereby increasing the interfacial contact between sample fluid stream and the sorptive material. The tortuous path also provides more opportunities for desorption and readsorption of volatile species. Further, the thermal efficiency of the tortuous path chemical preconcentrator is comparable or superior to the prior non-planar chemical preconcentrator. Finally, the tortuosity can be varied in different directions to optimize flow rates during the adsorption and desorption phases of operation of the preconcentrator.

Manginell, Ronald P. (Albuquerque, NM); Lewis, Patrick R. (Albuquerque, NM); Adkins, Douglas R. (Albuquerque, NM); Wheeler, David R. (Albuquerque, NM); Simonson, Robert J. (Cedar Crest, NM)

2010-09-21

391

A Path to Discovery  

ERIC Educational Resources Information Center

The path taken and the turns made as a turtle traces a polygon are examined to discover an important theorem in geometry. A unique tool, the Angle Adder, is implemented in the investigation. (Contains 9 figures.)

Stegemoller, William; Stegemoller, Rebecca

2004-01-01

392

Follow the Paths  

NSDL National Science Digital Library

In this lesson, younger students will be introduced to the various orbital paths that are used for satellites. Using a globe and a satellite model or a large picture of Earth, the teacher will introduce three types of orbital paths (polar, elliptical, and geosynchronous). The students should be able to define 'satellite', define the three types of orbits, describe how satellites orbit the Earth, and understand how they are slowed down by drag from the atmosphere.

393

Mobile robot path planning based on shuffled frog leaping optimization algorithm  

Microsoft Academic Search

Mobile robot path planning is a nondeterministic polynomial time (NP) problem, traditional optimization methods are not very effective to it, which are easy to plunge into local minimum. In this paper, we devise an evolutionary algorithm to solve the robot path planning problem. In the present work, we propose a method of robot path planning in partially unknown environments based

I. Hassanzadeh; K. Madani; M. A. Badamchizadeh

2010-01-01

394

Spatial fingerprint of quantum path interferences in high order harmonic generation.  

PubMed

We have spatially and spectrally resolved the high order harmonic emission from an argon gas target. Under proper phase matching conditions we were able to observe for the first time the spatial fine structure originating from the interference of the two shortest quantum paths in the harmonic beam. The structure can be explained by the intensity-dependent harmonic phase of the contributions from the two paths. The spatially and spectrally resolved measurements are consistent with previous spatially integrated results. Our measurement method represents a new tool to clearly distinguish between different interference effects and to potentially observe higher order trajectories in the future with improved detection sensitivity. Here, we demonstrate additional experimental evidence that the observed interference pattern is only due to quantum-path interferences and cannot be explained by a phase modulation effect. Our experimental results are fully supported by simulations using the strong field approximation and including propagation. PMID:20174127

Schapper, F; Holler, M; Auguste, T; Zaïr, A; Weger, M; Salières, P; Gallmann, L; Keller, U

2010-02-01

395

Path Integration in Desert Ants, Cataglyphis fortis  

Microsoft Academic Search

Foraging desert ants, Cataglyphis fortis, continually keep track of their own positions relative to home--i.e., integrate their tortuous outbound routes and return home along straight (inbound) routes. By experimentally manipulating the ants' outbound trajectories we show that the ants solve this path integration problem not by performing a true vector summation (as a human navigator does) but by employing a

Martin Muller; Rudiger Wehner

1988-01-01

396

Logic systems for path delay test generation  

Microsoft Academic Search

The authors present an algorithmic derivation of logic systems for solving path delay test problems. In these logic systems, the state of a signal represents any possible situation that can occur during two consecutive vectors. Starting from a set of valid input states, a state transition graph is constructed to enumerate all possible states produced by Boolean gates. Specifics of

Soumitra Bose; Prathima Agrawal; Vishwani D. Agrawal

1993-01-01

397

Exhaustive path tracing with Paris traceroute  

Microsoft Academic Search

Traceroute [2] is used to learn the path between two machines in the internet. Uses range from the diagnosis of network problems to the assemblage of internet maps. Unfortunately, traceroute measurements can be inaccurate and incomplete when the measured route traverses a load balancer.

Brice Augustin; Timur Friedman; Renata Teixeira

2006-01-01

398

Applications of Path Compression on Balanced Trees  

Microsoft Academic Search

Several fast algorithms are presented for computing functions defined on paths in trees under various assumpuons. The algorithms are based on tree mampulatton methods first used to efficiently represent equivalence relations. The algorithms have O((m + n)a(m + n, n)) running tunes, where m and n are measures of the problem size and a Is a functional reverse of Ackermann's

Robert Endre Tarjan

1979-01-01

399

Fastest Mixing Markov Chain on a Path  

Microsoft Academic Search

We consider the problem of assigning transition probabilities to the edges of a path in such a way that the resulting Markov chain or random walk mixes as rapidly as possible. In this note we prove that fastest mixing is obtained when each edge has a transition probability of 1=2. Although this result is intuitive (it was conjectured in (6))

Stephen Boyd; Persi Diaconis; Jun Sun; Lin Xiao

2004-01-01

400

Sweep Algorithm in Vehicle Routing Problem For Public Transport  

Microsoft Academic Search

This paper investigates the capability of Sweep Algorithm in solving the vehicle routing problem for public transport The Sweep Algorithm is firstly introduced as a method to search shortest route in the vehicle routing problem. In order to evaluate the result of the algorithm, current routes profile of a public transport is presented. An application is constructed based on the

GUNADI W. NURCAHYO; ROSE ALINDA ALIAS

2002-01-01

401

Real-Time Optimal Path Planning Using a Distributed Computing Paradigm  

Microsoft Academic Search

Path planning may be viewed as an optimal control problem which can be addressed using dynamic programming. The optimal control (i.e. path) is obtained after solving Bellman's dynamic programming equation for an \\

Michael Lemmon

1991-01-01

402

Molecular definition of the shortest region of deletion overlap in the Langer-Giedion syndrome  

PubMed Central

The Langer-Giedion syndrome (LGS), which is characterized by craniofacial dysmorphism and skeletal abnormalities, is caused by a genetic defect in 8q24.1. We have used 13 anonymous DNA markers from an 8q24.1-specific microdissection library, as well as c-myc and thyroglobulin gene probes, to map the deletion breakpoints in 16 patients with LGS. Twelve patients had a cytogenetically visible deletion, two patients had an apparently balanced translocation, and two patients had an apparently normal karyotype. In all cases except one translocation patient, loss of genetic material was detected. The DNA markers fall into 10 deletion intervals. Clone L48 (D8S51) defines the shortest region of deletion overlap (SRO), which is estimated to be less than 2 Mbp. Three clones–pl7-2.3EE (D8S43), L24 (D8S45), and L40 (D8S49)–which flank the SRO recognize evolutionarily conserved sequences. ImagesFigure 1Figure 3Figure 4

Ludecke, Hermann-Josef; Johnson, Carey; Wagner, Michael J.; Wells, Dan E.; Turleau, Catherine; Tommerup, Niels; Latos-Bielenska, Anna; Sandig, Klaus-Rainer; Meinecke, Peter; Zabel, Bernhard; Horsthemke, Bernhard

1991-01-01

403

Multifaceted Learning Paths Recommendation Via Semantic Linked Network  

Microsoft Academic Search

Cognition overload is one of the major problems in current self-learning intelligent learning systems. Providing learners with the personalized learning path can effectively smooth over users' learning disorientation. In this paper, we propose a multi-faceted recommendation framework that provides learners with personalized learning paths based on their different learning styles. Building the recommendation system mainly involves the following three steps:

Juan Yang; Zhixing Huang; Hongtao Liu

2010-01-01

404

Following straight line and orbital paths with input constraints  

Microsoft Academic Search

This paper considers the problem of fixed wing unmanned air vehicles following straight lines and orbits. To account for ambient winds, we use a path following approach as opposed to trajectory tracking. The unique feature of this paper is that we explicitly account for roll angle constraints and flight path angle constraints. The guidance laws are derived using the theory

Randal W. Beard; Jeffrey Humpherys

2011-01-01

405

Mission Path Following for an Autonomous Unmanned Airship  

Microsoft Academic Search

The development of an unmanned airship capable of autonomous flight over user-defined locations for aerial data and imagery acquisition is the objective of the AURORA project. One important mission problem is the flight path following of the vehicle through a set of pre-defined points at a given altitude and velocity. In this article, a path tracking error generation methodology is

Jose Raul Azinheira; E. Carneiro de Paiva; Josué Jr. Guimarães Ramos; Samuel Siqueira Bueno

2000-01-01

406

Optimal path planning for unmanned air vehicles with kinematic and tactical constraints  

Microsoft Academic Search

We consider a class of 2D optimal path-planning problems for unmanned air vehicles (UAVs) with kinematic and tactical constraints. The existence of an optimal path class satisfying the UAV kinematic constraints and vector calculus are exploited to reduce this class of optimal path-planning problems to a parameter optimization problem. Illustrative tactical constraints arising in target touring and obstacle avoidance problems

Guang Yang; Vikram Kapila

2002-01-01

407

Path planning for everday robotics with SANDROS  

SciTech Connect

We discuss the integration of the SANDROS path planner into a general robot simulation and control package with the inclusion of a fast geometry engine for distance calculations. This creates a single system that allows the path to be computed, simulated, and then executed on the physical robot. The architecture and usage procedures are presented. Also, we present examples of its usage in typical environments found in our organization. The resulting system is as easy to use as the general simulation system (which is in common use here) and is fast enough (example problems are solved in seconds) to be used interactively on an everyday basis.

Watterberg, P.; Xavier, P. [Sandia National Labs., Albuquerque, NM (United States); Hwang, Y. [Korea Inst. of Science and Technology, Seoul (Korea, Republic of)

1997-02-01

408

Uma Nova Abordagem para o Cálculo do Caminho Mais Curto com uma Restrição Adicional Baseada no Método NISE Bi-objectivo  

Microsoft Academic Search

The Shortest Path problem (SP) is one of the most important sub-problems related with real networks. This problem has been strongly studied and we can find in literature numerous algorithms that solve it in polynomial time. However, if an additional constraint is considered in the SP problem, the new problem, known as the Constrained Shortest Path problem (CSP), is at

Luís Santos; João Coutinho-Rodrigues

409

Following the Path  

ERIC Educational Resources Information Center

This article profiles Diane Stanley, an author and illustrator of children's books. Although she was studying to be a medical illustrator in graduate school, Stanley's path changed when she got married and had children. As she was raising her children, she became increasingly enamored of the colorful children's books she would check out of the…

Rodia, Becky

2004-01-01

410

Path to the Profession  

ERIC Educational Resources Information Center

A growing number of institutions are being more deliberate about bringing in fundraisers who fit the culture of the development department and about assessing skills and providing training that fill specific needs. Development shops are paying more attention to cultivating their staffs, staying attuned to employees' needs and creating career paths

Coleman, Toni

2012-01-01

411

Gas path seal  

NASA Technical Reports Server (NTRS)

A gas path seal suitable for use with a turbine engine or compressor is described. A shroud wearable or abradable by the abrasion of the rotor blades of the turbine or compressor shrouds the rotor bades. A compliant backing surrounds the shroud. The backing is a yieldingly deformable porous material covered with a thin ductile layer. A mounting fixture surrounds the backing.

Bill, R. C.; Johnson, R. D. (inventors)

1979-01-01

412

An Unplanned Path  

ERIC Educational Resources Information Center

The authors elucidate what they saw as three important challenges to overcome along the path to becoming elementary school mathematics teacher leaders: marginal interest in math, low self-confidence, and teaching in isolation. To illustrate how these challenges were mitigated, they focus on the stories of two elementary school teachers--Laura and…

McGarvey, Lynn M.; Sterenberg, Gladys Y.; Long, Julie S.

2013-01-01

413

CareerPath  

NSDL National Science Digital Library

CareerPath offers a searchable index of employment ads from six major newspapers: The Boston Globe, Chicago Tribune, Los Angeles Times, The New York Times, The San Jose Mercury News, and The Washington Post. The total ads available on October 21 was 21,442. The site is attractive and easy to use.

414

Stochastic Evolutionary Algorithms for Planning Robot Paths  

NASA Technical Reports Server (NTRS)

A computer program implements stochastic evolutionary algorithms for planning and optimizing collision-free paths for robots and their jointed limbs. Stochastic evolutionary algorithms can be made to produce acceptably close approximations to exact, optimal solutions for path-planning problems while often demanding much less computation than do exhaustive-search and deterministic inverse-kinematics algorithms that have been used previously for this purpose. Hence, the present software is better suited for application aboard robots having limited computing capabilities (see figure). The stochastic aspect lies in the use of simulated annealing to (1) prevent trapping of an optimization algorithm in local minima of an energy-like error measure by which the fitness of a trial solution is evaluated while (2) ensuring that the entire multidimensional configuration and parameter space of the path-planning problem is sampled efficiently with respect to both robot joint angles and computation time. Simulated annealing is an established technique for avoiding local minima in multidimensional optimization problems, but has not, until now, been applied to planning collision-free robot paths by use of low-power computers.

Fink, Wolfgang; Aghazarian, Hrand; Huntsberger, Terrance; Terrile, Richard

2006-01-01

415

NLTT 5306: the shortest period detached white dwarf+brown dwarf binary  

NASA Astrophysics Data System (ADS)

We have spectroscopically confirmed a brown dwarf mass companion to the hydrogen atmosphere white dwarf NLTT 5306. The white dwarf's atmospheric parameters were measured using the Sloan Digital Sky Survey and X-shooter spectroscopy as Teff = 7756 ± 35 K and log(g) = 7.68 ± 0.08, giving a mass for the primary of MWD = 0.44 ± 0.04 M? at a distance of 71 ± 4 pc with a cooling age of 710 ± 50 Myr. The existence of the brown dwarf secondary was confirmed through the near-infrared arm of the X-shooter data and a spectral type of dL4-dL7 was estimated using standard spectral indices. Combined radial velocity measurements from the Sloan Digital Sky Survey, X-shooter and the Hobby-Eberly Telescope's High Resolution Spectrograph of the white dwarf give a minimum mass of 56 ± 3 MJup for the secondary, confirming the substellar nature. The period of the binary was measured as 101.88 ± 0.02 min using both the radial velocity data and i'-band variability detected with the Isaac Newton Telescope. This variability indicates `day' side heating of the brown dwarf companion. We also observe H? emission in our higher resolution data in phase with the white dwarf radial velocity, indicating that this system is in a low level of accretion, most likely via a stellar wind. This system represents the shortest period white dwarf+brown dwarf binary and the secondary has survived a stage of common envelope evolution, much like its longer period counterpart, WD 0137-349. Both systems likely represent bona fide progenitors of cataclysmic variables with a low-mass white dwarf and a brown dwarf donor.

Steele, P. R.; Saglia, R. P.; Burleigh, M. R.; Marsh, T. R.; Gänsicke, B. T.; Lawrie, K.; Cappetta, M.; Girven, J.; Napiwotzki, R.

2013-03-01

416

AH Cam: A metal-rich RR Lyrae star with the shortest known Blazhko period  

NASA Technical Reports Server (NTRS)

Analysis of 746 new V-band observations of the RR Lyrae star AH Cam obtained during 1989 - 1992 clearly show that its light curve cannot be described by a single period. In fact, at first glance, the Fourier spectrum of the photometry resembles that of a double-mode pulsator, with peaks at a fundamental period of 0.3686 d and an apparent secondary period of 0.2628 d. Nevertheless, the dual-mode solution is a poor fit to the data. Rather, we believe that AH Cam is a single-mode RR Lyrae star undergoing the Blazhko effect: periodic modulation of the amplitude and shape of its light curve. What was originally taken to be the period of the second mode is instead the 1-cycle/d alias of a modulation sidelobe in the Fourier spectrum. The data are well described by a modulation period of just under 11 d, which is the shortest Blazhko period reported to date in the literature and confirms the earlier suggestion by Goranskii. A low-resolution spectrum of AH Cam indicates that it is relatively metal rich, with delta-S less than or = 2. Its high metallicity and short modulation period may provide a critical test of at least one theory for the Blazhko effect. Moskalik's internal resonance model makes specific predictions of the growth rate of the fundamental model vs fundamental period. AH Cam falls outside the regime of other known Blazhko variables and resonance model predictions, but these are appropriate for metal-poor RR Lyrae stars. If the theory matches the behavior of AH Cam for a metal-rich stellar model, this would bolster the resonance hypothesis.

Smith, Horace A.; Matthews, Jaymie M.; Lee, Kevin M.; Williams, Jeffrey; Silbermann, N. A.; Bolte, Michael

1994-01-01

417

Ad-Hoc Analysis of Synop Observations to enhance shortest-term wind power predictions  

NASA Astrophysics Data System (ADS)

Shortest term wind power predictions with forecast horizons less than 12 hours benefit from observed data. So comparison between Synop observations and numerical weather predictions can serve as assessment of the available forecasts. This ad-hoc analysis depends very much on the observed data whose spatial distribution is very patchy in some areas. A powerful interpolation method helps to create a correct representation of the observed fields. The Kriging method finds a correlation function which describes the variation of the spatial field best. An unknown data point is estimated by weighted observation points, taking distance and clustering effects into account. We use mean sea level pressure data measured at Synop and ship stations in Europe and the Atlantic to assess the quality of the predicted mean sea level pressure from Numerical Weather Prediction models. Those models serve as base of wind power predictions and influence the prediction error considerably. If this error can be estimated, a rating of different Numerical Weather Prediction Models which are taken into consideration can follow. The choice of the area that represents the area of interest in terms of prediction errors depend on the moving direction of the low pressure systems. First calculations show that errors of the ad-hoc analysis are in good agreement with the ECMWF analysis. The evaluation of the ad-hoc analysis in an area over Great Britain/North Sea and the comparison with available ECMWF forecasts over Germany reveals phase shifts for some time intervals. This supports the assumption of moving prediction errors along low pressure systems.

Busch-Saleck, N.; von Bremen, L.

2010-09-01

418

Small flow rate can supply inwardly migrating shortest-period planets  

NASA Astrophysics Data System (ADS)

The number of exoplanets found with periods as short as one day and less was surprising given how fast these planets had been expected to migrate into the star due to the tides raised on the star by planets at such close distances. It has been seen as improbable that we would find planets in such a small final fraction of their lives [1]. The favored solution has been that the tidal dissipation is much weaker than expected, which would mean that the final infall would be a larger fraction of the planets' life. We find no reason, however, to exclude the explanation that a small number of planets are continuously sent migrating inwards such that these planets indeed are in the last fraction of their lives. Following the observation that the distribution of medium planets disfavors tidal dissipation being significantly weaker than has been found from observations of binary stars [2], we now show that the numbers of planets in such a "flow" of excess planets migrating inwards is low enough that even depletion of the three-day pileup is a plausible source. Then the shortest period occurrence distribution would be shaped by planets continuously being sent into the star, which may explain the depletion of the pileup in the Kepler field relative to the solar neighborhood [3]. Because Kepler observes above the galactic plan, [3] suggested the Kepler field may include an older population of stars. The tidal dissipation strength in stars due to giant planets may be not greatly weaker than it is in binary stars.

Taylor, S. F.

2013-04-01

419

Optimal flow path design of unidirectional AGV systems  

Microsoft Academic Search

This paper describes an alternative formulation of the AGV flow path layout (FPL) problem which was first formulated by Gaskins and Tanchoco (1987) as a zero-one integer programming problem. A computationally efficient procedure is proposed which is based on the branch-and-bound technique. An algorithm for satisfying the reachability condition for nodes in the AGV flow path network is also presented.

MOSHE KASPI; J. M. A. TANCHOCO

1990-01-01

420

Handbook for the Estimation of Microwave Propagation Effects: Link Calculations for Earth-Space Paths (Path Loss and Noise Estimation).  

National Technical Information Service (NTIS)

A single model for a standard of comparison for other models when dealing with rain attenuation problems in system design and experimentation is proposed. Refinements to the Global Rain Production Model are incorporated. Path loss and noise estimation pro...

R. K. Crane D. W. Blood

1979-01-01

421

Transhorizon cochannel interference path measurements in Europe  

NASA Astrophysics Data System (ADS)

Existing methods for predicting co-channel interference levels are very inadequate, and development of these methods has been severely limited by the lack of suitable data. There are particular problems within Europe because there is a wide range of climatic and geographical conditions. COST Project 210 was set up to provide suitable data and prediction methods. The prime objective is to develop and evaluate models to serve as a basis for frequency planning co-ordination procedures and interference calculations, in order to improve the organization of further radio communication systems within Europe. After giving an up-to-date statement on the COST 210 activities set out above, early results obtained from three representative areas of study are given: (1) statistics of high signal level, and case studies, essentially in clear-air conditions, on paths of 150 to 300 km from France to the U.K. (in collaboration with CNET (Paris), CNET (Lannion), Portsmouth Polytechnic, IBA and RSGB); (2) hydrometeor scatter studies using a 10 cm wavelength dual-polarization radar at RAL, where a radar-derived raincell database is being used to simulate interference paths and to examine relative effects of ice and rain, etc; and (3) hydrometeor scatter statistics and case studies on a 131 km overland path (in collaboration with DTI), and a 48 km overland path, both in conjunction with the radar mentioned above, and two oversea paths of 201 and 302 km (in collaboration with CNET).

Hall, Martin P. M.

1988-12-01

422

Lander flight path analysis  

NASA Technical Reports Server (NTRS)

The primary functions of the Lander Flight Path Analysis Team (LFPAT) were to (1) design the Viking Lander (VL) descent trajectory and compute the descent guidance parameters for command transmission to the Viking Lander and Viking Orbiter (VO), (2) reconstruct the VL trajectory from separation to touchdown using data transmitted from the VL to Earth via the VO during descent, and (3) predict the VL/VO relay link system performance during descent and post touchdown. The preflight VL capability, the history of proposed descent trajectory designs as the site selection process evolved, and the final trajectory design and guidance parameters for each vehicle are addressed along with the trajectory reconstruction process, including the overall reconstructed VL flight path summary and a detailed discussion of the entry trajectory and atmosphere reconstruction results. The postland relay link prediction function is discussed.

Euler, E. A.; Adams, G. L.; Hopper, F. W.

1979-01-01

423

Use of a Colony of Cooperating Agents and MAPLE To Solve the Traveling Salesman Problem.  

ERIC Educational Resources Information Center

This paper reviews an approach for finding optimal solutions to the traveling salesman problem, a well-known problem in combinational optimization, and describes implementing the approach using the MAPLE computer algebra system. The method employed in this approach to the problem is similar to the way ant colonies manage to establish shortest

Guerrieri, Bruno

424

Ant Colony Optimization for the Single Vehicle Pickup and Delivery Problem with Time Window  

Microsoft Academic Search

The single vehicle pickup and delivery problem with time window (1-PDPTW) is an important class of vehicle routing problem. This problem aims to find a shortest route for a single vehicle to deliver objects from origin to destination, subject to load limit and time window of delivery. This study develops an ant colony optimization (ACO) method for the 1-PDPTW. Specifically,

Yu-Hsuan Huang; Chuan-Kang Ting

2010-01-01

425

Quantum Measurement and Extended Feynman Path Integral  

NASA Astrophysics Data System (ADS)

Quantum measurement problem has existed many years and inspired a large of literature in both physics and philosophy, but there is still no conclusion and consensus on it. We show it can be subsumed into the quantum theory if we extend the Feynman path integral by considering the relativistic effect of Feynman paths. According to this extended theory, we deduce not only the Klein-Gordon equation, but also the wave-function-collapse equation. It is shown that the stochastic and instantaneous collapse of the quantum measurement is due to the “potential noise" of the apparatus or environment and “inner correlation" of wave function respectively. Therefore, the definite-status of the macroscopic matter is due to itself and this does not disobey the quantum mechanics. This work will give a new recognition for the measurement problem.

Wen, Wei; Bai, Yan-Kui

2012-06-01

426

All-Electron Path Integral Monte Carlo Simulations of Small Atoms and Molecules  

Microsoft Academic Search

Imaginary-time Feynman path integrals describe quantum mechanics at finite temperatures. Monte Carlo simulations using path integrals have many ap- plications to nanoscale physics. Fermions introduce negative terms in the partition function, which we remove with a fixed-node approximation. In this article, we give an introduction to path integral Monte Carlo simulations. We focus on a difficult problem: the direct application

J. Shumway

427

Blurring of Light due to Multiple Scattering by Participating Medium: A Path Integral Approach  

Microsoft Academic Search

Volumetric light transport effects are significant for many materials like skin, smoke, clouds or water. In particular, one must consider the multiple scat tering of light within the volume. Recently, we presented a path integral-based approach to this problem which identifies the most probable path light takes in the medium and approximates energy transport over all paths by only those

Michael Ashikhmin; Simon Premoze; Ravi Ramamoorthi; Shree Nayar

428

Variational Approach to Search and Path Planning Using Level Set Methods.  

National Technical Information Service (NTIS)

In this paper we propose a variational approach to a path planning problem in 2 dimensions using a level set framework. After defining an energy integral over the path, we use gradient flow on the defined energy and evolve the entire path until a locally ...

T. Cecil D. Marthaler

2004-01-01

429

Deep Space Formation Flying Spacecraft Path Planning  

Microsoft Academic Search

Efficient algorithms for collision-free energy sub-optimal path plan- ning for formations of spacecraft flying in deep space are presented. The idea is to introduce a set of way-points through which the space- craft are required to pass, combined with parameterizations of the trajectories which are energy-optimal for each spacecraft. The re- sulting constrained optimization problem is formulated as a quasi-

Cornel Sultan; Sanjeev Seereeram; Raman K. Mehra

2007-01-01

430

Pick-a-Path  

NSDL National Science Digital Library

This mobile app (available for both iOS and Android devices) was developed by the National Council of Teachers of Mathematics with funding from Verizon Foundation. The app is based on the Decimal Maze from the popular lesson "Too Big or Too Small". The goal is to help Okta reach the target (maximum, minimum, or a specific value) by choosing a path from the top of the maze to the bottom â adding, subtracting, multiplying and dividing as the player goes. Seven levels with seven puzzles in each level test the player's skills with operation with powers of ten, negative numbers, fractions, decimals, and exponents.

2012-01-01

431

Byrds Flight Path  

NSDL National Science Digital Library

The Ohio State Universitys Library web site notes As a navigational aviator, Byrd pioneered in the technology that would be the foundation for modern polar exploration and investigation. As a decorated and much celebrated hero, Byrd drew popular attention to areas of the world that became focal points of scientific investigation in numerous disciplines. More information about Admiral Richard E. Byrd can be found at (http:--www.lib.ohio-state.edu-arvweb-polar-byrd-byrd.htm). The next animation, #1001, shows Byrds plane as it follows the flight path presented in this animation.

Biddlecome, Tom; Snodgrass, Stuart; Newcombe, Marte; Jezek, Ken

1999-11-08

432

Portage and Path Dependence*  

PubMed Central

We examine portage sites in the U.S. South, Mid-Atlantic, and Midwest, including those on the fall line, a geomorphological feature in the southeastern U.S. marking the final rapids on rivers before the ocean. Historically, waterborne transport of goods required portage around the falls at these points, while some falls provided water power during early industrialization. These factors attracted commerce and manufacturing. Although these original advantages have long since been made obsolete, we document the continuing importance of these portage sites over time. We interpret these results as path dependence and contrast explanations based on sunk costs interacting with decreasing versus increasing returns to scale.

Bleakley, Hoyt; Lin, Jeffrey

2012-01-01

433

JAVA PathFinder  

NASA Technical Reports Server (NTRS)

JPF is an explicit state software model checker for Java bytecode. Today, JPF is a swiss army knife for all sort of runtime based verification purposes. This basically means JPF is a Java virtual machine that executes your program not just once (like a normal VM), but theoretically in all possible ways, checking for property violations like deadlocks or unhandled exceptions along all potential execution paths. If it finds an error, JPF reports the whole execution that leads to it. Unlike a normal debugger, JPF keeps track of every step how it got to the defect.

Mehhtz, Peter

2005-01-01

434

Nonoptimal Component Placement, but Short Processing Paths, due to Long-Distance Projections in Neural Systems  

PubMed Central

It has been suggested that neural systems across several scales of organization show optimal component placement, in which any spatial rearrangement of the components would lead to an increase of total wiring. Using extensive connectivity datasets for diverse neural networks combined with spatial coordinates for network nodes, we applied an optimization algorithm to the network layouts, in order to search for wire-saving component rearrangements. We found that optimized component rearrangements could substantially reduce total wiring length in all tested neural networks. Specifically, total wiring among 95 primate (Macaque) cortical areas could be decreased by 32%, and wiring of neuronal networks in the nematode Caenorhabditis elegans could be reduced by 48% on the global level, and by 49% for neurons within frontal ganglia. Wiring length reductions were possible due to the existence of long-distance projections in neural networks. We explored the role of these projections by comparing the original networks with minimally rewired networks of the same size, which possessed only the shortest possible connections. In the minimally rewired networks, the number of processing steps along the shortest paths between components was significantly increased compared to the original networks. Additional benchmark comparisons also indicated that neural networks are more similar to network layouts that minimize the length of processing paths, rather than wiring length. These findings suggest that neural systems are not exclusively optimized for minimal global wiring, but for a variety of factors including the minimization of processing steps.

Kaiser, Marcus; Hilgetag, Claus C

2006-01-01

435

TSP -- Infrastructure for the Traveling Salesperson Problem  

Microsoft Academic Search

\\u000aThe traveling salesperson (or, salesman) problem (TSP) is a well known and\\u000a important combinatorial optimization problem. The goal is to find the\\u000a shortest tour that visits each city in a given list exactly once and then\\u000a returns to the starting city. Despite this simple problem statement,\\u000asolving the TSP is difficult since it belongs to the class of NP-complete\\u000a problems.

Michael Hahsler; Kurt Hornik

2007-01-01

436

Isoperimetric problems on the sphere and on surfaces with density  

Microsoft Academic Search

We discuss partitions of the sphere and other ellipsoids into equal areas and isoperimetric problems on surfaces with density. We prove that the least-perimeter partition of any ellipsoid into two equal areas is by division along the shortest equator. We extend the work of C. Quinn, 2007, and give a new sufficient condition for a perimeter- minimizing partition of S2

Max Engelstein; Anthony Marcuccio; Quinn Maurmann; Taryn Pritchard

437

Photodeactivation paths in norbornadiene.  

PubMed

The first high level ab initio quantum-chemical calculations of potential energy surfaces (PESs) for low-lying singlet excited states of norbornadiene in the gas phase are presented. The optimization of the stationary points (minima and conical intersections) and the recalculation of the energies were performed using the multireference configuration interaction with singles (MR-CIS) and the multiconfigurational second-order perturbation (CASPT2) methods, respectively. It was shown that the crossing between valence V2 and Rydberg R1 states close to the Franck-Condon (FC) point permits an easy population switch between these states. Also, a new deactivation path in which the doubly excited state with (?3)(2) configuration (DE) has a prominent role in photodeactivation from the R1 state due to the R1/DE and the DE/V1 conical intersections very close to the R1 and DE minima, respectively, was proposed. Subsequent deactivation from the V1 to the ground state goes through an Olivucci-Robb-type conical intersection that adopts a rhombic distorted geometry. The deactivation path has negligible barriers, thereby making ultrafast radiationless decay to the ground state possible. PMID:23553256

Antol, Ivana

2013-06-30

438

Phoenix's Path to Mars  

NASA Technical Reports Server (NTRS)

[figure removed for brevity, see original site] Click on the image for movie of Phoenix's Path to Mars

This artist's animation shows the route NASA's Phoenix Mars Lander took to get from Earth to Mars. The spacecraft's path is shown in yellow, and the orbits of Mars and Earth are shown in red and blue, respectively.

Phoenix was launched from Cape Canaveral Air Force Station, Fla., on Aug. 4, 2007, when Earth and Mars were 195 million kilometers (121 million miles) apart. It will have traveled a total of 679 million kilometers (422 million miles) when it is scheduled to reach Mars on May 25, 2008. At that time, Earth and Mars will be farther apart, at 276 million kilometers (171 million miles).

The Phoenix Mission is led by the University of Arizona, Tucson, on behalf of NASA. Project management of the mission is by NASA's Jet Propulsion Laboratory, Pasadena, Calif. Spacecraft development is by Lockheed Martin Space Systems, Denver

2008-01-01

439

pathChirp: Efficient Available Bandwidth Estimation for Network Paths  

Microsoft Academic Search

This paper presents pathChirp, a new active probing tool for estimating the available bandwidth on a communication network path. Based on the concept of ''self-induced congestion,'' pathChirp features an exponential flight pattern of probes we call a chirp. Packet chips offer several significant advantages over current probing schemes based on packet pairs or packet trains. By rapidly increasing the probing

Les

2003-01-01

440

Parallel Traveling Salesman Problem  

NSDL National Science Digital Library

The traveling salesman problem is a classic optimization problem in which one seeks to minimize the path taken by a salesman in traveling between N cities, where the salesman stops at each city one and only one time, never retracing his/her route. This implementation is designed to run on UNIX systems with X-Windows, and includes parallelization using MPI.

Joiner, David; Hassinger, Jonathan

441

Bead-Fourier path integral molecular dynamics.  

PubMed

Molecular dynamics formulation of Bead-Fourier path integral method for simulation of quantum systems at finite temperatures is presented. Within this scheme, both the bead coordinates and Fourier coefficients, defining the path representing the quantum particle, are treated as generalized coordinates with corresponding generalized momenta and masses. Introduction of the Fourier harmonics together with the center-of-mass thermostating scheme is shown to remove the ergodicity problem, known to pose serious difficulties in standard path integral molecular dynamics simulations. The method is tested for quantum harmonic oscillator and hydrogen atom (Coulombic potential). The simulation results are compared with the exact analytical solutions available for both these systems. Convergence of the results with respect to the number of beads and Fourier harmonics is analyzed. It was shown that addition of a few Fourier harmonics already improves the simulation results substantially, even for a relatively small number of beads. The proposed Bead-Fourier path integral molecular dynamics is a reliable and efficient alternative to simulations of quantum systems. PMID:16241383

Ivanov, Sergei D; Lyubartsev, Alexander P; Laaksonen, Aatto

2003-06-01

442

Bead-Fourier path integral molecular dynamics  

NASA Astrophysics Data System (ADS)

Molecular dynamics formulation of Bead-Fourier path integral method for simulation of quantum systems at finite temperatures is presented. Within this scheme, both the bead coordinates and Fourier coefficients, defining the path representing the quantum particle, are treated as generalized coordinates with corresponding generalized momenta and masses. Introduction of the Fourier harmonics together with the center-of-mass thermostating scheme is shown to remove the ergodicity problem, known to pose serious difficulties in standard path integral molecular dynamics simulations. The method is tested for quantum harmonic oscillator and hydrogen atom (Coulombic potential). The simulation results are compared with the exact analytical solutions available for both these systems. Convergence of the results with respect to the number of beads and Fourier harmonics is analyzed. It was shown that addition of a few Fourier harmonics already improves the simulation results substantially, even for a relatively small number of beads. The proposed Bead-Fourier path integral molecular dynamics is a reliable and efficient alternative to simulations of quantum systems.

Ivanov, Sergei D.; Lyubartsev, Alexander P.; Laaksonen, Aatto

2003-06-01

443

Student Behaviour Outcomes: Choosing Appropriate Paths. Selected Papers from the National Conference on Behaviour Management and Behaviour Change of Children and Youth with Emotional and/or Behaviour Problems (7th, Newcastle, New South Wales, Australia, 1995).  

ERIC Educational Resources Information Center

Twelve papers produced at an annual convention were selected for inclusion in this work on behavior management and behavior change in Australian children and youth with emotional and/or behavior problems. The papers are: (1) Developing Personal Strengths, Choosing More Effective Behaviours: Control Theory, Reality Therapy and Quality Management…

Conway, Robert, Ed.; Izard, John, Ed.

444

Interactive cutting path analysis programs  

NASA Technical Reports Server (NTRS)

The operation of numerically controlled machine tools is interactively simulated. Four programs were developed to graphically display the cutting paths for a Monarch lathe, Cintimatic mill, Strippit sheet metal punch, and the wiring path for a Standard wire wrap machine. These programs are run on a IMLAC PDS-ID graphic display system under the DOS-3 disk operating system. The cutting path analysis programs accept input via both paper tape and disk file.

Weiner, J. M.; Williams, D. S.; Colley, S. R.

1975-01-01

445

Path planning for virtual bronchoscopy.  

PubMed

We have developed an automated path planning method, which enables virtual bronchoscopic 3D multidetector computed tomography (MDCT) image analysis and follow on image-guided bronchoscopy. The method fundamentals are novel combination of distance transformation and snake-based models. The computation time of our algorithm is faster than similar works and there were no missing or false branches in the final path of airways. The planned path is suitable for quantitative airway analysis and smooth virtual navigation. PMID:17946384

Negahdar, Mohamadreza; Ahmadian, Alireza; Navab, Nassir; Firouznia, Kavous

2006-01-01

446

Lifelong Planning A  

Microsoft Academic Search

Heuristic search methods promise to find shortest paths for path-planning problems faster than uninformed search methods. Incremental search methods, on the other hand, promise to find shortest paths for series of similar path-planning problems faster than is possible by solving each path-planning problem from scratch. In this article, we develop Lifelong Planning A* (LPA*), an incremental version of A* that

Sven Koenig; Maxim Likhachev; David Furcy

2004-01-01

447

New potential functions for mobile robot path planning  

Microsoft Academic Search

Abstract—This paper first describes the problem of goals nonreachable with obstacles nearby when using potential field methods for mobile robot path planning. Then, new repulsive potential functions are presented by taking the relative distance between the robot and the goal into considera- tion, which ensures that the goal position is the global minimum of the total potential. Index Terms—GNRON problem,

S. S. Ge; Y. J. Cui

2000-01-01

448

Handbook of Feynman Path Integrals  

NASA Astrophysics Data System (ADS)

The Handbook of Feynman Path Integrals appears just fifty years after Richard Feynman published his pioneering paper in 1948 entitled "Space-Time Approach to Non-Relativistic Quantum Mechanics", in which he introduced his new formulation of quantum mechanics in terms of path integrals. The book presents for the first time a comprehensive table of Feynman path integrals together with an extensive list of references; it will serve the reader as a thorough introduction to the theory of path integrals. As a reference book, it is unique in its scope and will be essential for many physicists, chemists and mathematicians working in different areas of research.

Grosche, Christian, Steiner, Frank

449

The optomechanical design of AquEYE, an instrument for astrophysics on its shortest timescales at the Asiago Observatory  

NASA Astrophysics Data System (ADS)

This paper describes the ultra-fast photometer AquEYE (the Asiago Quantum Eye) being built for the 182 cm telescope at Cima Ekar, as a prototype for the QuantEYE instrument studied for the ESO OWL. In a way similar to what has been proposed for Quanteye, Aqueye isolates a single object at the center of the telescope field of view, and divides the telescope pupil in four parts. Each sub-pupil is then focused on a Single Photon Avalanche Photodiode capable to tag the arrival time of each photon to better than 50 picoseconds. The counts are acquired via a Time to Digital Converter board and stored in four separate memories. Both in-line and off-line algorithms will be available for data analysis. The designed optical non-imaging solution concentrates all the light collected inside a 3 arcsec field on the 50 micrometer detector square area. Different filters can be inserted in the 4 different optical paths. It is foreseen to utilize the instrument on several different astrophysical problems characterized by rapid variability, including occultations by the Moon, asteroids and KBOs, and extrasolar planet transits.

Barbieri, C.; Naletto, G.; Occhipinti, T.; Tamburini, F.; Giro, E.; D'Onofrio, M.; Sain, E.; Zaccariotto, M.

450

Constructs of highly effective heat transport paths by bionic optimization  

Microsoft Academic Search

The optimization approach based on the biological evolution principle is used to construct the heat transport paths for volume-to-point\\u000a problem. The transport paths are constructed by inserting high conductivity materials in the heat conduction domain where\\u000a uniform or nonuniform heat sources exist. In the bionic optimization process, the optimal constructs of the high conductivity\\u000a material are obtained by numerically simulating

Xinguang Cheng; Zhixin Li; Zengyuan Guo

2003-01-01

451

Teaching of Critical Path Networks Using Software Packages  

Microsoft Academic Search

The aim of this paper is to review a published paper, ‘Using computer software packages to enhance the teaching of Engineering\\u000a Management Science: Part 1 -Critical path networks’. Excel in Microsoft Office 2007 was discovered to be able to solve critical\\u000a path network problems with some programming. The capabilities of the two previously evaluated packages, Microsoft Project\\u000a 2007 and Quantitative

H. Ku

2009-01-01

452

Improving VoIP quality through path switching  

Microsoft Academic Search

Abstract— The current best-effort Internet cannot readily provide the service guarantees that VoIP applications often require. Path switching can potentially address this problem without requiring new network mechanisms, simply by leveraging the robustness to performance variations available from connectivity options such as multi-homing and overlays. In this paper, we evaluate the effectiveness and benefits of path switching in improving the

S. Tao; K. Xu; A. Estepa; T. Fei; L. Gao; R. Guerin; J. Kurose; D. Towsley

2004-01-01

453

Improving VoIP quality through path switching  

Microsoft Academic Search

The current best-effort Internet cannot readily pro- vide the service guarantees that VoIP applications often require. Path switching can potentially address this problem without requiring new network mechanisms, simply by leveraging the robustness to performance variations available from connectivity options such as multi-homing and overlays. In this paper, we evaluate the effectiveness and benefits of path switching in improving the

Shu Tao; Kuai Xu; Antonio Estepa; Teng Fei; Lixin Gao; Roch Guérin; James F. Kurose; Donald F. Towsley; Zhi-li Zhang

2005-01-01

454

Anomalous paths in quantum mechanical path-integrals  

NASA Astrophysics Data System (ADS)

We investigate modifications of the discrete-time lattice action, for a quantum mechanical particle in one spatial dimension, that vanish in the naïve continuum limit but which, nevertheless, induce non-trivial effects due to quantum fluctuations. These effects are seen to modify the geometry of the paths contributing to the path-integral describing the time evolution of the particle, which we investigate through numerical simulations. In particular, we demonstrate the existence of a modified lattice action resulting in paths with any fractal dimension, df, between one and two. We argue that df=2 is a critical value, and we exhibit a type of lattice modification where the fluctuations in the position of the particle becomes independent of the time step, in which case the paths are interpreted as superdiffusive Lévy flights. We also consider the jaggedness of the paths, and show that this gives an independent classification of lattice theories.

Grimsmo, Arne L.; Klauder, John R.; Skagerstam, Bo-Sture K.

2013-11-01

455

Path integral learning of multidimensional movement trajectories  

NASA Astrophysics Data System (ADS)

This paper explores the use of Path Integral Methods, particularly several variants of the recent Path Integral Policy Improvement (PI2) algorithm in multidimensional movement parametrized policy learning. We rely on Dynamic Movement Primitives (DMPs) to codify discrete and rhythmic trajectories, and apply the PI2-CMA and PIBB methods in the learning of optimal policy parameters, according to different cost functions that inherently encode movement objectives. Additionally we merge both of these variants and propose the PIBB-CMA algorithm, comparing all of them with the vanilla version of PI2. From the obtained results we conclude that PIBB-CMA surpasses all other methods in terms of convergence speed and iterative final cost, which leads to an increased interest in its application to more complex robotic problems.

André, Joa~o.; Santos, Cristina; Costa, Lino

2013-10-01

456

Extensions of TOPSIS for multi-objective large-scale nonlinear programming problems  

Microsoft Academic Search

In this paper, we focus on multi-objective large-scale nonlinear programming (MOLSNLP) problems with block angular structure. We extend technique for order preference by similarity ideal solution (TOPSIS) approach to solve (MOLSNLP) problems. Compromise (TOPSIS) control minimizes the measure of distance, providing that the closest solution should have the shortest distance from the positive ideal solution (PIS) as well as the

Mahmoud A. Abo-sinna; Azza H. Amer

2005-01-01

457

Path Analysis: A Brief Introduction.  

ERIC Educational Resources Information Center

Path analysis is presented as a technique that can be used to test on a priori model based on a theoretical conceptualization involving a network of selected variables. This being an introductory source, no previous knowledge of path analysis is assumed, although some understanding of the fundamentals of multiple regression analysis might be…

Carducci, Bernardo J.

458

Two arm robot path planning in a static environment using polytopes and string stretching. Thesis  

NASA Technical Reports Server (NTRS)

The two arm robot path planning problem has been analyzed and reduced into components to be simplified. This thesis examines one component in which two Puma-560 robot arms are simultaneously holding a single object. The problem is to find a path between two points around obstacles which is relatively fast and minimizes the distance. The thesis involves creating a structure on which to form an advanced path planning algorithm which could ideally find the optimum path. An actual path planning method is implemented which is simple though effective in most common situations. Given the limits of computer technology, a 'good' path is currently found. Objects in the workspace are modeled with polytopes. These are used because they can be used for rapid collision detection and still provide a representation which is adequate for path planning.

Schima, Francis J., III

1990-01-01

459

British Pathe Newsreels Online  

NSDL National Science Digital Library

British Pathe, one of the oldest media companies in the world, recently made available its entire 3500-hour film archive, covering "news, sport, social history and entertainment from 1896 to 1970." At the Web site, users can search by keyword or try out advanced search, if details such as reel numbers or exact titles are known. Casual users may prefer the "Lucky Dip" search, which provides a random selection of films to see. After a search returns a hit list of films, choices include "Preview Film: a page of stills, with a textual description of the clip;" "Download Now: a free, low resolution clip;" or "Add to basket, to purchase higher resolutions of the film." (A rate card giving prices for low and high resolution clips is provided.) One hint for first-time users, though: if files do not seem to download properly, check your email, because you will be sent the URL to retrieve your film. After just a bit of finagling on our first visit, we watched the Beatles at a water-skiing show, Charlie Chaplin, and Sir Ernest Shackleton and his sled dogs photographed in 1916 on returning from their Antarctic expedition.

2002-01-01

460

Reconfigurable data path processor  

NASA Technical Reports Server (NTRS)

A reconfigurable data path processor comprises a plurality of independent processing elements. Each of the processing elements advantageously comprising an identical architecture. Each processing element comprises a plurality of data processing means for generating a potential output. Each processor is also capable of through-putting an input as a potential output with little or no processing. Each processing element comprises a conditional multiplexer having a first conditional multiplexer input, a second conditional multiplexer input and a conditional multiplexer output. A first potential output value is transmitted to the first conditional multiplexer input, and a second potential output value is transmitted to the second conditional multiplexer output. The conditional multiplexer couples either the first conditional multiplexer input or the second conditional multiplexer input to the conditional multiplexer output, according to an output control command. The output control command is generated by processing a set of arithmetic status-bits through a logical mask. The conditional multiplexer output is coupled to a first processing element output. A first set of arithmetic bits are generated according to the processing of the first processable value. A second set of arithmetic bits may be generated from a second processing operation. The selection of the arithmetic status-bits is performed by an arithmetic-status bit multiplexer selects the desired set of arithmetic status bits from among the first and second set of arithmetic status bits. The conditional multiplexer evaluates the select arithmetic status bits according to logical mask defining an algorithm for evaluating the arithmetic status bits.

Donohoe, Gregory (Inventor)

2005-01-01

461

Hard paths, soft paths or no paths? Cross-cultural perceptions of water solutions  

NASA Astrophysics Data System (ADS)

In this study, we examine how development status and water scarcity shape people's perceptions of "hard path" and "soft path" water solutions. Based on ethnographic research conducted in four semi-rural/peri-urban sites (in Bolivia, Fiji, New Zealand, and the US), we use content analysis to conduct statistical and thematic comparisons of interview data. Our results indicate clear differences associated with development status and, to a lesser extent, water scarcity. People in the two less developed sites were more likely to suggest hard path solutions, less likely to suggest soft path solutions, and more likely to see no path to solutions than people in the more developed sites. Thematically, people in the two less developed sites envisioned solutions that involve small-scale water infrastructure and decentralized, community-based solutions, while people in the more developed sites envisioned solutions that involve large-scale infrastructure and centralized, regulatory water solutions. People in the two water-scarce sites were less likely to suggest soft path solutions and more likely to see no path to solutions (but no more likely to suggest hard path solutions) than people in the water-rich sites. Thematically, people in the two water-rich sites seemed to perceive a wider array of unrealized potential soft path solutions than those in the water-scarce sites. On balance, our findings are encouraging in that they indicate that people are receptive to soft path solutions in a range of sites, even those with limited financial or water resources. Our research points to the need for more studies that investigate the social feasibility of soft path water solutions, particularly in sites with significant financial and natural resource constraints.

Wutich, A.; White, A. C.; White, D. D.; Larson, K. L.; Brewis, A.; Roberts, C.

2014-01-01

462

Hard paths, soft paths or no paths? Cross-cultural perceptions of water solutions  

NASA Astrophysics Data System (ADS)

In this study, we examine how development status and water scarcity shape people's perceptions of "hard path" and "soft path" water solutions. Based on ethnographic research conducted in four semi-rural/peri-urban sites (in Bolivia, Fiji, New Zealand, and the US), we use content analysis to conduct statistical and thematic comparisons of interview data. Our results indicate clear differences based on development status and, to a lesser extent, water scarcity. People in less developed sites were more likely to suggest hard path solutions, less likely to suggest soft path solutions, and more likely to see no path to solutions than people in more developed sites. Thematically, people in less developed sites envisioned solutions that involve small-scale water infrastructure and decentralized, community based solutions, while people in more developed sites envisioned solutions that involve large-scale infrastructure and centralized, regulatory water solutions. People in water-scarce sites were less likely to suggest soft path solutions and more likely to see no path to solutions (but no more likely to suggest hard path solutions) than people in water-rich sites. Thematically, people in water-rich sites seemed to perceive a wider array of unrealized potential soft path solutions than those in water-scarce sites. On balance, our findings are encouraging in that they indicate that people are receptive to soft path solutions in a range of sites, even those with limited financial or water resources. Our research points to the need for more studies that investigate the social feasibility of soft path water solutions, particularly in sites with significant financial and natural resource constraints.

Wutich, A.; White, A. C.; Roberts, C. M.; White, D. D.; Larson, K. L.; Brewis, A.

2013-06-01

463

Integrated Flight Path Planning System and Flight Control System for Unmanned Helicopters  

PubMed Central

This paper focuses on the design of an integrated navigation and guidance system for unmanned helicopters. The integrated navigation system comprises two systems: the Flight Path Planning System (FPPS) and the Flight Control System (FCS). The FPPS finds the shortest flight path by the A-Star (A*) algorithm in an adaptive manner for different flight conditions, and the FPPS can add a forbidden zone to stop the unmanned helicopter from crossing over into dangerous areas. In this paper, the FPPS computation time is reduced by the multi-resolution scheme, and the flight path quality is improved by the path smoothing methods. Meanwhile, the FCS includes the fuzzy inference systems (FISs) based on the fuzzy logic. By using expert knowledge and experience to train the FIS, the controller can operate the unmanned helicopter without dynamic models. The integrated system of the FPPS and the FCS is aimed at providing navigation and guidance to the mission destination and it is implemented by coupling the flight simulation software, X-Plane, and the computing software, MATLAB. Simulations are performed and shown in real time three-dimensional animations. Finally, the integrated system is demonstrated to work successfully in controlling the unmanned helicopter to operate in various terrains of a digital elevation model (DEM).

Jan, Shau Shiun; Lin, Yu Hsiang

2011-01-01

464

Integrated flight path planning system and flight control system for unmanned helicopters.  

PubMed

This paper focuses on the design of an integrated navigation and guidance system for unmanned helicopters. The integrated navigation system comprises two systems: the Flight Path Planning System (FPPS) and the Flight Control System (FCS). The FPPS finds the shortest flight path by the A-Star (A*) algorithm in an adaptive manner for different flight conditions, and the FPPS can add a forbidden zone to stop the unmanned helicopter from crossing over into dangerous areas. In this paper, the FPPS computation time is reduced by the multi-resolution scheme, and the flight path quality is improved by the path smoothing methods. Meanwhile, the FCS includes the fuzzy inference systems (FISs) based on the fuzzy logic. By using expert knowledge and experience to train the FIS, the controller can operate the unmanned helicopter without dynamic models. The integrated system of the FPPS and the FCS is aimed at providing navigation and guidance to the mission destination and it is implemented by coupling the flight simulation software, X-Plane, and the computing software, MATLAB. Simulations are performed and shown in real time three-dimensional animations. Finally, the integrated system is demonstrated to work successfully in controlling the unmanned helicopter to operate in various terrains of a digital elevation model (DEM). PMID:22164029

Jan, Shau Shiun; Lin, Yu Hsiang

2011-01-01

465

Overcoming path dependency: path generation in open systems  

Microsoft Academic Search

Studies on societal path dependencies tend to focus on mechanisms that anchor and stabilize national trajectories while paying\\u000a less attention to transnational interactions and multilevel governance. This paper explores processes of path transformation\\u000a in societies that are presumed to have the characteristics of open systems. Two pairs of case studies are presented and compared.\\u000a The first illustrates institutional change through

Marie-Laure Djelic; Sigrid Quack

2007-01-01

466

Path planning for complex terrain navigation via dynamic programming  

SciTech Connect

This work considers the problem of planning optimal paths for a mobile robot traversing complex terrain. In addition to the existing obstacles, locations in the terrain where the slope is too steep for the mobile robot to navigate safely without tipping over become mathematically equivalent to extra obstacles. To solve the optimal path problem, the authors use a dynamic programming approach. The dynamic programming approach utilized herein does not suffer the difficulties associated with spurious local minima that the artificial potential field approaches do. In fact, a globally optimal solution is guaranteed to be found if a feasible solution exists. The method is demonstrated on several complex examples including very complex terrains.

Kwok, K.S.; Driessen, B.J.

1998-12-31

467

An expert path through a thermo maze  

NASA Astrophysics Data System (ADS)

Several studies in recent years have demonstrated that upper-division students struggle with partial derivatives and the complicated chain rules ubiquitous in thermodynamics. We asked several experts (primarily faculty who teach thermodynamics) to solve a challenging and novel thermodynamics problem in order to understand how they navigate through this maze. What we found was a tremendous variety in solution strategies and sense-making tools, both within and between individuals. This case study focuses on one particular expert: his solution paths, use of sense-making tools, and comparison of different approaches.

Kustusch, Mary Bridget; Roundy, David; Dray, Tevian; Manogue, Corinne

2013-01-01

468

An expert path through a thermo maze  

NSDL National Science Digital Library

Several studies in recent years have demonstrated that upper-division students struggle with partial derivatives and the complicated chain rules ubiquitous in thermodynamics. We asked several experts (primarily faculty who teach thermodynamics) to solve a challenging and novel thermodynamics problem in order to understand how they navigate through this maze. What we found was a tremendous variety in solution strategies and sense-making tools, both within and between individuals. This case study focuses on one particular expert: his solution paths, use of sense-making tools, and comparison of different approaches.

Kustusch, Mary B.; Roundy, David J.; Dray, Tevian; Manogue, Corinne

2014-02-01

469

DICOM involving XML path-tag  

NASA Astrophysics Data System (ADS)

Digital Imaging and Communications in Medicine (DICOM) is a standard for handling, storing, printing, and transmitting information in medical imaging. XML (Extensible Markup Language) is a set of rules for encoding documents in machine-readable form which has become more and more popular. The combination of these two is very necessary and promising. Using XML tags instead of numeric labels in DICOM files will effectively increase the readability and enhance the clear hierarchical structure of DICOM files. However, due to the fact that the XML tags rely heavily on the orders of the tags, the strong data dependency has a lot of influence on the flexibility of inserting and exchanging data. In order to improve the extensibility and sharing of DICOM files, this paper introduces XML Path-Tag to DICOM. When a DICOM file is converted to XML format, adding simple Path-Tag into the DICOM file in place of complex tags will keep the flexibility of a DICOM file while inserting data elements and give full play to the advantages of the structure and readability of an XML file. Our method can solve the weak readability problem of DICOM files and the tedious work of inserting data into an XML file. In addition, we set up a conversion engine that can transform among traditional DICOM files, XML-DCM and XML-DCM files involving XML Path-Tag efficiently.

Zeng, Qiang; Yao, Zhihong; Liu, Lei

2011-03-01

470

A Flight Examination of Operating Problems of V/STOL Aircraft in STOL-Type Landing and Approach  

NASA Technical Reports Server (NTRS)

A flight investigation has been conducted using a large twin-engine cargo aircraft to isolate the problems associated with operating propeller-driven aircraft in the STOL speed range where appreciable engine power is used to augment aerodynamic lift. The problems considered would also be representative of those of a large overloaded VTOL aircraft operating in an STOL manner with comparable thrust-to-weight ratios. The study showed that operation at low approach speeds was compromised by the necessity of maintaining high thrust to generate high lift and yet achieving the low lift-drag ratios needed for steep descents. The useable range of airspeed and flight path angle was limited by the pilot's demand for a positive climb margin at the approach speed, a suitable stall margin, and a control and/or performance margin for one engine inoperative. The optimum approach angle over an obstacle was found to be a compromise between obtaining the shortest air distance and the lowest touchdown velocity. In order to realize the greatest low-speed potential from STOL designs, the stability and control characteristics must be satisfactory.

Innis, Robert C.; Quigley, Hervey C.

1961-01-01

471

PCB Drill Path Optimization by Combinatorial Cuckoo Search Algorithm.  

PubMed

Optimization of drill path can lead to significant reduction in machining time which directly improves productivity of manufacturing systems. In a batch production of a large number of items to be drilled such as printed circuit boards (PCB), the travel time of the drilling device is a significant portion of the overall manufacturing process. To increase PCB manufacturing productivity and to reduce production costs, a good option is to minimize the drill path route using an optimization algorithm. This paper reports a combinatorial cuckoo search algorithm for solving drill path optimization problem. The performance of the proposed algorithm is tested and verified with three case studies from the literature. The computational experience conducted in this research indicates that the proposed algorithm is capable of efficiently finding the optimal path for PCB holes drilling process. PMID:24707198

Lim, Wei Chen Esmonde; Kanagaraj, G; Ponnambalam, S G

2014-01-01

472

PCB Drill Path Optimization by Combinatorial Cuckoo Search Algorithm  

PubMed Central

Optimization of drill path can lead to significant reduction in machining time which directly improves productivity of manufacturing systems. In a batch production of a large number of items to be drilled such as printed circuit boards (PCB), the travel time of the drilling device is a significant portion of the overall manufacturing process. To increase PCB manufacturing productivity and to reduce production costs, a good option is to minimize the drill path route using an optimization algorithm. This paper reports a combinatorial cuckoo search algorithm for solving drill path optimization problem. The performance of the proposed algorithm is tested and verified with three case studies from the literature. The computational experience conducted in this research indicates that the proposed algorithm is capable of efficiently finding the optimal path for PCB holes drilling process.

Lim, Wei Chen Esmonde; Kanagaraj, G.; Ponnambalam, S. G.

2014-01-01

473

Mobile transporter path planning using a genetic algorithm approach  

NASA Technical Reports Server (NTRS)

The use of an optimization technique known as a genetic algorithm for solving the mobile transporter path planning problem is investigated. The mobile transporter is a traveling robotic vehicle proposed for the Space Station which must be able to reach any point of the structure autonomously. Specific elements of the genetic algorithm are explored in both a theoretical and experimental sense. Recent developments in genetic algorithm theory are shown to be particularly effective in a path planning problem domain, though problem areas can be cited which require more research. However, trajectory planning problems are common in space systems and the genetic algorithm provides an attractive alternative to the classical techniques used to solve these problems.

Baffes, Paul; Wang, Lui

1988-01-01

474

Path Characterization Algorithms for FASCODE.  

National Technical Information Service (NTIS)

This report has described the results of a study undertaken at AER to identify and implement a state of the art nonlinear retrieval approach to characterize line of sight variability of atmospheric thermal and constituent environments. This path character...

B. L. Linder J. L. Moncet R. G. Isaacs S. A. Clough S. D. Worsham

1990-01-01

475

Heuristically optimal path scanning for high-speed multiphoton circuit imaging.  

PubMed

Population dynamics of patterned neuronal firing are fundamental to information processing in the brain. Multiphoton microscopy in combination with calcium indicator dyes allows circuit dynamics to be imaged with single-neuron resolution. However, the temporal resolution of fluorescent measures is constrained by the imaging frequency imposed by standard raster scanning techniques. As a result, traditional raster scans limit the ability to detect the relative timing of action potentials in the imaged neuronal population. To maximize the speed of fluorescence measures from large populations of neurons using a standard multiphoton laser scanning microscope (MPLSM) setup, we have developed heuristically optimal path scanning (HOPS). HOPS optimizes the laser travel path length, and thus the temporal resolution of neuronal fluorescent measures, using standard galvanometer scan mirrors. Minimizing the scan path alone is insufficient for prolonged high-speed imaging of neuronal populations. Path stability and the signal-to-noise ratio become increasingly important factors as scan rates increase. HOPS addresses this by characterizing the scan mirror galvanometers to achieve prolonged path stability. In addition, the neuronal dwell time is optimized to sharpen the detection of action potentials while maximizing scan rate. The combination of shortest path calculation and minimization of mirror positioning time allows us to optically monitor a population of neurons in a field of view at high rates with single-spike resolution, ? 125 Hz for 50 neurons and ? 8.5 Hz for 1,000 neurons. Our approach introduces an accessible method for rapid imaging of large neuronal populations using traditional MPLSMs, facilitating new insights into neuronal circuit dynamics. PMID:21715667

Sadovsky, Alexander J; Kruskal, Peter B; Kimmel, Joseph M; Ostmeyer, Jared; Neubauer, Florian B; MacLean, Jason N

2011-09-01

476

Path integration on Darboux spaces  

Microsoft Academic Search

In this paper, the Feynman path integral technique is applied to two-dimensional spaces of nonconstant curvature: these spaces\\u000a are called Darboux spaces D\\u000a I-D\\u000a IV. We start each consideration in terms of the metric and then analyze the quantum theory in the separable coordinate systems.\\u000a The path integral in each case is formulated and then solved in the majority of

Christian Grosche; Theoretische Physik

2006-01-01

477

Backup Path Classification Based on Failure Risks for Efficient Backup Path Computation  

Microsoft Academic Search

Abstract. We propose a new approach exploiting the failure risk (node, link or Shared Risk Link Group) structures to enhance the backup path computation. Upon failure, our approach classifies the backup paths into two categories: operative backup paths and inoperative backup,paths. An operative backup path is an active backup path which really receives traffic of some affected communications while an

Mohand Yazid Saidi; Bernard Cousin; Jean-louis Le Roux

2009-01-01

478

A Bat Algorithm with Mutation for UCAV Path Planning  

PubMed Central

Path planning for uninhabited combat air vehicle (UCAV) is a complicated high dimension optimization problem, which mainly centralizes on optimizing the flight route considering the different kinds of constrains under complicated battle field environments. Original bat algorithm (BA) is used to solve the UCAV path planning problem. Furthermore, a new bat algorithm with mutation (BAM) is proposed to solve the UCAV path planning problem, and a modification is applied to mutate between bats during the process of the new solutions updating. Then, the UCAV can find the safe path by connecting the chosen nodes of the coordinates while avoiding the threat areas and costing minimum fuel. This new approach can accelerate the global convergence speed while preserving the strong robustness of the basic BA. The realization procedure for original BA and this improved metaheuristic approach BAM is also presented. To prove the performance of this proposed metaheuristic method, BAM is compared with BA and other population-based optimization methods, such as ACO, BBO, DE, ES, GA, PBIL, PSO, and SGA. The experiment shows that the proposed approach is more effective and feasible in UCAV path planning than the other models.

Wang, Gaige; Guo, Lihong; Duan, Hong; Liu, Luo; Wang, Heqi

2012-01-01

479

Heuristic optimization of the scanning path of particle therapy beams.  

PubMed

Quasidiscrete scanning is a delivery strategy for proton and ion beam therapy in which the beam is turned off when a slice is finished and a new energy must be set but not during the scanning between consecutive spots. Different scanning paths lead to different dose distributions due to the contribution of the unintended transit dose between spots. In this work an algorithm to optimize the scanning path for quasidiscrete scanned beams is presented. The classical simulated annealing algorithm is used. It is a heuristic algorithm frequently used in combinatorial optimization problems, which allows us to obtain nearly optimal solutions in acceptable running times. A study focused on the best choice of operational parameters on which the algorithm performance depends is presented. The convergence properties of the algorithm have been further improved by using the next-neighbor algorithm to generate the starting paths. Scanning paths for two clinical treatments have been optimized. The optimized paths are found to be shorter than the back-and-forth, top-to-bottom (zigzag) paths generally provided by the treatment planning systems. The gamma method has been applied to quantify the improvement achieved on the dose distribution. Results show a reduction of the transit dose when the optimized paths are used. The benefit is clear especially when the fluence per spot is low, as in the case of repainting. The minimization of the transit dose can potentially allow the use of higher beam intensities, thus decreasing the treatment time. The algorithm implemented for this work can optimize efficiently the scanning path of quasidiscrete scanned particle beams. Optimized scanning paths decrease the transit dose and lead to better dose distributions. PMID:19610293

Pardo, J; Donetti, M; Bourhaleb, F; Ansarinejad, A; Attili, A; Cirio, R; Garella, M A; Giordanengo, S; Givehchi, N; La Rosa, A; Marchetto, F; Monaco, V; Pecka, A; Peroni, C; Russo, G; Sacchi, R

2009-06-01

480

Path Planning Algorithms for Autonomous Border Patrol Vehicles  

NASA Astrophysics Data System (ADS)

This thesis presents an online path planning algorithm developed for unmanned vehicles in charge of autonomous border patrol. In this Pursuit-Evasion game, the unmanned vehicle is required to capture multiple trespassers on its own before any of them reach a target safe house where they are safe from capture. The problem formulation is based on Isaacs' Target Guarding problem, but extended to the case of multiple evaders. The proposed path planning method is based on Rapidly-exploring random trees (RRT) and is capable of producing trajectories within several seconds to capture 2 or 3 evaders. Simulations are carried out to demonstrate that the resulting trajectories approach the optimal solution produced by a nonlinear programming-based numerical optimal control solver. Experiments are also conducted on unmanned ground vehicles to show the feasibility of implementing the proposed online path planning algorithm on physical applications.

Lau, George Tin Lam

481

Follow this path to pollution prevention  

SciTech Connect

Processes that minimize the amount of waste generated at the source are the most economical. Even in existing facilities, waste generation can be reduced by more than 30% on average, while at the same time lowering operating costs and new capital investment. This article charts a path to an effective pollution prevention (P{sup 2}) program, with particular emphasis on reducing waste generation in existing manufacturing facilities. It is based on a proven methodology used within the DuPont Co., and can be applied to both large- and small-scale problems. An example illustrates both the how-to of a pollution prevention program, as well as some of the tools and techniques available to tackle waste generation problems by looking inside the pipes and vessels.

Dyer, J.A.; Mulholland, K.L. [E.I. du Pont de Nemours and Co. (United States)

1998-01-01

482

Experimental Study on GA-Based Path-Oriented Test Data Generation Using Branch Distance Function  

Microsoft Academic Search

Automatic path-oriented test data generation is not only a key problem but a hot issue in the research area of software testing today. Genetic algorithm (GA) has been used to path-oriented test data generation since 1992 and outperforms other approaches. A fitness function based on branch distance (BDBFF) has been applied in GA-based path-oriented test data generation. To investigate performance

Yong Chen; Yong Zhong

2009-01-01

483

A Note on Drawing Direction-constrained Paths in 3D  

Microsoft Academic Search

We study the problem of drawing a graph-theoretic path where each edge is assigned an axis-parallel direction in 3D. Di Battista et al.(3) gives a combinatorial character- ization for such path drawings that start at the origin and reach a point in an octant. In this paper, we con- sider the drawability question for such paths that start at the

Ethan Kim; Sue Whitesides; Giuseppe Liotta

2007-01-01

484

Piecewise Bezier Curves Path Planning with Continuous Curvature Constraint for Autonomous Driving  

Microsoft Academic Search

\\u000a We present two practical path planning algorithms based on Bezier curves for autonomous vehicles operating under waypoints\\u000a and corridor constraints. Bezier curves have useful properties for the trajectory generation problem. This paper describes\\u000a how the algorithms apply these properties to generate the reference trajectory for vehicles to satisfy the path constraints.\\u000a Both algorithms generate the piecewise-Bezier-curves path such that the

Ji-Wung Choi; Renwick Curry; Gabriel Elkaim

485

Path Integral Monte Carlo Calculation of Interatomic Forces  

Microsoft Academic Search

The calculation of electronic forces with quantum Monte Carlo has, for many years, been an outstanding problem. One can calculate interatomic forces with Path Integral Monte Carlo(PIMC) as the coordinate derivatives of the partition function. Advantages of using PIMC are that effects of thermal electronic excitations and correlations are included, no trial functions are involved and the force estimator is

Fenghua Zong; David Ceperley

1997-01-01

486

An Algorithm for Path Connections and Its Applications  

Microsoft Academic Search

The algorithm described in this paper is the outcome of an endeavor to answer the following question: Is it possible to find procedures which would enable a computer to solve efficiently path-connection problems inherent in logical drawing, wiring diagramming, and optimal route finding? The results are highly encouraging. Within our framework, we are able to solve the following types of

C. Y. Lee

1961-01-01

487

Vision-based path-planning in unstructured environments  

Microsoft Academic Search

Autonomous driving in unstructured environments has attracted an unprecedented level of attention when the DARPA announced the Grand Challenge Competitions in 2004 and 2005. Autonomous driving involves (at least) three major subtasks: perception of the environment, path planning and subsequent vehicle control. Whereas the latter has proven a solved problem, the first two constituted, apart from hardware failures, the most

Britta Hummel; S. Kammel; Thao Dang; C. Duchow; C. Stiller

2006-01-01

488

Dynamic path planning in sensor-based terrain acquisition  

Microsoft Academic Search

The terrain acquisition problem is formulated as that of continuous motion planning, and no constraints are imposed on obstacle geometry. Two algorithms are described for acquiring planar terrains with obstacles of arbitrary shape. Estimates of the algorithm performance are derived as upper bounds on the lengths of generated paths

V. J. Lumelsky; S. Mukhopadhyay; K. Sun

1990-01-01

489

Real-Time Randomized Path Planning for Robot Navigation  

Microsoft Academic Search

Mobile robots often find themselves in a situation where they must find a trajectory to another position in their environment, subject to constraints posed by obstacles and the capabilities of the robot itself. This is the problem of planning a path through a continuous domain, for which several approaches have been developed. Each has some limitations however, including requiring state

James Bruce; Manuela M. Veloso

2002-01-01

490

Mixed Integer Programming for Multi-Vehicle Path Planning  

Microsoft Academic Search

Abstract: This paper presents a new approach to fuel-optimal path planningof multiple vehicles using a combination of linear and integerprogramming. The basic problem formulation is to havethe vehicles move from an initial dynamic state to a final statewithout colliding with each other, while at the same time avoidingother stationary and moving obstacles. It is shown that thisproblem can be rewritten

T. Schouwenaars; B. Demoor; E. Feron

2001-01-01

491

Probabilistic path selection in wireless sensor networks with controlled mobility  

Microsoft Academic Search

We consider the problem of planning path of a ¿data mule¿ in a cluster based sensor networks. Recent research shows that significant energy saving can be achieved by using this mobile data collection nodes. Although a data mule (DM) can reduce the energy consumption of the cluster head (CH), it increases the latency from the time the CH gain the

Xiwei Zhang; Lili Zhang; Guihai Chen; Xia Zou

2009-01-01

492

Beschreven Banen van Grote Voertuigen (Swept Paths of Heavy Vehicles).  

National Technical Information Service (NTIS)

Problems of swept paths of heavy vehicles are determined. The following two points are discussed: (1) Methods which are available for the estimation of the magnitude of the bends made by heavy vehicles when turning; and (2) when is an exact description of...

1986-01-01

493

Tool path planning for compound surfaces in spray forming processes  

Microsoft Academic Search

Spray forming is an emerging manufacturing process. The automated tool planning for this process is a nontrivial problem, especially for geometry-complicated parts consisting of multiple freeform surfaces. Existing tool planning approaches are not able to deal with this kind of compound surface. This paper proposes a tool-path planning approach which optimizes the tool motion performance and the thickness uniformity. There

Weihua Sheng; Heping Chen; Ning Xi; Yifan Chen

2005-01-01

494

Time-Optimal Control of Robotic Manipulators Along Specified Paths  

Microsoft Academic Search

The minimum-time manipulator control problem is solved for the case when the path is specified and the actuator torque limitations are known. The optimal open-loop torques are found, and a method is given for implementing these torques with a conventional linear feedback control system. The algorithm allows bounds on the torques that may be arbitrary functions of the joint angles

J. E. Bobrow; S. Dubowsky; J. S. Gibson

1985-01-01

495

Smoothing of mixed complementarity problems  

SciTech Connect

The authors introduce a smoothing approach to the mixed complementarity problem, and study the limiting behavior of a path defined by approximate minimizers of a nonlinear least squares problem. The main result guarantees that, under a mild regularity condition, limit points of the iterates are solutions to the mixed complementarity problem. The analysis is applicable to a wide variety of algorithms suitable for large-scale mixed complementarity problems.

Gabriel, S.A.; More, J.J. [Argonne National Lab., IL (United States). Mathematics and Computer Science Div.

1995-09-01

496

V753 MON: A UNIQUE CLOSE BINARY JUST AFTER THE EVOLUTIONARY STAGE WITH THE SHORTEST PERIOD DURING MASS TRANSFER  

SciTech Connect

We discovered that the O-C curve of V753 Mon shows an upward parabolic change while undergoing a cyclic variation with a period of 13.5 yr. The upward parabolic change reveals a long-term period increase at a rate of P-dot = +7.8 x 10{sup -8} days yr{sup -1}. Photometric solutions determined using the Wilson-Devinney method confirm that V753 Mon is a semi-detached binary system where the slightly less massive, hotter component star is transferring mass to the more massive one. This is in agreement with the long-term increase of the orbital period. The increase of the orbital period, the mass ratio very close to unity, and the semi-detached configuration with a less massive lobe-filling component all suggest that V753 Mon is on a key evolutionary stage just after the evolutionary stage with the shortest period during mass transfer. The results in this paper will shed light on the formation of massive contact binaries and the evolution of binary stars. The cyclic oscillation in the O-C diagram indicates that V753 Mon may be a triple system containing an extremely cool stellar companion that may play an important role for the formation and evolution in the binary system.

Qian, S.-B.; Zhang, J.; Wang, J.-J.; Zhu, L.-Y.; Liu, L.; Zhao, E. G.; Li, L.-J.; He, J.-J., E-mail: qsb@ynao.ac.cn [Yunnan Observatories, Chinese Academy of Sciences (CAS), P.O. Box 110, 650011 Kunming (China)

2013-08-15

497

Optical Path, Phase, and Interference  

NASA Astrophysics Data System (ADS)

A powerful tool in wave optics is the concept of optical path length, a notion usually introduced with Fermat's principle.1-3 The analysis of Fermat's principle requires the application of the calculus of variations and the concept of an extremum, ideas too advanced for beginning students. However, the concept has proven its usefulness in the analysis4 of interference experiments such as those of Michelson and Fabry-Perot. In this paper we shall show how optical path length can aid in the analysis of a modified two-slit Young experiment.

Newburgh, Ronald

2005-11-01

498

Cooperative path planning for multiple UAVs in dynamic and uncertain environments  

Microsoft Academic Search

This paper addresses the problem of cooperative path planning for a fleet of unmanned aerial vehicles (UAVs). The paths are optimized to account for uncertainty\\/adversaries in the environment by modeling the probability of UAV loss. The approach extends prior work by coupling the failure probabilities for each UAV to the selected missions for all other UAVs. In order to maximize

John S. Bellingham; Michael Tillerson; Mehdi Alighanbari

2002-01-01

499

Tool paths and cutting technology in computer-aided process planning  

Microsoft Academic Search

This paper reports on the development of a module to calculate automatically tool paths and cutting conditions for metal cutting operations. Process planning must select correct cutting conditions to minimise disturbances on the shop floor owing to tooling problems. Tool path and cutting condition algorithms to generate reliable NC programs have been designed. The algorithms have been implemented in the

R. M. Boogert; H. J. J. Kals; F. J. A. M. van Houten

1996-01-01

500

Genetic Algorithm Based Path Planning and Optimization for Autonomous Mobile Robots with Morphological Preprocessing  

Microsoft Academic Search

This paper presents an algorithm for optimal path planning for mobile robots using genetic algorithms coupled with morphological image preprocessing of the terrain. Path planning in a given environment, being a NP-hard problem, is computationally demanding especially if exact or deterministic techniques are employed. This paves the way for the use of evolutionary computing techniques, such as genetic algorithms (GAs),

Fayyaz A. Afsar; M. Arif; M. Hussain

2006-01-01