Two-dimensional partial orders
Jeremy Spinrad · 1982
This thesis presents new algorithms dealing with a class of graphs called two dimensional partial orders. Algorithms are given which recognize two dimensional partial orders, and determine whether a pair of two dimensional partial orders are isomorphic. These algorithms have a time complexity of O(n('2)) time, while previous algorithms required O(n('3)) time. A new characterization of bipartite two dimensional partial orders is presented. A polynomial time algorithm is developed which solves the minimum dummy task problem for PERT networks if the input graph is a two dimensional partial order.