  Random linear network coding (RLNC) is asymptotically throughput optimal in
the wireless broadcast of a block of packets from a sender to a set of
receivers, but suffers from heavy computational load and packet decoding delay.
To mitigate this problem while maintaining good throughput, we partition the
packet block into disjoint generations after broadcasting the packets uncoded
once and collecting one round of feedback about receivers' packet reception
state. We prove the NP-hardness of the optimal partitioning problem by using a
hypergraph coloring approach, and develop an efficient heuristic algorithm for
its solution. Simulations show that our algorithm outperforms existing
solutions.
