Let us recall that the objective of the BANDWIDTHMINIMIZATIONproblem is to find an optimal layout of a graphG= (V,E), i.e. a bijection f:V→ {1, . . . ,n}such that the width of the layout f,
max
{u,v}∈E|f(u)−f(v)|
is minimized. The layout f can be seen as an embedding of the vertices ofGinto slots numbered from 1 ton. Thus the bandwidth of a graph is at mostB, if there is an embedding in{1,2, . . . ,n}such that the stretch|f(u)−f(v)|of each edge{u,v} ofGis at mostB. Thus sometimes we will refer to integersi∈ {1,2, . . . ,n}asslots.
Obviously, the bandwidth of any graphGonnvertices is at mostn−1. In this section, we discuss an algorithm that for any B, 1≤B≤n−1, decides in time O∗(6n)whether the bandwidth ofGis at mostB. Then running this algorithm for all values of B, the BANDWIDTHMINIMIZATIONproblem can be solved in time O∗(6n).
LetGbe a graph onnvertices andB, 1≤B≤n−1, be an integer. Let us assume thatnis divisible byB+1 (this assumption does not change the result but makes the description slightly easier). IfGis not connected, then its bandwidth is equal to the maximum bandwidth of its connected components. Thus we may assume thatGis
171
a connected graph. We partition the set of slots{1,2, . . . ,n}into segments {1, . . . ,B+1},{B+2, . . . ,2B+2}, . . . ,{n−B, . . . ,n}. With every sloti∈ {1,2, . . . ,n}we associate two values
x(i) = ((i−1) mod(B+1)) +1 and
y(i) =d i B+1e.
In other words,x(i)is the position ofiin its segment, andy(i)is the number of the segment to whichibelongs.
For example, forB=2 andn=9, we have the following partition into 3 segments 1 2 3|4 5 6|7 8 9.
In this case,x(1) =1,y(1) =1,x(6) =3,y(5) =2, etc.
We say that the permutation
π1π2 ···πn
of slots is thelexicographicalordering of slots if fori≤j, (x(πi),y(πi))(x(πj),y(πj)).
For our example with set of slots{1,2, . . . ,9}andB=2, the lexicographical order-ing of slots is
1 4 7 2 5 8 3 6 9.
Now we are ready to describe the algorithm. The algorithm proceeds in two phases. In the first phase it creates O∗(3n)subproblems and in the second phase it solves each of the subproblems in timeO∗(2n).
The goal of the first phase is to break a possible layout intoO∗(3n)subproblems, such that for each of the subproblems the approximate position of every vertex is known. More precisely: The first phase starts by computing all possible assignments of the vertices of the graph to the segments. The crucial observation is that for ev-ery layout of width at mostB, every pair of adjacent vertices is either assigned to the same segment or to adjacent ones. Indeed, if two adjacent vertices are placed into different non adjacent segments, then the stretch of the edge connecting these vertices is at leastB+2. Thus if a vertex of a graph is assigned to a segment with numberi, then its neighbors can only be placed in one of the segments with num-bersi−1,i, ori+1. The number of such assignments satisfying the condition that adjacent vertices ofGare assigned to the same or to adjacent segments is at most
n
B+1·3n=O∗(3n). This can be seen as follows. We select (arbitrarily) a vertexvinG and we consider alln/(B+1)possibilities of assigningvto different segments. Then we iteratively select an unassigned vertexuwhich has a neighborwthat already has
11.1 Bandwidth 173 been assigned to some segment. If no such vertexuexists then all vertices have been assigned to segments asGis connected. Sinceuandware adjacent, there are only three possible segments to whichucan be assigned. For each such an assignment we also perform a check leaving only those assignmentsσassigning exactlyB+1 vertices to each of the segments. We also remove assignments containing edges with endpoints in non-adjacent segments. Assignments generated in the first phase will be calledsegment assignments.
To describe the second phase of the algorithm we need the following definition.
For a fixed segment assignmentσ:V → {1,2, . . . ,n/(B+1)}, we say that a subset A⊆V islexicographically embeddiblein{1,2, . . . ,n}if
a)for each edge{u,v} ∈E, conditionsu∈Aandv6∈Ayield thatσ(v)≤σ(u). In other words,vcan be assigned either to the same segment asu, or to the adjacent segment preceding the slot containingu;
b)there is a mappingγ :A→ {1,2, . . . ,n}agreeing withσ, which means that for every vertexv∈A,γ(v)belongs to the segment containingσ(v), and such that the slots occupied by γ(v),v∈A, are the first|A| slots in the lexicographical ordering of slots.
In Fig. 11.1, we give examples of lexicographically embeddible sets. For graphGin Fig. 11.1 andB=2, the mappingσ(a) =σ(b) =σ(f) =1,σ(c) =σ(g) =σ(h) = 2, andσ(d) =σ(e) =σ(i) =3, is the segment assignment. The layoutγagrees with σ and its width is at mostB. The sets /0⊂ {a} ⊂ {a,g} ⊂ {a,d,g} ⊂ {a,d,f,g} ⊂
{a,c,d,f,g} ⊂ {a,c,d,f,g,i} ⊂ {a,b,c,d,f,g,i} ⊂ {a,b,c,d,f,g,h,i} ⊂ {a,b,c,d,e,f,g,h,i} are lexicographically embeddible. The setP={a,c,d,g}is not lexicographically
embeddible because the first four slots in the lexicographical ordering are 1,4,7,2 but every mapping agreeing withσ must use two slots from the second segment {4,5,6}forcandg. Thus there is no mapping satisfying conditionb)of the defini-tion of lexicographically embeddible sets. The setQ={a,b,g,h}is also not lexico-graphically embeddible becausec6∈Qbutσ(c)>σ(b)and thusσ does not satisfy conditiona).
Lemma 11.1.Letσbe a segment assignment. Then the following are equivalent
• There is layoutγ:V → {1,2, . . . ,n}agreeing withσand of width at most B
• There is sequence/0=A0⊂A1⊂ ··· ⊂An=V such that for each i∈ {1,2, . . . ,n},
|Ai|=i, and Aiis lexicographically embeddible in{1,2, . . . ,n}.
Proof. Letγbe a layout of width at mostBagreeing withσ. We define the setAi, 1≤i≤n, as the set of vertices occupying the firsti slots in the lexicographical ordering of slots. Letu∈Ai,v6∈Ai, be a pair of adjacent vertices, and letkbe the slot occupied byuand`be the slot occupied byvin the layoutγ. Layoutγagrees withσ, and thusy(k) =σ(u),y(`) =σ(v). The vertices ofAi occupy the firsti slots in the lexicographical ordering, and thus in every segment with number at least σ(u), the firsty(k)−1 slots are occupied by vertices ofAi. Therefore, there are at leastBslots betweenkand the first unoccupied slot of the segmentσ(u) +1. Since
174 11 Miscellaneous
as u, or to the adjacent slot preceding the slot containing u;
• There is a mapping γ : A → { 1, 2, . . . , n } “agreeing” with σ, which means that for every vertex v ∈ A, γ (v) belongs to the segment con-taining σ(v), such that the slots occupied by γ(v ), v ∈ A, are the first
| A | slots in the lexicographical ordering of slots.
To give an example here.
184 CHAPTER 11. MISCELLANEOUS (DK + FF)
With every slot i ∈ { 1, 2, . . . , n } we associate two values x(i) = (i − 1) mod (B + 1) + 1 and
y(i) = # i B + 1 $ .
In other words, x(i) is the position of i in its segment, and y(i) is the number of the segment i belongs to.
For example, for B = 2 and n = 9, we have the following partition into 3 segments
1 2 3 | 4 5 6 | 7 8 9.
In this case, x(1) = 1, y(1) = 1, x(6) = 3, y(5) = 2, etc.
We say that permutation
π
1π
2· · · π
nof slots is the lexicographical ordering of slots if for i ≤ j, (x(π
i), y(π
i)) & (x(π
j), y(π
j)).
For our example with set of slots { 1, 2, . . . , 9 } and B = 2, the lexicographical ordering is
1 4 7 2 5 8 3 6 9.
Now we are ready to describe the algorithm. We start by computing all possible assignments of the vertices of the graph to segments. In every assignment of the vertices of the graphs to slots { 1, 2, . . . , n } with bandwidth at most B, every pair of adjacent vertices is either assigned to the same segment or to adjacent ones. Indeed, if two adjacent vertices are placed into different non adjacent segments, then the stretch of the edge connecting these vertices is at least B + 1. Thus if a vertex of a graph is assigned to a segment with number i, then its neighbors can be placed only in one of the segments with numbers i − 1, i, or i + 1. The number of such assignments is at most n/(B + 1)3
n= O
∗(3
n). This can be seen as follows. If we select some spanning rooted tree of G, and try to assign its vertices according breadth-first search starting from the root. There are n/(B + 1) possible assignments of the root to segments but for every other vertex v of the tree there are at most 3 segments to which v can be assigned.
For each such an assignment we also perform a “sanity” check leaving only those assignments σ assigning exactly B + 1 vertices to each of the segments.
We also remove assignments containing edges with endpoints in non-adjacent segments. We will call such assignments by segment assignments.
Let us fix one of such segment assignments σ : V → { 1, 2, . . . , n/(B + 1) } . We say that a subset A ⊆ V is lexicographically embeddible in { 1, 2, . . . , n } if
Fig. 11.1 A Graph, its segment assignment and the corresponding embedding
|k−`| ≤B, we conclude thatvcan be assigned only to segmentσ(u)orσ(u)−1, Now we want to use Lemma 11.1 to compute a layout γ of width at most B which agrees with segment assignmentσ. For every vertex subsetA⊆V, we de-cide whetherA is lexicographically embeddible in{1,2, . . . ,n}by making use of dynamic programming.
Every setA={v}of cardinality one is lexicographically embeddible in{1,2, . . . ,n} if and only ifσassignsvto the first segment and all neighbors ofvare also assigned to the first segment. This check can clearly be performed in polynomial time. Let Abe a set of cardinality at least two that is lexicographically embeddible and letγ be the corresponding mapping. Then for the vertexv∈Aassigned byγto the slot with maximum (in the lexicographical ordering of occupied slots) position, the set A\ {v}is also lexicographically embeddible. Hence a setAof cardinality at least
11.2 Branch & Recharge 175