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 79 for “"disjoint paths"”.

  1. Disjoint paths in geometric graphs

    Construction of the shortest paths connecting two given nodes in a geometric graph is the quintessential problem in computational geometry. We consider several variations of this problem with applications that include robotics, Geographic Information Systems, and sensor networks. The first problem …

    unlv Repository record for Disjoint paths in geometric graphs (opens in a new tab) Download PDF for Disjoint paths in geometric graphs (opens in a new tab)

  2. Algorithms for flows and disjoint paths in planar graphs

    … for computing flows, connectivity, and disjoint paths in planar graphs. In all cases, the algorithms are either the first polynomial-time algorithms or are faster than all previously-known algorithms. First, we describe algorithms for the maximum flow problem in directed planar graphs …

    uiuc Repository record for Algorithms for flows and disjoint paths in planar graphs (opens in a new tab)

  3. Coloring graphs with no k5-subdivision: disjoint paths in graphs

    The Four Color Theorem states that every planar graph is 4-colorable. Hajos conjectured that for any positive integer k, every graph containing no K_{k+1}-subdivision is k-colorable. However, Catlin disproved Hajos conjecture for k>=6. It is not hard to prove that the conjecture is true for k<=3. …

    gatech Repository record for Coloring graphs with no k5-subdivision: disjoint paths in graphs (opens in a new tab)

  4. Decompositions and Algorithms for the Disjoint Paths Problem in Planar Graphs

    Στο πρόβλημα των Διακεκριμενων Μονοπατιων μας ζητείται να εξετάσουμε, δεδομένου ενός γραφήματος G και ενος συνόλου k ζευγών τερματικών,αν τα ζεύγη των τερματικών μπορούν να συνδεθούν με διακεκριμένα μονοπάτια. Στα "Graph Minors", μια σειρά 23 εργασιών μεταξύ 1984 και 2011, οι Neil Robertson και …

    athens Repository record for Decompositions and Algorithms for the Disjoint Paths Problem in Planar Graphs (opens in a new tab)

  5. REND: Reliable and Energy-Efficient Node-Disjoint Paths in Wireless Sensor Networks

    … finding most reliable and most efficient paths between source node and destination node is considered NP hard problem. We can increase reliability by ability to find node-disjoint alternate path when there is any disruption in the path from source to destination. If we can find reliable …

    ndsu Repository record for REND: Reliable and Energy-Efficient Node-Disjoint Paths in Wireless Sensor Networks (opens in a new tab)

  6. Timely, Reliable, and Cost-Effective Internet Transport Service using Structured Overlay Networks

    … schemes ranging from a single path, to multiple disjoint paths, to arbitrary graphs. We conduct an extensive analysis of real-world network data, finding that a routing approach using two disjoint paths performs well in most cases, and that cases where two disjoint paths do not perform well …

    jhu Repository record for Timely, Reliable, and Cost-Effective Internet Transport Service using Structured Overlay Networks (opens in a new tab)

  7. Centralidade de proximidade por múltiplos caminhos disjuntos

    … centrality metrics consider only shortest paths, neglecting the existence of bit-longer paths between nodes in a network, which can be strategic to maintain network connectivity. This work proposes the disjoint multipath closeness centrality, which extrapolates the traditional closeness by …

    brazil-uerj Repository record for Centralidade de proximidade por múltiplos caminhos disjuntos (opens in a new tab)

  8. Turn Constrained Path Planning Problems

    We consider the problem of constructing multiple disjoint paths connecting a source point s to a target point t in a geometric graph. We require that the paths do not have any sharp turn angles. We present a review of turn constrained path planning algorithms and also algorithms for constructing …

    unlv Repository record for Turn Constrained Path Planning Problems (opens in a new tab) Download PDF for Turn Constrained Path Planning Problems (opens in a new tab)

  9. Properties and Algorithms of the (n,k)-Arrangement Graphs and Augmented Cubes

    … we investigate the problem of finding k(n − k) disjoint paths from a source node to k(n−k) target nodes in an (n, k)-arrangement interconnection network such that no path has length more than diameter+(n−k)+2, where diameter is the maximum length of shortest path between any two nodes in the …

    brock Repository record for Properties and Algorithms of the (n,k)-Arrangement Graphs and Augmented Cubes (opens in a new tab)

  10. Near-optimal broadcast in all-port wormhole-routed hypercubes using error-correcting codes

    … hypercube. Once stations are identified, node disjoint paths are formed from the source to all stations. The broadcasting is accomplished first by sending the message to all stations, which will inform the rest of the nodes. To establish node-disjoint paths between the source node and all …

    unlv Repository record for Near-optimal broadcast in all-port wormhole-routed hypercubes using error-correcting codes (opens in a new tab) Download PDF for Near-optimal broadcast in all-port wormhole-routed hypercubes using error-correcting codes (opens in a new tab)

  11. Distributed Algorithms in Membrane Systems

    … problems in graph theory: the edge- and node-disjoint paths problems. For a given membrane system with n cells and m links, these solutions find sets of edge- and node-disjoint paths of maximum cardinality in O(mn) steps. These solutions are the first P algorithms for solving the edge- and …

    auckland-ms Repository record for Distributed Algorithms in Membrane Systems (opens in a new tab)

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

    … requires 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 …

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

  13. Network design for survivable military satellite communication.

    … radio links, is defined as a number "m" of node-disjoint paths between any node and the ground satellite terminal, assuming that the terminals and the satellite links are highly invulnerable. In this thesis, an heuristic method for finding the required number and the locations of satellite ground …

    nps Repository record for Network design for survivable military satellite communication. (opens in a new tab)

  14. ΖΗΤΗΜΑΤΑ ΣΥΝΕΚΤΙΚΟΤΗΤΑΣ ΣΕ ΤΥΧΑΙΟΥΣ ΓΡΑΦΟΥΣ

    … FOR THE EXISTENCE OF MANY, SHORT, VERTEX DISJOINT PATHS IN RANDOM GRAPHS.FURTHERMORE, WE PROVE THE EXISTENCE OF A GIANT CONNECTED COMPONENT IN RANDOM GRAPHS WITH EDGE FAULTS. WE ALSO SHOW THAT THIS GIANT COMPONENT IS A CERTIFIABLE EFFICIENT EXPANDER WITH HIGH PROBABILITY. WE PRESENT THE …

    greece Repository record for ΖΗΤΗΜΑΤΑ ΣΥΝΕΚΤΙΚΟΤΗΤΑΣ ΣΕ ΤΥΧΑΙΟΥΣ ΓΡΑΦΟΥΣ (opens in a new tab)

  15. Planning the deployment of fault-tolerant wireless sensor networks

    … where each sensor node must have k vertex-disjoint paths of length ≤ l. To count how many disjoint paths a node has, we propose Counting-Paths. GRASP-ABP deploys fewer relays than GRASP-ARP by focusing only on the most important nodes – those whose failure has the worst effect. To identify …

    cork Repository record for Planning the deployment of fault-tolerant wireless sensor networks (opens in a new tab)

  16. On strong fault tolerance (or strong Menger-connectivity) of multicomputer networks

    … v in Gf , there are min{degf (u), degf (v)} node-disjoint paths in Gf from u to v, where degf (u) and degf (v) are the degrees of the nodes u and v in Gf, respectively. First we study the strong fault tolerance for the popular network structures such as star networks and hypercube networks. We …

    tamu Repository record for On strong fault tolerance (or strong Menger-connectivity) of multicomputer networks (opens in a new tab)

  17. Linear-time algorithms for graphs with bounded branchwidth

    … CUT, GRAPH COLORING, HAMILTONIAN CYCLE, and DISJOINT PATHS). The linearity is achieved assuming the provision of a branch decomposition of the instance graph. We then modify the framework to create a multithreaded framework that uses the existing problem-specific extensions without any …

    rice Repository record for Linear-time algorithms for graphs with bounded branchwidth (opens in a new tab)

  18. Numerical estimates for arm exponents and the acceptance profile in two-dimensional invasion percolation

    … arm exponents when there exist a number of open paths and closed dual paths that extend to the boundary of different sizes of boxes centering at the origin in bond invasion percolation on a plane square lattice by Monte-Carlo simulations. The results turn out to be supportive of the conjectured …

    gatech Repository record for Numerical estimates for arm exponents and the acceptance profile in two-dimensional invasion percolation (opens in a new tab)

Page 1 of 4