A note on two problems in connexion with graphs

1959/12/01 by E. W. Dijkstra, E. Dijkstra · 190 citations
Physics and Astronomy · #Advanced Mathematical Theories and Applications

paper · doi:10.1007/bf01386390

Citations

• On the shortest spanning subtree of a graph and the traveling salesman problem

Cited by

• NetworkCommons: bridging data, knowledge and methods to build and evaluate context-specific biological networks
• Landscape-explicit phylogeography illuminates the ecographic radiation of early archosauromorph reptiles
• Fast Marching Methods
• Resilience and rewiring of the passenger airline networks in the United States
• Computer Folding of Parallel <scp>DNA</scp> G‐Quadruplex: Hitchhiker's Guide to the Conformational Space
• State of the aRt personality research: A tutorial on network analysis of personality data in R
• The Discrete Geodesic Problem
• The latent variable proximal point algorithm for variational problems with inequality constraints
• Recursive Shortest Path Algorithm with Application to Density-integration of Weighted Graphs
• Solving Partial Differential Equations on Manifolds From Incomplete Inter-Point Distance
• Toward Automated Physics-Based Absolute Drug Residence Time Predictions
• Speeding up shortest path algorithms
• Shortest Feasible Paths with Charging Stops for Battery Electric Vehicles
• Finding knowledge paths among scientific disciplines
• Efficient Single-Source Shortest Path and Distance Queries on Large Graphs
• Optimal Path Planning using CAMIS: a Continuous Anisotropic Model for Inclined Surfaces
• A Simple Algorithm For Replacement Paths Problem
• Relating Strong Spatial Cognition to Symbolic Problem Solving --- An\n Example
• StackSeq2Seq: Dual Encoder Seq2Seq Recurrent Networks
• A multidimensional toolkit for elucidating temporal trajectories in cell development <i>in vivo</i>
• On Directed Steiner Trees with Multiple Roots
• Relevant Region Sampling Strategy with Adaptive Heuristic for Asymptotically Optimal Path Planning
• A grid graph-based model for the analysis of 2D indoor spaces
• Half-checking propagators
• The Promotion of Intermodal Transport in Central Europe Through the Design and Realisation of eLogistics Services
• POMP: Pomcp-based Online Motion Planning for active visual search in indoor environments
• RRphylogeography: A new method to find the area of origin of species and the history of past contacts between species
• Algorithms to test open set condition for self-similar set related to P.V. numbers
• First genomic snapshots of recolonising lineages following a devastating earthquake
• Optimization of the directed spanning trees using the weighted matroid intersection algorithm
• The Atlas for the Aspiring Network Scientist
• GRMR: Generalized Regret-Minimizing Representatives
• Estimating congestion zones and travel time indexes based on the floating car data
• Eco-friendly 3D-Routing: A GIS based 3D-Routing-Model to estimate and reduce CO2-emissions of distribution transports
• Determining transmission line path alternatives using a valley-finding algorithm
• Path Planning in Unknown Environments Using Optimal Transport Theory
• User Preferences and the Shortest Path
• Geodesic Paths On 3D Surfaces: Survey and Open Problems
• Multiple-Source Shortest Paths in Embedded Graphs
• Combining detection and tracking for human pose estimation in videos
• Efficient Large-Scale Graph Processing on Hybrid CPU and GPU Systems
• Optimal transport for vector Gaussian mixture models
• Coastal oceanographic connectivity at the global scale: a dataset of pairwise probabilities and travel times derived from biophysical modeling
• DRLViz: Understanding Decisions and Memory in Deep Reinforcement\n Learning
• An easily-implemented, block-based fast marching method with superior sequential and parallel performance
• New and Simplified Distributed Algorithms for Weighted All Pairs Shortest Paths
• Go-Explore: a New Approach for Hard-Exploration Problems
• Context-free Algorithms
• Computational analysis of folding and mutation properties of C5 domain of myosin binding protein C
• Bilevel Optimization Approach to Design of Network of Bike Lanes
• Meme as Building Block for Evolutionary Optimization of Problem Instances
• Automatic Recognition of Landmarks on Digital Dental Models
• Static and Dynamic Path Planning Using Incremental Heuristic Search
• Optimized Graph Based Routing Algorithm for the Angara Interconnect
• Problemy wyznaczania optymalnej trajektorii obiektu na obszarze ograniczonym
• A Tight Lower Bound for Decrease-Key in the Pure Heap Model
• Dynamic Lake Ice Conditions Shape Caribou Water‐Crossing Behavior in the Arctic
• All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication
• Pricing of Connected and Autonomous Vehicles in Mixed-Traffic Networks
• Stable Matching with Incomplete Information in Structured Networks
• A network transformation heuristic approach for the deviation flow refueling location model
• Graph Processing on FPGAs: Taxonomy, Survey, Challenges
• Energy harvesting aware path planning for ambiently-powered multi-robot systems
• Acronym-Meaning Extraction from Corpora Using Multi-Tape Weighted Finite-State Machines
• What Explains Country-Level Differences in Political Belief System Coherence?
• U-Safe: Urban air mobility safe integration into aerodrome via bio-inspired and reinforcement learning-based trajectory management
• Emergency Management Systems and Algorithms: a Comprehensive Survey
• Combining the Connection Scan Algorithm with Contraction Hierarchies
• Machine Learning Based Path Planning for Improved Rover Navigation (Pre-Print Version)
• Superdiffusion on complex networks: the role of shortcuts and long-range interactions
• A global map of travel time to access veterinarians
• An Extension of BIM Using AI: a Multi Working-Machines Pathfinding Solution
• Connectivity and Minimal Distance Spectral Radius of Graphs
• Reconstructing and grounding narrated instructional videos in 3D
• A Survey of Motion Planning and Control Techniques for Self-driving\n Urban Vehicles
• Context-Adaptive Visual Cues for Safe Navigation in Augmented Reality Using Machine Learning
• Evaluating population connectivity for species of conservation concern in the American Great Plains
• Risk-based path planning for autonomous underwater vehicles in an oil spill environment
• SpaceNet: A Remote Sensing Dataset and Challenge Series
• Optimally cutting a surface into a disk
• SCALABLE INTERNETWORKING: Final Technical Report
• Multi-Robot Routing with Time Windows: A Column Generation Approach
• Path planning of multiple autonomous marine vehicles for adaptive sampling using Voronoi-based ant colony optimization
• <i>myAURA</i> : a personalized health library for epilepsy management via knowledge graph sparsification and visualization
• West Nile virus spread in Europe: Phylogeographic pattern analysis and key drivers
• Comparative performance of viral landscape phylogeography approaches
• A practical Single Source Shortest Path algorithm for random directed graphs with arbitrary weight in expecting linear time
• Lasso formulation of the shortest path problem
• A Framework for Searching AND/OR Graphs with Cycles
• Does Google Scholar contain all highly cited documents (1950-2013)?
• Large-Scale Cargo Distribution
• The Geometry of Nonparametric Filament Estimation
• Extended <scp>tight‐binding</scp> quantum chemistry methods
• Human Learning of Unknown Environments in Agile Guidance Tasks
• Fibonacci Heaps Revisited
• Optimizing cycling network design in the city of Parma
• Faster Worst Case Deterministic Dynamic Connectivity
• Anytime Motion Planning on Large Dense Roadmaps with Expensive Edge\n Evaluations
• Optimal control with reset-renewable resources
• Path-ZVA: general, efficient and automated importance sampling for highly reliable Markovian systems
• Extended Dijkstra algorithm and Moore-Bellman-Ford algorithm
• Cell divisions both challenge and refine tissue boundaries in the <i>Drosophila</i> embryo
• Ontological differentiation as a measure of semantic accuracy
• Multi-stencils fast marching method for factored eikonal equations with quadratic anisotropy
• Mobile Robot Path Planning in Dynamic Environments through Globally Guided Reinforcement Learning
• Sparse Graphical Memory for Robust Planning
• The relative influence of habitat density, landscape configuration and spatial sorting on population expansion: a simulation test
• Tax avoidance by redirecting royalty flows: estimating the global revenue loss
• Why some heaps support constant-amortized-time decrease-key operations,\n and others do not
• A general framework for the IT-based clustering methods
• Impact of network structure on the capacity of wireless multihop ad hoc communication
• Approximating meta-heuristics with homotopic recurrent neural networks
• Fused Segmentation of Geometric Models for Myocardium and Coronary Artery via Medial Axis
• Nonparametric Causal Feature Selection for Spatiotemporal Risk Mapping of Malaria Incidence in Madagascar
• Statistical harmonization corrects site effects in functional connectivity measurements from multi‐site fMRI data
• Cooperative Motion Planning for Non-Holonomic Agents with Value\n Iteration Networks
• The Structure of Borders in a Small World
• Automatic Segmentation of Choroid Layer in EDI OCT Images Using Graph Theory in Neutrosophic Space
• Parameter inference from a non-stationary unknown process
• A Dijkstra Seeded Evolutionary Multiobjective Optimization System for a Sustainable User Multimodal Transport Routing
• Evolutionary Algorithms for Optimizing Emergency Exit Placement in Indoor Environments
• Evolutionary history of Jamestown Canyon virus reveals complex multi-vector ecology
• Rapport de recherche sur le problème du plus court chemin contraint
• AI-Powered Personalized Path Planning Using User Behavioural Patterns and Semantic Context for Smart Navigation Systems
• Using satellite imagery to measure the impacts of new highways: An application to India
• SPAGAN: Shortest Path Graph Attention Network
• Topological based classification using graph convolutional networks
• Discovering and measuring giant trees through the integration of multi‐platform lidar data
• Multi‐Scale Geophysical Imaging of a Hydrothermal System in Yellowstone National Park, USA
• Toward Agile Maneuvers in Highly Constrained Spaces: Learning from Hallucination
• Efficient Network Analysis Under Single Link Deletion
• Designing a scalable framework for declarative automation on distributed systems
• Flexible parametrization of graph‐theoretical features from individual‐specific networks for prediction
• MolBar: a molecular identifier for inorganic and organic molecules with full support of stereoisomerism
• Computational detection, characterization, and clustering of microglial cells in a mouse model of fat-induced postprandial hypothalamic inflammation
• From Metaphor to Computation: Constructing the Potential Landscape for Multivariate Psychological Formal Models
• Benchmarking atlas-level data integration in single-cell genomics
• Analyzing the Performance of Graph Neural Networks with Pipe Parallelism
• Map Route Ranking with Weighted Distance using Environmental Factors
• Service Selection using Predictive Models and Monte-Carlo Tree Search
• Thinking Like a Vertex: a Survey of Vertex-Centric Frameworks for Distributed Graph Processing
• Curve Matching, Time Warping, and Light Fields: New Algorithms for Computing Similarity between Curves
• A low complexity algorithm for non-monotonically evolving fronts
• Graph-theoretic autofill
• Repair and Resource Scheduling in Unbalanced Distribution Systems using Neighborhood Search
• An exploration of urban air health navigation system based on dynamic exposure risk forecast of ambient PM2.5
• Coloring rings
• A Lexicographic Search Method for Multi-Objective Motion Planning
• Path-Planning for Unmanned Aerial Vehicles with Environment Complexity Considerations: A Survey
• Transportation Planning and Traffic Flow Models
• Routing of Electric Vehicles in a Stochastic Network with Non-recurrent\n Incidents
• Parallel Shortest-Paths Using Radius Stepping
• Risk-aware Path and Motion Planning for a Tethered Aerial Visual Assistant in Unstructured or Confined Environments
• Deep Manifold Embedding for Hyperspectral Image Classification
• Zero-shot Imitation Learning from Demonstrations for Legged Robot Visual Navigation
• Linear-Space Computation of the Edit-Distance between a String and a Finite Automaton
• Single source shortest paths in H-minor free graphs
• DRLViz: Understanding Decisions and Memory in Deep Reinforcement Learning
• Dyna-H: a heuristic planning reinforcement learning algorithm applied to role-playing-game strategy decision systems
• Algorithm for Overcoming the Curse of Dimensionality for State-dependent Hamilton-Jacobi equations
• Environmental emissions influencing solar photovoltaic waste management in Australia: An optimised system network of waste collection facilities
• Impact of Traffic Conditions and Carpool Lane Availability on Peer to\n Peer Ridesharing Demand
• Generic and Efficient Solution Solves the Shortest Paths Problem in Square Runtime
• Encoded Prior Sliced Wasserstein AutoEncoder for learning latent\n manifold representations
• Counting Down Thunder: Timing Attacks on Privacy in Payment Channel Networks
• The ubiquitous efficiency of going further: how street networks affect travel speed
• Efficient Top-K Retrieval in Online Social Tagging Networks
• Algorithms for Non-Linear and Stochastic Resource Constrained Shortest\n Paths
• Multi-Stage Improved Route Planning Approach: theoretical foundations
• Open problem on risk-aware planning in the plane
• Measuring Neighborhood Walkability Using Detour Factor Distributions
• Facial Surface Analysis using Iso-Geodesic Curves in Three Dimensional Face Recognition System
• Surrogate Search As a Way to Combat Harmful Effects of Ill-behaved\n Evaluation Functions
• Achieving sub-second IGP convergence in large IP networks
• Probabilistic Safety Programs
• Learning with Algorithmic Supervision via Continuous Relaxations
• Optimal Approximation Algorithms for Multi-agent Combinatorial Problems with Discounted Price Functions
• GSoFa: Scalable Sparse Symbolic LU Factorization on GPUs
• Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards
• A comprehensive theory of cascading via-paths and the reciprocal pointer\n chain method
• Learning the optimally coordinated routes from the statistical mechanics of polymers
• Finding the Loops that Matter
• Simple odd β-cycle inequalities for binary polynomial optimization
• DeePore: A deep learning workflow for rapid and comprehensive characterization of porous materials
• Validating mechanistic models of fluid displacement during imbibition
• Safest Nearby Neighbor Queries in Road Networks (Full Version)
• Combining the Shortest Paths and the Bottleneck Paths Problems
• k-best enumeration
• A Fast Planning Approach for 3D Short Trajectory with a Parallel Framework
• Edsger W. Dijkstra [wikipedia]