7 Literal Selection in Switching Lattice Design
167
3. In case of successive ties select a literal arbitrarily.
The algorithm makes use of two arrays occ, f req of size , and of an array Lit of
size m. The arrays occ and f req keep track of the occurrences of the literals in the
lattice and of the number of times each literal has been chosen, respectively; Lit
stores the literal assigned to each lattice switch.
HMDA (input S = {L i | 1 ≤ i ≤ m}, output Lit)
sort the sets in S in non decreasing order of cardinality, using a linear time algorithm;
define two arrays occ, f req of size , and set to 0 their elements;
for all R ∈ S do
for all v ∈ R do
occ[v] ← occ[v] + 1; /* count the occurrences of each literal */
for all R ∈ S do
lit o ← the first literal v ∈ R with the lowest occ value;
lit f ← the first literal v ∈ R with the lowest f req value;
if (f req[lit o ] <
m
) Lit[R.pos] ← lit o ;
else Lit[R.pos] ← lit f ;
f req[Lit[R.pos]] ← f req[Lit[R.pos]] + 1; /* update the frequency of Lit[R.pos] */
for all v ∈ R do
occ[v] ← occ[v] − 1; /* update the occurrences of the literals in R */
7.5 The MPA Problem
The MPA problem has already been studied in [29] for general graphs and for some
variations, showing that it is NP-hard on a lattice. Moreover, in [21] it has been
shown how the problem may be simplified reducing the number of literals contained
in the subsets associated with the vertices, and a very simple heuristic has been
proposed. Here we develop two more skilled heuristics for the problem and analyze
their performances on a set of known benchmarks.
First of all, from [21] we recall the rule used to simplify the input instance of the
problem.
Rule 1 Let v j be a vertex, v 1 , v 2 , v 3 , v 4 be the four vertices adjacent to v j (if any),
and L j , L 1 , L 2 , L 3 , L 4 be the relative subsets of literals. Apply in sequence the
following steps:
Step 1. Let |L j | > 1. If a literal x ∈ L j does not appear in any of the sets L i , for
1 ≤ i ≤ 4, cancel x from L j and repeat the step until at least one element
remains in L j .
Step 2. Let |L j | > 1, and let L k ⊂ L j with k ∈ {1, 2, 3, 4}. If a literal x ∈ L j
appears in exactly one set L h with h ∈ {1, 2, 3, 4} and h = k, then cancel
x from L j and repeat the step until at least the literals of L k remain in L j .
Proposition 7.3 (From [21]) The application of Rule 1 does not prevent finding an
MPA.
167
3. In case of successive ties select a literal arbitrarily.
The algorithm makes use of two arrays occ, f req of size , and of an array Lit of
size m. The arrays occ and f req keep track of the occurrences of the literals in the
lattice and of the number of times each literal has been chosen, respectively; Lit
stores the literal assigned to each lattice switch.
HMDA (input S = {L i | 1 ≤ i ≤ m}, output Lit)
sort the sets in S in non decreasing order of cardinality, using a linear time algorithm;
define two arrays occ, f req of size , and set to 0 their elements;
for all R ∈ S do
for all v ∈ R do
occ[v] ← occ[v] + 1; /* count the occurrences of each literal */
for all R ∈ S do
lit o ← the first literal v ∈ R with the lowest occ value;
lit f ← the first literal v ∈ R with the lowest f req value;
if (f req[lit o ] <
m
) Lit[R.pos] ← lit o ;
else Lit[R.pos] ← lit f ;
f req[Lit[R.pos]] ← f req[Lit[R.pos]] + 1; /* update the frequency of Lit[R.pos] */
for all v ∈ R do
occ[v] ← occ[v] − 1; /* update the occurrences of the literals in R */
7.5 The MPA Problem
The MPA problem has already been studied in [29] for general graphs and for some
variations, showing that it is NP-hard on a lattice. Moreover, in [21] it has been
shown how the problem may be simplified reducing the number of literals contained
in the subsets associated with the vertices, and a very simple heuristic has been
proposed. Here we develop two more skilled heuristics for the problem and analyze
their performances on a set of known benchmarks.
First of all, from [21] we recall the rule used to simplify the input instance of the
problem.
Rule 1 Let v j be a vertex, v 1 , v 2 , v 3 , v 4 be the four vertices adjacent to v j (if any),
and L j , L 1 , L 2 , L 3 , L 4 be the relative subsets of literals. Apply in sequence the
following steps:
Step 1. Let |L j | > 1. If a literal x ∈ L j does not appear in any of the sets L i , for
1 ≤ i ≤ 4, cancel x from L j and repeat the step until at least one element
remains in L j .
Step 2. Let |L j | > 1, and let L k ⊂ L j with k ∈ {1, 2, 3, 4}. If a literal x ∈ L j
appears in exactly one set L h with h ∈ {1, 2, 3, 4} and h = k, then cancel
x from L j and repeat the step until at least the literals of L k remain in L j .
Proposition 7.3 (From [21]) The application of Rule 1 does not prevent finding an
MPA.