Nextendible posets, and how to minimize total weighted completion time
Peter, Markus and Wambach, Georg
(2000)
Nextendible posets, and how to minimize total weighted completion time.
Published in:
Discrete Applied Mathematics Vol. 99 (13).
pp. 157167.
Abstract
P_4extendible graphs have been introduced by B. Jamison and S. Olariu [Stud. Appl. Math. 81 (1989), no. 1, 7987, Discrete Appl. Math. 34 (1991), no. 13, 151164, Discrete Appl. Math. 35 (1992), no. 2, 115129] as one of several tractable generalizations of P_4free graphs (cographs). A P_4 has a path of length three. A graph G is P_4extendible, if every vertex set W of G inducing a P_4 has a proper extension, i.e., there is at most one vertex x not in W which belongs to an induced P_4 that shares vertices with W. In this paper we first examine P_4extendible comparability graphs and exhibit the class of Nextendible posets, a true superset of Nsparse posets. In particular, every poset of size at most five is Nextendible. Second, we solve the single machine scheduling problem of mini mizing total weighted completion time for Nextendible posets in O(n log n) time, thereby improving an O(n^2) result of Schulz for Nsparse posets.
Item Type:  Article 

Citations:  0 (Web of Science) 
Uncontrolled Keywords:  Nextendible posets partially ordered sets seriesparallel posets single machine scheduling structural graph theory total weighted completion time 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Schrader 
Additional Information:  Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1997) 
Related URLs: 
ZAIK Number:  zaik2000401 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  16 Aug 2011 11:30 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/401 