The online graph bandwidth problem

The online graph bandwidth problem is defined, and we present an online algorithm that always outputs a (((2k − 1)n + 1)/2k)-bandwidth function for any n-vertex graph with bandwidth k. A lower bound of k/(k + 1))n − 2 is shown for any such algorithm. Two other protocols for online problems are given, and we prove lower bounds for the bandwidth problem under both of these alternative protocols.

Authors

• Raymond Board

Keywords

No keywords are indexed for this paper.