@article{Madani_Maheshwari_2024, title={Distance-Preserving Graph Compression Techniques}, volume={28}, url={https://jgaa.info/index.php/jgaa/article/view/2933}, DOI={10.7155/jgaa.v28i1.2933}, abstractNote={<pre>We study the problem of distance-preserving graph compression for weighted paths and trees. <br>The problem entails a weighted graph $G = (V, E)$ with non-negative weights and a subset of edges $E^{\prime} \subset E$, which needs to be removed from G (with </pre> <pre>their endpoints merged as a supernode). The goal is to redistribute the weights of the deleted edges in a way that </pre> <pre>minimizes the error. The error is defined as the sum of the absolute differences of the shortest path lengths between different pairs of nodes before and after contracting $E^{\prime}$. </pre> <pre>Based on this error function, we propose optimal approaches for merging any subset of edges in a path and a single edge in a </pre> <pre>tree. Previous works on graph compression techniques aimed at preserving different graph properties (such as the chromatic </pre> <pre>number) or solely focused on identifying the optimal set of edges to contract. However, our focus in this paper is on </pre> <pre>achieving optimal edge contraction (when the contracted edges are provided as input), specifically for weighted trees and paths. </pre> <pre> </pre>}, number={1}, journal={Journal of Graph Algorithms and Applications}, author={Madani, Amirali and Maheshwari, Anil}, year={2024}, month={May}, pages={179–224} }