PMC:1524773 / 19707-20327
Annnotations
{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/1524773","sourcedb":"PMC","sourceid":"1524773","source_url":"https://www.ncbi.nlm.nih.gov/pmc/1524773","text":"The y-structure suffices to guarantee the correctness of this algorithm, because it guarantees that all maximal cliques of active semi-squares are kept in Q. Since a semi-square X is only non-active if it has not yet begun or if the rest of its corresponding interval is not long enough for any new semi-square to overlap it enough, it cannot be an element of a clique when it is non-active. For its active time, the y-structure guarantees that all its maximal cliques are contained in Q. This algorithm is thus correct because the y-structure invariance is maintained in all steps. The pseudocode is sketched in Fig. 4.","tracks":[]}