2026-07-24T12:38:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7879 2024-03-06T10:41:20Z ddc:004 open_access

Distance-Preserving Subgraphs of Interval Graphs Gajjar, Kshitij Radhakrishnan, Jaikumar interval graphs shortest path distance-preserving subgraphs bit-reversal permutation matrix 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kshitij Gajjar and Jaikumar Radhakrishnan 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.39 urn:nbn:de:0030-drops-78798 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.39 eng https://creativecommons.org/licenses/by/3.0/legalcode