Nothing Special   »   [go: up one dir, main page]

Klein et al., 1998 - Google Patents

A fully dynamic approximation scheme for shortest paths in planar graphs

Klein et al., 1998

View PDF
Document ID
15971170722712181800
Author
Klein P
Subramanian S
Publication year
Publication venue
Algorithmica

External Links

Snippet

In this paper we give a fully dynamic approximation scheme for maintaining all-pairs shortest paths in planar networks. Given an error parameter ϵ such that 0<ϵ, our algorithm maintains approximate all-pairs shortest paths in an undirected planar graph G with nonnegative edge …
Continue reading at 128.148.32.110 (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30961—Trees
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30312—Storage and indexing structures; Management thereof
    • G06F17/30321—Indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30958—Graphs; Linked lists
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30386—Retrieval requests
    • G06F17/30424—Query processing
    • G06F17/30533—Other types of queries
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30994—Browsing or visualization
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/50—Computer-aided design
    • G06F17/5009—Computer-aided design using simulation

Similar Documents

Publication Publication Date Title
Klein et al. A fully dynamic approximation scheme for shortest paths in planar graphs
Eppstein et al. Dynamic graph algorithms
Anselin et al. Efficient algorithms for constructing proper higher order spatial lag operators
Di Battista et al. Spirality and optimal orthogonal drawings
Agarwal et al. Parametric and kinetic minimum spanning trees
Baswana et al. Dynamic DFS in undirected graphs: Breaking the o(m) barrier
Kanevsky et al. On-line maintenance of the four-connected components of a graph
Morrison et al. Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
Demetrescu et al. Dynamic graphs
Borradaile et al. All-pairs minimum cuts in near-linear time for surface-embedded graphs
Wang et al. Near-optimal algorithms for shortest paths in weighted unit-disk graphs
Imai et al. Dynamic orthogonal segment intersection search
Dujmović et al. On the parameterized complexity of layered graph drawing
Choumane et al. Core expansion: a new community detection algorithm based on neighborhood overlap
Bertolazzi et al. Quasi-upward planarity
Hanauer et al. Recent advances in fully dynamic graph algorithms
Imai et al. Dynamic segment intersection search with applications
Klein et al. A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
Apers et al. Quantum complexity of minimum cut
Abraham et al. Dynamic Decremental Approximate Distance Oracles with $(1+\epsilon, 2) $ stretch
Berry et al. Triangulation and clique separator decomposition of claw-free graphs
Mozes et al. Efficient vertex-label distance oracles for planar graphs
Maestre et al. A cooperative game theory approach to the PageRank problem
Di Giacomo et al. On the parameterized complexity of bend-minimum orthogonal planarity
Høgemo et al. On dasgupta’s hierarchical clustering objective and its relation to other graph parameters