Geodesic
Distance-Preserving Graph Compression Techniques
Amirali Madani1 ; Anil Maheshwari1
1 School of Computer Science, Carleton University
Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 179-224.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We study the problem of distance-preserving graph compression for weighted paths and trees. 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 their endpoints merged as a supernode). The goal is to redistribute the weights of the deleted edges in a way that 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}$. Based on this error function, we propose optimal approaches for merging any subset of edges in a path and a single edge in a tree. Previous works on graph compression techniques aimed at preserving different graph properties (such as the chromatic number) or solely focused on identifying the optimal set of edges to contract. However, our focus in this paper is on achieving optimal edge contraction (when the contracted edges are provided as input), specifically for weighted trees and paths.
DOI : 10.7155/jgaa.v28i1.2933
Keywords: graph compression, graph algorithms, contraction

Amirali Madani 1 ; Anil Maheshwari 1

1 School of Computer Science, Carleton University 
@article{JGAA_2024_28_1_a7,
     author = {Amirali Madani and Anil Maheshwari},
     title = {Distance-Preserving {Graph} {Compression} {Techniques}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {179--224},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2024},
     doi = {10.7155/jgaa.v28i1.2933},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2933/}
}
TY  - JOUR
AU  - Amirali Madani
AU  - Anil Maheshwari
TI  - Distance-Preserving Graph Compression Techniques
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 179
EP  - 224
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2933/
DO  - 10.7155/jgaa.v28i1.2933
LA  - en
ID  - JGAA_2024_28_1_a7
ER  - 
%0 Journal Article
%A Amirali Madani
%A Anil Maheshwari
%T Distance-Preserving Graph Compression Techniques
%J Journal of Graph Algorithms and Applications
%D 2024
%P 179-224
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2933/
%R 10.7155/jgaa.v28i1.2933
%G en
%F JGAA_2024_28_1_a7
Amirali Madani; Anil Maheshwari. Distance-Preserving Graph Compression Techniques. Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 179-224. doi : 10.7155/jgaa.v28i1.2933. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2933/

Cité par Sources :