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
Apostolico et al. Efficient parallel algorithms for string editing and related problems
Bertolazzi et al. Optimal upward planarity testing of single-source digraphs
Anselin et al. Efficient algorithms for constructing proper higher order spatial lag operators
Gawrychowski et al. Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic ̃O(n^5/3) Time
Agarwal et al. Parametric and kinetic minimum spanning trees
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
Imai et al. Dynamic orthogonal segment intersection search
Korman et al. Labeling schemes for dynamic tree networks
Bertolazzi et al. Quasi-upward planarity
Dinitz et al. Maintaining the classes of 4-edge-connectivity in a graph on-line
Baswana et al. Dynamic DFS in Undirected Graphs: Breaking the O(m) Barrier
Imai et al. Dynamic segment intersection search with applications
Akbari et al. Locality in online, dynamic, sequential, and distributed graph algorithms
Klein et al. A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
Hanaka et al. Parameterized orientable deletion
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
Apers et al. A sublinear time quantum algorithm for st minimum cut on dense simple graphs