interval graphs

Near-optimal solutions of large-scale Single Machine Scheduling Problems

  • Pasquale Avella
  • Maurizio Boccia
  • Bernardo D'Auria
    • Categories Combinatorial Optimization, Production and Logistics Tags , ,

    We present a lagrangean heuristic based on the time-indexed formulation of the Single Machine Scheduling Problem with Release Dates. We observe that lagrangian relaxation of job constraints leads to a Weighted Stable Set problem on an Interval Graph. The problem is polynomially solvable by a dynamic programming algorithm. Computational experience is reported on instances up … Read more

    Solving Stability Problems on a Superclass of Interval Graphs

  • Carlo Mannino
  • Gianpaolo Oriolo
    • Categories Dynamic Programming, Graphs and Matroids, Telecommunications Tags , , ,

    We introduce a graph invariant, called thinness, and show that a maximum weighted stable set on a graph $G(V, E)$ with thinness $k$ may be found in $O(\frac{|V|}{k})^k$-time, if a certain representation is given. We show that a graph has thinness 1 if and only if it is an interval graph, while a graph with … Read more