Skip to main content
gave reference
Source Link
Peter Shor
  • 4.5k
  • 1
  • 25
  • 35

The graph of overlapping jobs is an interval graph. Interval graphs are perfect graphs. So what you are trying to do is find a maximum weight independent set (i.e., no two overlap) in a perfect graph. This can be solved in polynomial time. The algorithm is given in "Polynomial Algorithms for Perfect Graphs", by M. Grötschel, L. Lovász, and A. Schrijver.

I don't have my reference books handy, so you mightThere are a number of special cases of perfect graphs for which people have to wait until I they're handydiscovered simpler and more efficient algorithms for me to you to the papersthis task. I also don't know whether there are any algorithms for finding the maximum weight independent set in an interval graph that are simpler than using the algorithm for perfect graphs fall into one of these special cases.

The graph of overlapping jobs is an interval graph. Interval graphs are perfect graphs. So what you are trying to do is find a maximum weight independent set (i.e., no two overlap) in a perfect graph. This can be solved in polynomial time.

I don't have my reference books handy, so you might have to wait until I they're handy for me to you to the papers. I also don't know whether there are any algorithms for finding the maximum weight independent set in an interval graph that are simpler than using the algorithm for perfect graphs.

The graph of overlapping jobs is an interval graph. Interval graphs are perfect graphs. So what you are trying to do is find a maximum weight independent set (i.e., no two overlap) in a perfect graph. This can be solved in polynomial time. The algorithm is given in "Polynomial Algorithms for Perfect Graphs", by M. Grötschel, L. Lovász, and A. Schrijver.

There are a number of special cases of perfect graphs for which people have discovered simpler and more efficient algorithms for this task. I don't know whether interval graphs fall into one of these special cases.

Source Link
Peter Shor
  • 4.5k
  • 1
  • 25
  • 35

The graph of overlapping jobs is an interval graph. Interval graphs are perfect graphs. So what you are trying to do is find a maximum weight independent set (i.e., no two overlap) in a perfect graph. This can be solved in polynomial time.

I don't have my reference books handy, so you might have to wait until I they're handy for me to you to the papers. I also don't know whether there are any algorithms for finding the maximum weight independent set in an interval graph that are simpler than using the algorithm for perfect graphs.