Maximal Stable Set in an Interval Graph

Dear all,
We are pleased to announce the release of a C++ implementation of the following algorithm:
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.


The implementation is here (under GPL licence)
http://www.prism.uvsq.fr/~touati/sw/MSSIG

Regards
S.T.


ps: we are open for any remark
.

Relevant Pages

  • Re: Measuring the effectiveness of a GA implementation?
    ... GA - or of any optimisation algorithm, ... comparison with an optimal solution is ... mean fitness) plus, preferably, some measure of the ... about evaluating effectiveness of optimisation algorithms (I'm loath to ...
    (comp.ai.genetic)
  • Re: Needleman-Wunsch - producing more than the optimal solution -- please help
    ... What I want is the optimal solution, second optimal solution, third ... an issue I see is that it's not clear to me that the algorithm actually compares solutions to find the "optimal" one so much as it detects the best alignment of two inputs based on a pre-computed weighting matrix. ... But the moment you allow for the choice of something other than the maximal choice, you have to deal with every permutation possible, and evaluate those permutations in some way. ... Not only would you, after redoing the choice, have to recompute the rest of the "F" matrix that depended on that choice, there's no guarantee that when you're done, the score in the lower-right corner that results from that replacement would indeed be the next-lowest score possible in the matrix. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: C to Forth converter?
    ... how to find the minimum number of instructions for solving a stack juggling ... But is this the shortest solution? ... algorithm to converge towards. ... optimal solution because the only way to find that it is optimal is to ...
    (comp.lang.forth)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... R U really sure about if a TSP has exactly one optimal tour, ... But the most important thing is this algorithm discovering this "one and ... to TSP with only one optimal solution is possible, so if I had algorith you ... This would be this small numbers added to each weight ...
    (comp.theory)