Shortest paths without a map
From MaRDI portal
Publication:809612
DOI10.1016/0304-3975(91)90263-2zbMath0733.68065OpenAlexW1992876208WikidataQ126634813 ScholiaQ126634813MaRDI QIDQ809612
Mihalis Yannakakis, Christos H. Papadimitriou
Publication date: 1991
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(91)90263-2
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Competitive algorithms for the weighted server problem, Meeting a deadline: shortest paths on stochastic directed acyclic graphs with information gathering, Traveling salesman problems in temporal graphs, Competitive exploration of rectilinear polygons, Competitive online routing in geometric graphs, The weighted 2-server problem, The CNN problem and other \(k\)-server variants, Agent searching in a tree and the optimality of iterative deepening, On-line algorithms for weighted bipartite matching and stable marriages, Walking streets faster, Approximation and complexity of multi-target graph search and the Canadian traveler problem, Going home through an unknown street, On the complexity of partially observed Markov decision processes, The Steiner traveling salesman problem with online edge blockages, Treasure Hunt with Advice, An on-line multi-CBR agent dispatching algorithm, ONLINE ROUTING IN CONVEX SUBDIVISIONS, PH-graphs for analyzing shortest path problems with correlated traveling times, The Steiner traveling salesman problem with online advanced edge blockages, The \(k\)-Canadian travelers problem with communication, Online routing and searching on graphs with blocked edges, Optimal on-line algorithms for walking with minimum number of turns in unknown streets, Online graph exploration on trees, unicyclic graphs and cactus graphs, Approximating the Canadian traveller problem with online randomization, Shortest paths with shortest detours. A biobjective routing problem, Interactive foundations of computing, Fibonacci helps to evacuate from a convex region in a grid network, On the online multi-agent O-D \(k\)-Canadian traveler problem, Worst-case optimal exploration of terrains with obstacles, An online optimization approach for post-disaster relief distribution with online blocked edges, Complexity of Canadian traveler problem variants, Online graph exploration: New results on old and new algorithms, On a simple depth-first search strategy for exploring unknown graphs, Searching game trees under a partial order, Evacuating two robots from multiple unknown exits in a circle, Complexity of planning for connected agents in a partially known environment, The influence of maximum \((s,t)\)-cuts on the competitiveness of deterministic strategies for the Canadian traveller problem, The beachcombers' problem: walking and searching with mobile robots, Competitive analysis of randomized online strategies for the multi-agent \(k\)-Canadian traveler problem, On the randomized online strategies for the \(k\)-Canadian traveler problem, Optimal obstacle placement with disambiguations, Penalty-Based Algorithms for the Stochastic Obstacle Scene Problem, Canadian traveller problem with predictions, A simple ant colony optimizer for stochastic shortest path problems, Discussion of ``Network routing in a dynamic environment, The covering Canadian traveller problem, The \(k\)-server problem, Online algorithms for searching and exploration in the plane, Online Strategies for Evacuating from a Convex Region in the Plane, Efficient strategies for robot navigation in unknown environment, The k-Canadian Travelers Problem with Communication, Agent search in uniform b-ary trees: Multiple goals and unequal costs, The reset disambiguation policy for navigating stochastic obstacle fields, Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints, Online covering salesman problem, Weighted online minimum latency problem with edge uncertainty, Online Graph Exploration: New Results on Old and New Algorithms, Reactive synthesis without regret, Tree exploration with advice, COMPETITIVE COMPLEXITY OF MOBILE ROBOT ON-LINE MOTION PLANNING PROBLEMS, A note on the \(k\)-Canadian traveller problem, Lower bounds in on-line geometric searching, Metrical service systems with multiple servers, Online matching on a line, The ultimate strategy to search on \(m\) rays?, On-line path planning in an unknown polygonal environment, Parallel searching on \(m\) rays, Impact of topographic information on graph exploration efficiency, LOWER BOUNDS FOR STREETS AND GENERALIZED STREETS, On the two-dimensional cow search problem, Weighted nearest neighbor algorithms for the graph exploration problem on cycles, Multiple canadians on the road: minimizing the distance competitive ratio, Efficient, optimal stochastic-action selection when limited by an action budget, MULTIDIMENSIONAL ONLINE MOTION PLANNING FOR A SPHERICAL ROBOT, An AO* Based Exact Algorithm for the Canadian Traveler Problem, The \(m\)-Steiner traveling salesman problem with online edge blockages, Advice complexity of treasure hunt in geometric terrains, Intuitionistic Layered Graph Logic, Utility-based on-line exploration for repeated navigation in an embedded graph, A representation theorem for minmax regret policies, Unnamed Item, The Canadian Traveller Problem and its competitive analysis, A Risk-Reward Competitive Analysis for the Recoverable Canadian Traveller Problem, Piecemeal graph exploration by a mobile robot., Optimal robot localization in trees, The power of a pebble: Exploring and mapping directed graphs, Generalized Canadian traveller problems, Complexity of node coverage games, An optimal randomized online algorithm for the \(k\)-Canadian traveller problem on node-disjoint paths, Performance bounds for planning in unknown terrain
Cites Work
