A semiorder is a model of preference relations where each element $x$ is associated with a utility value $α(x)$, and there is a threshold $t$ such that $y$ is preferred to $x$ iff $α(y) > α(x)+t$. These are motivated by the notion that there is some uncertainty in the utility values we assign an object or that a subject may be unable to distinguish a preference between objects whose values are close. However, they fail to model the well-known phenomenon that preferences are not always transitive. Also, if we are uncertain of the utility values, it is not logical that preference is determined absolutely by a comparison of them with an exact threshold. We propose a new model in which there are two thresholds, $t_1$ and $t_2$; if the difference $α(y) - α(x)$ less than $t_1$, then $y$ is not preferred to $x$; if the difference is greater than $t_2$ then $y$ is preferred to $x$; if it is between $t_1$ and $t_2$, then then $y$ may or may not be preferred to $x$. We call such a relation a double-threshold semiorder, and the corresponding directed graph $G = (V,E)$ a double threshold digraph. Every directed acyclic graph is a double threshold graph; bounds on $t_2/t_1$ give a nested hierarchy of subclasses of the directed acyclic graphs. In this paper we characterize the subclasses in terms of forbidden subgraphs, and give algorithms for finding an assignment of of utility values that explains the relation in terms of a given $(t_1,t_2)$ or else produces a forbidden subgraph, and finding the minimum value $λ$ of $t_2/t_1$ that is satisfiable for a given directed acyclic graph. We show that $λ$ gives a measure of the complexity of a directed acyclic graph with respect to several optimization problems that are NP-hard on arbitrary directed acyclic graphs.

We use a new structural theorem on the presence of two-pairs in weakly chordal graphs to develop improved algorithms. For the recognition problem, we reduce the time complexity from O( mn 2 ) to O( m 2 ) and the space complexity from O( n 3 ) to O( m + n ), and also produce a hole or antihole if the input graph is not weakly chordal. For the optimization problems, the complexity of the clique and coloring problems is reduced from O( mn 2 ) to O( n 3 ) and the complexity of the independent set and clique cover problems is improved from O( n 4 ) to O( mn ). The space complexity of our optimization algorithms is O( m + n ).

A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves that the answer has not been compromised by a bug in the implementation. We give linear-time certifying algorithms for recognition of interval graphs and permutation graphs, and for a few other related problems. Previous algorithms fail to provide supporting evidence when they claim that the input graph is not a member of the class. We show that our certificates of nonmembership can be authenticated in O(|V|) time.

This paper uses periodic matrix multiplication to improve the time complexities for a number of graph problems. The time for finding an asteroidal triple is reduced from O(nm) to O(n 2.82 ), and the time for finding a star cutset, a two-pair, and a dominating pair is reduced from O(nm) to O(n 2.79 ). It is also shown that each of these problems is at least as hard as one of three basic graph problems for which the best known algorithms run in times O(nm) and O(n alpha ). We note that the fast matrix multiplication algorithms do not seem to be practical because of the enormous constants needed to achieve the asymptotic time bounds. These results are important theoretically for breaking the n 3 barrier rather than giving efficient algorithms for a user.

The class of weakly triangulated comparability graphs and their complements are generalizations of interval graphs and chordal comparability graphs. We show that problems on these classes of graphs can be solved efficiently by transforming them into problems on chordal bipartite graphs. We show that recognition and independent set on weakly triangulated comparability graphs can be solved in O(n 2 ) time in this manner, and that the number of weakly triangulated comparability graphs is $2^{\Theta ( n {{\log}^2} n)}$.\ We also give algorithms to compute transitive closure and transitive reduction in O(n 2 loglogn) time if the underlying undirected graph of the transitive closure is a weakly triangulated comparability graph.

This paper studies a new method for representing $\Gamma $-free matrices, which occur in characterizations of chordal bipartite and strongly chordal graphs. We show that the number of $\Gamma $-free matrices with n rows and columns (and thus the number of chordal bipartite and strongly chordal graphs with n vertices) is proportional to $2^{\Theta ( n \log^2 n )} $, and give an asymptotically space optimal method for storing these matrices.

Modular decomposition is a form of graph decomposition that has been discovered independently by researchers in graph theory, game theory, network theory, and other areas. This paper reduces the time needed to find the modular decomposition of a graph from Ω( n 3 ) to Ο( n 2 ). Together with a new algorithm for transitive orientation given in [21], this leads to fast new algorithms for a number of problems in graph recognition and isomorphism, including recognition of comparability graphs and permutation graphs. The new algorithm works by inserting each vertex successively into the decomposition tree, using Ο( n ) time to insert each vertex.

This paper develops an $O(n^2 )$ algorithm for testing whether a graph is decomposable with respect to the split decomposition. The fastest previous algorithm required $w (n^3 )$ time for this problem. This leads to an $O(n^2 )$ expected time algorithm for computing the split decomposition of a graph.

Abstract The minimum dummy task problem for PERT networks is NP‐complete on arbitrary graphs. This paper presents a very simple heuristic algorithm for the minimum dummy task problem and proves that this algorithm finds an optimal PERT network for various classes of graphs, including interval orders, two‐dimensional partial orders, and seriesparallel partial orders.

This paper presents a technique for orienting a comparability graph transitively in $O(n^2 )$ time. The best previous algorithm for this problem required $\Omega (n^3 )$ time. When combined with a result in [SP], we can recognize permutation graphs in $O(n^2 )$ time, and determine in the same time complexity whether two permutation graphs are isomorphic. The orientation algorithm can also be used to reduce the problem of recognizing comparability graphs to that of recognizing transitive graphs. This gives an upper bound of $O(n^{2.49 + } )$ for comparability graph recognition, while the fastest previous algorithms required $\Omega (n^3 )$ time.

This paper presents an algorithm for the transitive graph orientation problem which runs in 0(n2) time. The best previous algorithms for this problem required 0(n3) time. Transitive orientation is the slowest part of several graph recognition problems, so the new algorithm immediately improves the complexity of algorithms for recognizing comparability graphs, permutation graphs, and circular permutation graphs.