A C++ implementation of a O(n log n) algorithm computing a maximal stable set of an interval graph

Sid Touati (1)

1 KAIROS - Logical Time for Formal Embedded System Design

This software implements the algorithm published in U.I. Gupta, D.T. Lee, J.-T Leung. An optimal solution for the channel-assignment problem; IEEE Transactions on Computers C-28(1979), 807-810. Citation of the authors: "Given a set of intervals (pairs of real numbers), we look at the problem of finding a minimal partition of this set such that no element of the partition contains two overlapping intervals. We exhibit a O (n log n) algorithm which is optimal. The problem has applications in LSI layout design and job scheduling". And I add that this algorithm solves also some problems in register allocation inside compilers.

Domaines: Informatique; Algorithme et structure de données [cs.DS]

Sid Touati. A C++ implementation of a O(n log n) algorithm computing a maximal stable set of an interval graph. 2021, ⟨swh:1:dir:95986a410683154bc0c9d55a2331839b74993c3d;origin=https://hal.archives-ouvertes.fr/hal-03445937;visit=swh:1:snp:63bdc74d56c678b7fa433ed87f0a4654050d02a3;anchor=swh:1:rel:9906213d31fdd2ce4d04d281a9b47747038836f1;path=/⟩. ⟨hal-03445937⟩