Distance-Preserving Subgraphs of Interval Graphs

DOI10.4230/LIPIcs.ESA.2017.39zbMath1442.05140arXiv1708.03081OpenAlexW2963209922MaRDI QIDQ5111726

Kshitij Gajjar

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1708.03081

zbMATH Keywords

shortest pathinterval graphsbit-reversal permutation matrixdistance-preserving subgraphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (4)

Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Graph spanners: a tutorial review ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ New Results on Linear Size Distance Preservers

Cites Work

• Unnamed Item
• Clique partitions, graph compression and speeding-up algorithms
• Preserving Terminal Distances Using Minors
• Sparse Sourcewise and Pairwise Distance Preservers
• Electing a leader in a synchronous ring
• Graph spanners
• Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
• Distance-Preserving Graph Contractions
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Logarithmic Lower Bounds in the Cell-Probe Model
• Cutting Corners Cheaply, or How to Remove Steiner Points

This page was built for publication: Distance-Preserving Subgraphs of Interval Graphs