Decomposing a graph into shortest paths with bounded eccentricity

DOI10.1016/j.dam.2020.03.060zbMath1443.05154OpenAlexW3018472973MaRDI QIDQ777405

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

Publication date: 7 July 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.03.060

zbMATH Keywords

BFSgraph decompositiongraph clusteringdistance labelingMESP

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12)

Related Items (2)

Minimum eccentricity shortest path problem with respect to structural parameters ⋮ Minimum eccentricity shortest path problem with respect to structural parameters

Cites Work

• Unnamed Item
• Unnamed Item
• Finding the longest isometric cycle in a graph
• Distortion is Fixed Parameter Tractable
• Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem
• On the Minimum Eccentricity Shortest Path Problem
• Approximate distance oracles
• Low-distortion embeddings of general metrics into the line
• Distance labeling in graphs
• Proximity-preserving labeling schemes
• Algorithms and Computation

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