Distance-Preserving Subgraphs of Interval Graphs

File

Author Details

Kshitij Gajjar

Jaikumar Radhakrishnan

Cite As Get BibTex

Kshitij Gajjar and Jaikumar Radhakrishnan. Distance-Preserving Subgraphs of Interval Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 39:1-39:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.39

Abstract

We consider the problem of finding small distance-preserving subgraphs of undirected, unweighted interval graphs that have k terminal vertices. We show that every interval graph admits a distance-preserving subgraph with O(k log k) branching vertices. We also prove a matching lower bound by exhibiting an interval graph based on bit-reversal permutation matrices. In addition, we show that interval graphs admit subgraphs with O(k) branching vertices that approximate distances up to an additive term of +1.

Subject Classification

Keywords

interval graphs
shortest path
distance-preserving subgraphs
bit-reversal permutation matrix

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Yun Kuen Cheung, Gramoz Goranci, and Monika Henzinger. Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 131:1-131:14, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.131.
James W Cooley and John W Tukey. An algorithm for the machine calculation of complex fourier series. Mathematics of computation, 19(90):297-301, 1965.
Don Coppersmith and Michael Elkin. Sparse sourcewise and pairwise distance preservers. SIAM Journal on Discrete Mathematics, 20(2):463-501, 2006.
Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, and Frieder Smolny. Distance-preserving graph contractions. CoRR, abs/1705.04544, 2017. URL: http://arxiv.org/abs/1705.04544.
Tomás Feder and Rajeev Motwani. Clique partitions, graph compression and speeding-up algorithms. J. Comput. System Sci., 51(2):261-272, 1995. URL: http://dx.doi.org/10.1006/jcss.1995.1065.
Greg N Frederickson and Nancy A Lynch. Electing a leader in a synchronous ring. Journal of the ACM (JACM), 34(1):98-115, 1987.
Anupam Gupta. Steiner points in tree metrics don't (really) help. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 220-227. Society for Industrial and Applied Mathematics, 2001.
Lior Kamma, Robert Krauthgamer, and Huy L Nguyên. Cutting corners cheaply, or how to remove steiner points. SIAM Journal on Computing, 44(4):975-995, 2015.
Robert Krauthgamer, Huy Nguyên, and Tamar Zondiner. Preserving terminal distances using minors. SIAM Journal on Discrete Mathematics, 28(1):127-141, 2014. URL: http://dx.doi.org/10.1137/120888843.
Robert Krauthgamer and Tamar Zondiner. Preserving terminal distances using minors. In Automata, Languages, and Programming, volume 7391 of Lecture Notes in Computer Science, pages 594-605. Springer Berlin Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_50.
David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. URL: http://dx.doi.org/10.1002/jgt.3190130114.
Mihai Pǎtraşcu and Erik D Demaine. Logarithmic lower bounds in the cell-probe model. SIAM Journal on Computing, 35(4):932-963, 2006.

Distance-Preserving Subgraphs of Interval Graphs

Authors Kshitij Gajjar, Jaikumar Radhakrishnan