The Steiner Path Aggregation Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908572903800832 |
|---|---|
| author | Chen, Da Qi Hathcock, Daniel Hershkowitz, D Ellis Ravi, R. |
| author_facet | Chen, Da Qi Hathcock, Daniel Hershkowitz, D Ellis Ravi, R. |
| contents | In the Steiner Path Aggregation Problem, our goal is to aggregate paths in a directed network into a single arborescence without significantly disrupting the paths. In particular, we are given a directed multigraph with colored arcs, a root, and $k$ terminals, each of which has a monochromatic path to the root. Our goal is to find an arborescence in which every terminal has a path to the root, and its path does not switch colors too many times. We give an efficient algorithm that finds such a solution with at most $2\log_{4/3}k$ color switches. Up to constant factors this is the best possible universal bound, as there are graphs requiring at least $\log_2 k$ color switches. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_01392 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Steiner Path Aggregation Problem Chen, Da Qi Hathcock, Daniel Hershkowitz, D Ellis Ravi, R. Data Structures and Algorithms In the Steiner Path Aggregation Problem, our goal is to aggregate paths in a directed network into a single arborescence without significantly disrupting the paths. In particular, we are given a directed multigraph with colored arcs, a root, and $k$ terminals, each of which has a monochromatic path to the root. Our goal is to find an arborescence in which every terminal has a path to the root, and its path does not switch colors too many times. We give an efficient algorithm that finds such a solution with at most $2\log_{4/3}k$ color switches. Up to constant factors this is the best possible universal bound, as there are graphs requiring at least $\log_2 k$ color switches. |
| title | The Steiner Path Aggregation Problem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.01392 |