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

Sommer, 2014 - Google Patents

Shortest-path queries in static networks

Sommer, 2014

View PDF
Document ID
14702005425646648644
Author
Sommer C
Publication year
Publication venue
ACM Computing Surveys (CSUR)

External Links

Snippet

We consider the point-to-point (approximate) shortest-path query problem, which is the following generalization of the classical single-source (SSSP) and all-pairs shortest-path (APSP) problems: we are first presented with a network (graph). A so-called preprocessing …
Continue reading at www.chsommer.com (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/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/50—Computer-aided design
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06N—COMPUTER SYSTEMS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computer systems based on biological models
    • G06N3/12—Computer systems based on biological models using genetic models
    • G06N3/126—Genetic algorithms, i.e. information processing using digital simulations of the genetic system
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06N—COMPUTER SYSTEMS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N99/00—Subject matter not provided for in other groups of this subclass
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99941—Database schema or data structure
    • Y10S707/99943—Generating database or data structure, e.g. via user interface
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06N—COMPUTER SYSTEMS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N5/00—Computer systems utilising knowledge based models

Similar Documents

Publication Publication Date Title
Sommer Shortest-path queries in static networks
Madkour et al. A survey of shortest-path algorithms
Whitley Permutations
Greistorfer A tabu scatter search metaheuristic for the arc routing problem
Delling et al. Robust distance queries on massive networks
Botea et al. Near optimal hierarchical path-finding.
Gutin et al. The traveling salesman problem and its variations
Krishnamoorthy et al. Comparison of algorithms for the degree constrained minimum spanning tree
Möhring et al. Partitioning graphs to speedup Dijkstra's algorithm
Sankaranarayanan et al. Efficient query processing on spatial networks
Hershberger et al. Finding the k shortest simple paths: A new algorithm and its implementation
Samet et al. Scalable network distance browsing in spatial databases
Ahuja et al. Some recent advances in network flows
Liu et al. Efficient constrained shortest path query answering with forest hop labeling
Zhang et al. Efficient maximal spatial clique enumeration
Liu et al. FHL-cube: multi-constraint shortest path querying with flexible combination of constraints
Liu et al. Multi-constraint shortest path using forest hop labeling
Lu et al. A beamlet-based graph structure for path planning using multiscale information
Xia et al. Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs
Tucnik et al. Comparative analysis of selected path-planning approaches in large-scale multi-agent-based environments
Zheng et al. Workload-aware shortest path distance querying in road networks
CN115331751A (en) Chemical pathway analysis and prediction method based on machine learning and terminal equipment
Rizzi Genetic operators for hierarchical graph clustering
CN103345509A (en) Method and system for obtaining grading partition tree of dual-reverse furthest neighbors on road network
Honiden et al. Approximate shortest path queries using Voronoi duals