On the Broadcast Routing Problem in Computer Networks

Abstract

Given an undirected graph $G=(V,E)$, and a vertex $r\in V$, an $r$-acyclic orientation of $G$ is an orientation $OE$ of the edges of $G$ such that the digraph $OG=(V,OE)$ is acyclic and $r$ is the unique vertex with indegree equal to 0. For $w\in {\mathbb{R}}_{+}^E$, $k(G,w)$ is the value of the $w$-maximum packing of $r$-arborescences for all $r\in V$ and all $r$-acyclic orientations $OE$ of $G$. In this case, the Broadcast Routing (in Computers Networks) Problem (BRP) is to compute $k(G,w)$, by finding an optimal $r$ and an optimal $r$-acyclic orientation. BRP is a mathematical formulation of multipath broadcast routing in computer networks. In this paper, we provide a polynomial time algorithm to solve BRP in outerplanar graphs. Outerplanar graphs are encountered in many applications such as computational geometry, robotics, etc.

17 pages