Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 218 for “"Shortest Paths"”.

  1. Shortest paths in line arrangements

    The problem of finding a shortest Euclidean path in an arrangement of lines between two points in the arrangement has been extensively studied; however, the best known exact solution takes quadratic time, and it’s not known if a subquadratic time algorithm exists. While I did not succeed in …

    ubc Repository record for Shortest paths in line arrangements (opens in a new tab) Download PDF for Shortest paths in line arrangements (opens in a new tab)

  2. Shortest paths on uncertain terrains

    … Sack. We then examine the problem of finding the shortest path that stays on these terrains given certain assumptions about the terrains. We show that this problem is NP-hard under two fairly natural assumptions (meaning that we do not expect any polynomial time algorithm that finds these paths to …

    ubc Repository record for Shortest paths on uncertain terrains (opens in a new tab) Download PDF for Shortest paths on uncertain terrains (opens in a new tab)

  3. Shortest paths in weighted polygons.

    … ($s>1$). The problem consists of finding the shortest path between p and q. We solve this problem in O(n) time for convex polygons. For simple polygons, we show two algorithms. The first algorithm runs in O(E log n) time using O(E) space (where E is the size of the visibility of P). The second …

    ottawa-retro Repository record for Shortest paths in weighted polygons. (opens in a new tab)

  4. Shortest Paths Among Dynamic Obstacles

    … we study the problem of computing collision-free shortest paths among growing discs. This problem has previously been studied for discs where the growth rates are fixed. We study a more general problem variant, where: (1) the speeds at which the discs grow are polynomial functions of degree β and …

    carleton Repository record for Shortest Paths Among Dynamic Obstacles (opens in a new tab)

  5. Shortest Paths in Geometric Intersection Graphs

    This thesis studies shortest paths in geometric intersection graphs, which can model, among others, ad-hoc communication and transportation networks. First, we consider two classical problems in the field of algorithms, namely Single-Source Shortest Paths (SSSP) and All-Pairs Shortest Paths (APSP). …

    waterloo Repository record for Shortest Paths in Geometric Intersection Graphs (opens in a new tab)

  6. Resource constrained shortest paths and extensions

    … techniques to solve the resource constrained shortest path problem (RCSPP) which seeks a minimum cost path between two nodes in a directed graph subject to a finite set of resource constraints. Although NP-hard, the RCSPP is extremely useful in practice and often appears as a subproblem in …

    gatech Repository record for Resource constrained shortest paths and extensions (opens in a new tab)

  7. Clustering, weighted sequences, and shortest paths

    … study graph and string problems.Multiple Source Shortest Paths in Planar Graphs: Given an embedded planar digraph with positive edge weights and a face f, we are interested in a data structure supporting shortest path queries, where the source is in f. The best known data structure by Klein [SODA …

    greece Repository record for Clustering, weighted sequences, and shortest paths (opens in a new tab)

  8. Exploring Shortest Paths on Large-Scale Networks

    … a series of problems for understanding networks. Shortest path is among themost fundamental notions studied in graph theory. By exploring shortest path struc-ture, we can better understand the connections between entities. However, it is oftencomputationally expensive to compute shortest paths on …

    anu Repository record for Exploring Shortest Paths on Large-Scale Networks (opens in a new tab)

  9. Constrained Shortest Paths in Terrains and Graphs

    Finding a shortest path is one of the most well-studied optimization problems. In this thesis we focus on shortest paths in geometric and graph theoretic settings subject to different feasibility constraints that arise in practical applications of such paths. One of the most fundamental problems in …

    waterloo Repository record for Constrained Shortest Paths in Terrains and Graphs (opens in a new tab)

  10. Finding shortest paths in large scale networks

    Finding the shortest path between two points in a network is a fundamental problem in computer science with many applications. By exploiting properties of the underlying networks we improve and extend one of the state-of-the-art algorithms for finding shortest paths in road networks, Transit Node …

    unsw Repository record for Finding shortest paths in large scale networks (opens in a new tab)

  11. Optimistic and pessimistic shortest paths on uncertain terrains

    In the Uncertain Terrain Shortest Path problem we consider a triangulated terrain with vertices having uncertain Z-coordinates: each vertex is denned as a (x,y,z―,z+) tuple, where the z coordinate of a vertex is uncertain and can be anywhere in the range from z― to z+. We are looking for a path …

    ubc Repository record for Optimistic and pessimistic shortest paths on uncertain terrains (opens in a new tab) Download PDF for Optimistic and pessimistic shortest paths on uncertain terrains (opens in a new tab)

  12. Constant storage for computing shortest paths for a polyhedron

    We present a new scheme for storing shortest path information for a polyhedron. This scheme is obtained by applying the constant storage scheme of Han and Saxena [5] on the outward layout of Sharir and Schorr [10]. We achieve constant storage and O(log n + k) time for computing the shortest path …

    umkc Repository record for Constant storage for computing shortest paths for a polyhedron (opens in a new tab)

  13. Single-face non-crossing shortest paths in planar graphs

    The student, Alexander Steiger, submitted this Thesis for approval on 2017-07-12 at 16:52.

    uiuc Repository record for Single-face non-crossing shortest paths in planar graphs (opens in a new tab)

  14. Practicality of Sub-Linear Algorithms for Distributed Shortest Paths

    The computation of Single-Source Shortest Paths (SSSP) is a fundamental problem in distributed networks. This thesis explores efficient SSSP solutions within the synchronous CONGEST model, where communication occurs in rounds in which each node can send O(log n) information to each of its …

    concordia Download PDF for Practicality of Sub-Linear Algorithms for Distributed Shortest Paths (opens in a new tab)

  15. Time constrained shortest paths in stochastic and dynamic transportation networks

    … develops methodologies for solving constrained shortest path problems in dynamic and random conditions. Due to the randomness of the network, the decisions need to account for uncertainty of the future real-time network state. Currently the randomness of the arc attributes is not taken into …

    texas Repository record for Time constrained shortest paths in stochastic and dynamic transportation networks (opens in a new tab) Restricted access

  16. Constrained shortest paths for QoS routing and path protection in communication networks.

    … the selection of a set of k > 1 link-disjoint paths with minimum total cost and with total delay bounded by a given upper bound. This problem arises in the context of provisioning paths in a network that could be used to provide resilience to link failures. Again we studied the LP relaxation of …

    oklahoma-thes Repository record for Constrained shortest paths for QoS routing and path protection in communication networks. (opens in a new tab)

  17. Algorithms for dynamic and distributed networks : shortest paths, betweenness centrality and related problems

    … in computer science: computing all pairs all shortest paths (APASP) in a graph. One of the main contributions of this thesis is a collection of dynamic algorithms for computing APASP and BC scores which are provably faster than static algorithms for several classes of graphs. We use n = |V| …

    texas Repository record for Algorithms for dynamic and distributed networks : shortest paths, betweenness centrality and related problems (opens in a new tab)

Page 1 of 11