# Minimum Eccentricity Shortest Path Problem: an Approximation Algorithm and Relation with the k-Laminarity Problem

Preprint · Etienne Birmelé, Fabien De Montgolfier, Léo Planche

- Archive id: arxiv:1609.04593
- Published: 2016-09-15
- arXiv: https://arxiv.org/abs/1609.04593
- Source URL: https://arxiv.org/abs/1609.04593
- PDF: https://arxiv.org/pdf/1609.04593
- Provenance: arxiv

## Abstract

The Minimum Eccentricity Shortest Path (MESP) Problem consists in determining a shortest path (a path whose length is the distance between its extremities) of minimum eccentricity in a graph. It was introduced by Dragan and Leitert \[9\] who described a linear-time algorithm which is an 8-approximation of the problem. In this paper, we study deeper the double-BFS procedure used in that algorithm and extend it to obtain a linear-time 3-approximation algorithm. We moreover study the link between the MESP problem and the notion of laminarity, introduced by V{ö}lkel et al \[12\], corresponding to its restriction to a diameter (i.e. a shortest path of maximum length), and show tight bounds between MESP and laminarity parameters.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.