Bandwidth Lower Bound Formula

Problem

Compute a simple lower bound on the bandwidth of a connected undirected graph.

Any hub needs room for its neighbors within its own position plus or minus the bandwidth, and a layout has to stretch across the diameter, so the bound is max(ceil(max_degree / 2), ceil((n - 1) / diameter)). edges is a list of [u, v] pairs of a connected graph. Return 0 when n is at most 1, otherwise the integer bound.

Hint

Both the busiest vertex and the farthest pair impose independent constraints on the layout.

Test cases

case 1

in: [5,[[0,1],[1,2],[2,3],[3,4]]]

expected: 1

case 2

in: [5,[[0,1],[1,2],[2,3],[3,4],[4,0]]]

expected: 2

case 3

in: [5,[[0,1],[0,2],[0,3],[0,4]]]

expected: 2

case 4

in: [3,[[0,1],[1,2],[2,0]]]

expected: 2

case 5

in: [1,[]]

expected: 0

Starter codePython

def bandwidth_lower_bound(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor