On the minimum eccentricity shortest path problem
DOI10.1016/j.tcs.2017.07.004zbMath1373.68266OpenAlexW2734550876MaRDI QIDQ2404081
Arne Leitert, Feodor F. Dragan
Publication date: 12 September 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2017.07.004
NP-complete problemsgraph algorithmsapproximation algorithmsminimum eccentricity shortest path\(k\)-Dominating Setminimum distortion embedding into the lineW[2-hard problems]
Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (4)
Cites Work
- Unnamed Item
- Fundamentals of parameterized complexity
- Bandwidth and distortion revisited
- Line-distortion, bandwidth and path-length of a graph
- An exact algorithm for minimum distortion embedding
- Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
- Hardness and approximation of minimum distortion embeddings
- HAMILTONian circuits in chordal bipartite graphs
- Domination and total domination on asteroidal triple-free graphs
- Minimum Eccentricity Shortest Paths in some Structured Graph Classes
- Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem
- On the Minimum Eccentricity Shortest Path Problem
- Optimal Binary Space Partitions in the Plane
- Low-distortion embeddings of general metrics into the line
- Distortion Is Fixed Parameter Tractable
- Linear time algorithms for dominating pairs in asteroidal triple-free graphs
This page was built for publication: On the minimum eccentricity shortest path problem
