Document Open Access Logo

Decomposing a Graph into Shortest Paths with Bounded Eccentricity

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.15.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Etienne Birmelé, Fabien de Montgolfier, Léo Planche, and Laurent Viennot. Decomposing a Graph into Shortest Paths with Bounded Eccentricity. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.15

Abstract

We introduce the problem of hub-laminar decomposition which generalizes that of computing a shortest path with minimum eccentricity (MESP). Intuitively, it consists in decomposing a graph into several paths that collectively have small eccentricity and meet only near their extremities. The problem is related to computing an isometric cycle with minimum eccentricity (MEIC). It is also linked to DNA reconstitution in the context of metagenomics in biology. We show that a  graph having such a decomposition with long enough paths can be decomposed in polynomial time with approximated guaranties on the parameters of the decomposition. Moreover, such a decomposition with few paths allows to compute a compact representation of distances with additive distortion. We also show that having an isometric cycle with small eccentricity is related to the possibility of embedding the graph in a cycle with low distortion.

Subject Classification

Keywords
  • Graph Decomposition
  • Graph Clustering
  • Distance Labeling
  • BFS
  • MESP

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Patrice Assouad. étude d'une dimension métrique liée à la possibilité de plongements dans Rⁿ. C. R. Acad. Sci. Paris Sér. A-B, 288(15):A731-A734, 1979. Google Scholar
  2. Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, and Anastasios Sidiropoulos. Low-distortion embeddings of general metrics into the line. In SToC 2005, pages 225-233. ACM, 2005. URL: http://dx.doi.org/10.1145/1060590.1060624.
  3. Mihai Badoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, and Anastasios Sidiropoulos. Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In SODA 2005, pages 119-128. SIAM, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070449.
  4. Etienne Birmelé, Fabien de Montgolfier, and Léo Planche. Minimum eccentricity shortest path problem: An approximation algorithm and relation with the k-laminarity problem. In Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Hong Kong, China, December 16-18, 2016, Proceedings, pages 216-229, 2016. URL: http://dx.doi.org/10.1007/978-3-319-48749-6_16.
  5. Feodor F. Dragan and Arne Leitert. On the minimum eccentricity shortest path problem. In Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, pages 276-288, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21840-3_23.
  6. Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances A. Rosamond, and Saket Saurabh. Distortion is fixed parameter tractable. TOCT, 5(4):16:1-16:20, 2013. URL: http://dx.doi.org/10.1145/2489789.
  7. Cyril Gavoille and Olivier Ly. Distance labeling in hyperbolic graphs. In ISAAC 2005, volume 3827 of Lecture Notes in Computer Science, pages 1071-1079. Springer, 2005. URL: http://dx.doi.org/10.1007/11602613_106.
  8. Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. Distance labeling in graphs. J. Algorithms, 53(1):85-112, 2004. URL: http://dx.doi.org/10.1016/j.jalgor.2004.05.002.
  9. Piotr Indyk. Algorithmic applications of low-distortion geometric embeddings. In FOCS 2001, pages 10-33. IEEE Computer Society, 2001. URL: http://dx.doi.org/10.1109/SFCS.2001.959878.
  10. Piotr Indyk and Jiří Matoušek. Low-distortion embeddings of finite metric spaces. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, Second Edition., pages 177-196. Chapman and Hall/CRC, 2004. URL: http://dx.doi.org/10.1201/9781420035315.ch8.
  11. Daniel Lokshtanov. Finding the longest isometric cycle in a graph. Discrete Applied Mathematics, 12(157):2670-2674, 2009. Google Scholar
  12. David Peleg. Proximity-preserving labeling schemes. Journal of Graph Theory, 33(3):167-176, 2000. URL: http://dx.doi.org/10.1002/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5.
  13. Jimmy H et al. Saw. Exploring microbial dark matter to resolve the deep archaeal ancestry of eukaryotes. Phil. Trans. R. Soc. B, 370(1678):20140328, 2015. Google Scholar
  14. Torsten Thomas, Jack Gilbert, and Folker Meyer. Metagenomics-a guide from sampling to data analysis. Microbial informatics and experimentation, 2(1):3, 2012. Google Scholar
  15. Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1-24, 2005. URL: http://dx.doi.org/10.1145/1044731.1044732.
  16. Finn Völkel, Eric Bapteste, Michel Habib, Philippe Lopez, and Chloe Vigliotti. Read networks and k-laminar graphs. arXiv:1603.01179, Mar 2016. URL: https://hal.inria.fr/hal-01282715.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact