# Minimum Eccentricity Shortest Path Problem with Respect to Structural Parameters

Preprint · Martin Kučera, Ondřej Suchý

- Archive id: arxiv:2008.07898
- Published: 2020-08-18
- DOI: https://doi.org/10.1007/978-3-030-79987-8_31
- arXiv: https://arxiv.org/abs/2008.07898
- Source URL: https://arxiv.org/abs/2008.07898
- PDF: https://arxiv.org/pdf/2008.07898
- Provenance: arxiv

## Abstract

The Minimum Eccentricity Shortest Path Problem consists in finding a shortest path with minimum eccentricity in a given undirected graph. The problem is known to be NP-complete and W\[2\]-hard with respect to the desired eccentricity. We present fpt-algorithms for the problem parameterized by the modular width, distance to cluster graph, the combination of treewidth with the desired eccentricity, and maximum leaf number.

_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.