The Steiner Path Aggregation Problem
By: Da Qi Chen , Daniel Hathcock , D Ellis Hershkowitz and more
Potential Business Impact:
Makes computer paths less confusing for many users.
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.
Similar Papers
Steiner Forest: A Simplified Better-Than-2 Approximation
Data Structures and Algorithms
Finds shortest paths connecting many points.
Simultaneous Network Design with Restricted Link Usage
Data Structures and Algorithms
Finds paths that connect points using colors.
Fixed-parameter tractability and hardness for Steiner rooted and locally connected orientations
Discrete Mathematics
Makes computer networks more reliable for important connections.