On the minimum eccentricity shortest path problem

DOI10.1016/J.TCS.2017.07.004MaRDI QIDQ2404081zbMATH OpenOpenAlexFDO

Authors Feodor F. Dragan, Arne Leitert

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

zbMATH Keywords

approximation algorithmsgraph algorithmsNP-complete problems\(k\)-Dominating Setminimum distortion embedding into the lineminimum eccentricity shortest pathW[2-hard problems]

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12)

Recommendations

• On the minimum eccentricity shortest path problem
• Minimum eccentricity shortest path problem: an approximation algorithm and relation with the k-laminarity problem
• Minimum eccentricity shortest path problem with respect to structural parameters
• Minimum eccentricity shortest path problem with respect to structural parameters
• Parameterized algorithms for eccentricity shortest path problem
• Minimum eccentricity shortest paths in some structured graph classes
• Minimum eccentricity shortest paths in some structured graph classes
• Approximate Euclidean shortest paths amid convex obstacles
• Decomposing a graph into shortest paths with bounded eccentricity
• Decomposing a graph into shortest paths with bounded eccentricity

Cites work

• An exact algorithm for minimum distortion embedding
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Bandwidth and distortion revisited
• Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
• Distortion Is Fixed Parameter Tractable
• Domination and total domination on asteroidal triple-free graphs
• Fundamentals of parameterized complexity
• HAMILTONian circuits in chordal bipartite graphs
• Hardness and approximation of minimum distortion embeddings
• Line-distortion, bandwidth and path-length of a graph
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• Low-distortion embeddings of general metrics into the line
• Minimum eccentricity shortest path problem: an approximation algorithm and relation with the k-laminarity problem
• Minimum eccentricity shortest paths in some structured graph classes
• On the minimum eccentricity shortest path problem
• Optimal binary space partitions in the plane

Cited in

(11)

• Decomposing a graph into shortest paths with bounded eccentricity
• Minimum eccentricity shortest path problem with respect to structural parameters
• Minimum eccentricity shortest path problem with respect to structural parameters
• Additive approximation algorithm for geodesic centers in -hyperbolic graphs
• On the minimum eccentricity shortest path problem
• On the minimum eccentricity isometric cycle problem
• Parameterized algorithms for eccentricity shortest path problem
• Decomposing a graph into shortest paths with bounded eccentricity
• Minimum eccentricity shortest paths in some structured graph classes
• Minimum eccentricity shortest paths in some structured graph classes
• Minimum eccentricity shortest path problem: an approximation algorithm and relation with the k-laminarity problem

This page was built for publication: On the minimum eccentricity shortest path problem

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