N-extendible posets, and how to minimize total weighted completion time

N-extendible posets, and how to minimize total weighted completion time

0.00 Avg rating0 Votes
Article ID: iaor20012903
Country: Netherlands
Volume: 99
Issue: 1/3
Start Page Number: 157
End Page Number: 167
Publication Date: Feb 2000
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: scheduling
Abstract:

P4-extendible graphs have been introduced by Jamison and Olariu as one of several tractable generalizations of P4-free graphs (cographs). A P4 is a path of length three. A graph G is P4-extendible, if every vertex set W of G inducing a P4 has a proper extension, i.e., there is at most one vertex x6W which belongs to an induced P4 that shares vertices with W. In this paper we first examine P4-extendible comparability graphs and exhibit the class of N-extendible posets, a true superset of N-sparse posets. In particular, every poset of size at most five is N-extendible. Second, we solve the single machine scheduling problem of minimizing total weighted completion time for N-extendible posets in O(nlogn) time, thereby improving an O(n2) result of Schulz for N-sparse posets.

Reviews

Required fields are marked *. Your email address will not be published.