Exploration of graphs with excluded minors

DOI10.1016/J.JCSS.2025.103725MaRDI QIDQ6885357zbMATH OpenFDO

Authors Júlia Baligács, Y. Disser, Irene Heinrich, P. Schweitzer

Publication date 11 December 2025

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2025.103725

zbMATH Keywords

bounded-genus graphscompetitive analysisgraph explorationgraph spannersminor-free graphsonline algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Cites work

• A general lower bound for collaborative tree exploration
• Algorithms – ESA 2005
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• An improved lower bound for competitive graph exploration
• An improved upper bound for the online graph exploration problem on unicyclic graphs
• Approximation algorithms via contraction decomposition
• Constructing competitive tours from local information
• Exploration of graphs with excluded minors
• Exploring an unknown graph
• Exploring Unknown Environments
• Fast collaborative graph exploration
• Graph spanners
• Graphs on surfaces
• scientific article; zbMATH DE number 1670877 (Why is no real title available?)
• scientific article; zbMATH DE number 3179262 (Why is no real title available?)
• scientific article; zbMATH DE number 1303538 (Why is no real title available?)
• scientific article; zbMATH DE number 2119747 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• Light graphs with small routing cost
• Light spanners in bounded pathwidth graphs
• Lower and upper competitive bounds for online directed graph exploration
• Minor-free graphs have light spanners
• Minors in expanding graphs
• Near-optimal light spanners
• On sparse spanners of weighted graphs
• On the nearest neighbor rule for the traveling salesman problem
• Online k-server routing problems
• Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs
• Online graph exploration on trees, unicyclic graphs and cactus graphs
• Online graph exploration with advice
• Online graph exploration: New results on old and new algorithms
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• The greedy spanner is existentially optimal
• Tight Bounds for Online TSP on the Line
• Tight bounds for undirected graph exploration with pebbles and multiple agents

This page was built for publication: Exploration of graphs with excluded minors

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