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

DOI10.1007/978-3-319-48749-6_16zbMath1484.68151arXiv1609.04593OpenAlexW2521878023MaRDI QIDQ2958315

Etienne Birmelé, Léo Planche, Fabien de Montgolfier

Publication date: 1 February 2017

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1609.04593

zbMATH Keywords

BFSgraph theorydiametereccentricityapproximation algorithmsgraph search\(k\)-laminar graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12) Approximation algorithms (68W25)

Related Items (6)

On the minimum eccentricity shortest path problem ⋮ Parameterized algorithms for eccentricity shortest path problem ⋮ Minimum eccentricity shortest path problem with respect to structural parameters ⋮ Minimum eccentricity shortest path problem with respect to structural parameters ⋮ Unnamed Item ⋮ Decomposing a graph into shortest paths with bounded eccentricity

Cites Work

• A linear time algorithm to compute a dominating path in an AT-free graph
• Characterization of graphs dominated by induced paths
• Graph minors. I. Excluding a forest
• Isomorphism for graphs of bounded distance width
• Representation of a finite graph by a set of intervals on the real line
• On the Minimum Eccentricity Shortest Path Problem
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Asteroidal Triple-Free Graphs
• On the power of BFS to determine a graph's diameter
• Dominating Pair Graphs

This page was built for publication: Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem