Distance-Preserving Graph Compression Techniques
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910608558915584 |
|---|---|
| author | Madani, Amirali Maheshwari, Anil |
| author_facet | Madani, Amirali Maheshwari, Anil |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_05829 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Distance-Preserving Graph Compression Techniques Madani, Amirali Maheshwari, Anil Data Structures and Algorithms Discrete Mathematics 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. |
| title | Distance-Preserving Graph Compression Techniques |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2307.05829 |