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

\(k\)-Dominating Setapproximation algorithmsgraph algorithmsminimum distortion embedding into the lineminimum eccentricity shortest pathNP-complete problemsW[2-hard problems]

Mathematics Subject Classification ID

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

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

(12)

• On the minimum eccentricity isometric cycle problem
• 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
• On the minimum eccentricity shortest path problem
• 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
• Parameterized algorithms for eccentricity shortest path problem
• Additive approximation algorithm for geodesic centers in -hyperbolic graphs
• New fault domains for conformance testing of finite state machines
• Decomposing a graph into shortest paths with bounded eccentricity

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)