Decomposing a graph into shortest paths with bounded eccentricity

DOI10.4230/LIPICS.ISAAC.2017.15zbMATH Open1457.05083MaRDI QIDQ5136231FDOQ5136231

Authors Etienne Birmelé, Fabien De Montgolfier, Léo Planche, Laurent Viennot 

Publication date 25 November 2020

zbMATH Keywords

BFSgraph clusteringgraph decompositiondistance labelingMESP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Decomposing a graph into shortest paths with bounded eccentricity
• Minimum eccentricity shortest path problem: an approximation algorithm and relation with the \(k\)-laminarity problem
• On the minimum eccentricity shortest path problem
• On the minimum eccentricity shortest path problem
• Minimum eccentricity shortest paths in some structured graph classes

Cites Work

• scientific article; zbMATH DE number 3636876 (Why is no real title available?)
• Algorithms and Computation
• Approximate distance oracles
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Distance labeling in graphs
• Distortion is fixed parameter tractable
• Finding the longest isometric cycle in a graph
• Low-distortion embeddings of general metrics into the line
• Minimum eccentricity shortest path problem: an approximation algorithm and relation with the \(k\)-laminarity problem
• On the minimum eccentricity shortest path problem
• Proximity-preserving labeling schemes

Cited In (5)

• On the minimum eccentricity isometric cycle 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

This page was built for publication: Decomposing a graph into shortest paths with bounded eccentricity

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