Merging incomparable linearizations

Implementation
,
29

Merging individually post-processed linearizations (thus, ones with connected chunks) may result in a linearization whose chunks are disconnected. This means post-processing the merged result can still be useful.

For example:

graph BT
   T0["B: 5"];
   T1["C: 10"] --> T4;
   T2["D: 2"] --> T4;
   T3["E: 2"] --> T0;
   T3 --> T4;
   T4["A: 1"];
  • L1 = [B,A,E,C,D] (chunked as [B,AEC,D])
  • L2 = [B,A,D,C,E] (chunked as [B,ADC,E])
  • Prefix-intersection merge yields [B,A,C,D,E] (chunked as [BAC,D,E])
  • Post-processing the merge gives [A,C,B,D,E] (chunked as [AC,B,D,E])