A fast algorithm for the gas station problem

DOI10.1016/J.IPL.2017.11.009MaRDI QIDQ1685029zbMATH OpenOpenAlexFDO

Authors Kleitos Papadopoulos, Demetres Christofides

Publication date 13 December 2017

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

Full work available at URL https://arxiv.org/abs/1706.00195

zbMATH Keywords

algorithm complexityalgorithmsgas station problemtransportation

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Transportation, logistics and supply chain management (90B06)

Abstract: In the gas station problem we want to find the cheapest path between two vertices of an $n$-vertex graph. Our car has a specific fuel capacity and at each vertex we can fill our car with gas, with the fuel cost depending on the vertex. Furthermore, we are allowed at most $Delta$ stops for refuelling. In this short paper we provide an algorithm solving the problem in $O(Delta{n}^2+n^{2}logn)$ steps improving an earlier result by Khuller, Malekian and Mestre.

Recommendations

• To Fill or Not to Fill: The Gas Station Problem
• To fill or not to fill, the gas station problem
• scientific article; zbMATH DE number 3845637
• Fly cheaply: On the minimum fuel consumption problem
• Publication:4503663

Cites work

• A linear-time algorithm for finding optimal vehicle refueling policies
• Finding Optimal Refueling Policies in Transportation Networks
• Introduction to algorithms.
• To fill or not to fill, the gas station problem

Cited in

(4)

• On the statistical evaluation of algorithmic's computational experimentation with infeasible solutions
• To fill or not to fill, the gas station problem
• scientific article; zbMATH DE number 3845637 (Why is no real title available?)
• To Fill or Not to Fill: The Gas Station Problem

This page was built for publication: A fast algorithm for the gas station problem

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