Weighted nearest neighbor algorithms for the graph exploration problem on cycles

DOI10.1016/J.IPL.2009.10.013zbMATH Open1206.68369OpenAlexW2032799093MaRDI QIDQ990116FDOQ990116

Authors Yuichi Asahiro, Eiji Miyano, Shuichi Miyazaki, Takuro Yoshimuta

Publication date 2 September 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2009.10.013

zbMATH Keywords

competitive ratioon-line algorithmsgraph exploration problemweighted nearest neighbor

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Weighted Nearest Neighbor Algorithms for the Graph Exploration Problem on Cycles
• Faster approximation algorithms for computing shortest cycles on weighted graphs
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• Worst case analysis of nearest neighbour algorithms for the minimum weighted directed \(k\)-cycle problem
• Improved Approximation Algorithms for Weighted Hypergraph Embedding in a Cycle
• scientific article; zbMATH DE number 7310218
• Algorithms for finding the minimum cycle mean in the weighted directed graph
• scientific article; zbMATH DE number 4101240
• On nearest-neighbor graphs
• On nearest-neighbor graphs

Cites work

• scientific article; zbMATH DE number 1003229 (Why is no real title available?)
• scientific article; zbMATH DE number 6472590 (Why is no real title available?)
• Algorithms for the on-line travelling salesman
• Algorithms – ESA 2005
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Constructing competitive tours from local information
• Exploring Unknown Environments
• How to learn an unknown environment. I
• Impact of memory size on graph exploration capability
• ONLINE ROUTING IN CONVEX SUBDIVISIONS
• Shortest paths without a map
• The polygon exploration problem
• Tree exploration with little memory

Cited in

(7)

• An improved upper bound for the online graph exploration problem on unicyclic graphs
• An improved lower bound for competitive graph exploration
• Worst case analysis of nearest neighbour algorithms for the minimum weighted directed \(k\)-cycle problem
• Weighted Nearest Neighbor Algorithms for the Graph Exploration Problem on Cycles
• Online Graph Exploration: New Results on Old and New Algorithms
• Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs
• Online graph exploration: New results on old and new algorithms

This page was built for publication: Weighted nearest neighbor algorithms for the graph exploration problem on cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990116)