ECE 526 (Fall 2015)
Homework 5
Due Friday, November 20, 2015 by 3 p.m.
1. This question relates to the paper "Multiparty Equality Function
Computation in Networks with Point-to-Point Links".
Consider the bipartite graph with nodes 1, 2, 3 in the left part,
and nodes 4, 5, 6 in the right part. The graph contains the following
edges: (1,4), (2,5), (3,6), (1,5), (2,6).
(a) Draw this bipartite graph, and label the edges with their colors that
achieve strong edge coloring.
(b) Determine an equality computation algorithm for 3 nodes using the
above edge coloring (i.e., show functions f_AB, f_BC and f_CA as
in the example in the paper).
2. Determine "reversal distance" for each node in the graph at the bottom in
Figure 11 of the notes at
http://web.cs.iastate.edu/~chaudhur/cs611/Sp07/notes/lec18.pdf