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

Peter, Markus and Wambach, Georg (2000) N-extendible posets, and how to minimize total weighted completion time.
Published in: Discrete Applied Mathematics Vol. 99 (1-3). pp. 157-167.

Abstract

P_4-extendible graphs have been introduced by B. Jamison and S. Olariu [Stud. Appl. Math. 81 (1989), no. 1, 79--87, Discrete Appl. Math. 34 (1991), no. 1-3, 151--164, Discrete Appl. Math. 35 (1992), no. 2, 115--129] as one of several tractable generalizations of P_4-free graphs (cographs). A P_4 has a path of length three. A graph G is P_4-extendible, 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_4-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 mini mizing total weighted completion time for N-extendible posets in O(n log n) time, thereby improving an O(n^2) result of Schulz for N-sparse posets.


Actions:
Full text not available from this repository.
Export as:
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 0 (Web of Science)
Uncontrolled Keywords: N-extendible posets partially ordered sets series-parallel posets single machine scheduling structural graph theory total weighted completion time
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms

  • 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:
    Deposit Information:
    ZAIK Number: zaik2000-401
    Depositing User: Archive Admin
    Date Deposited: 02 Apr 2001 00:00
    Last Modified: 16 Aug 2011 11:30
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/401