We propose bipartite analogues of comparability and cocomparability graphs. Surprisingly, the two classes coincide. We call these bipartite graphs cocomparability bigraphs. We characterize cocomparability bigraphs in terms of vertex orderings, forbidden substructures, and orientations of their complements. In particular, we prove that cocomparability bigraphs are precisely those bipartite graphs that do not have edge-asteroids; this is analogous to Gallai's structural characterization of cocomparability graphs by the absence of (vertex-) asteroids. Our characterizations imply a robust polynomial-time recognition algorithm for the class of cocomparability bigraphs. Finally, we also discuss a natural relation of cocomparability bigraphs to interval containment bigraphs, resembling a well-known relation of cocomparability graphs to interval graphs.

We unify several seemingly different graph and digraph classes under one umbrella. These classes are all, broadly speaking, different generalizations of interval graphs, and include, in addition to interval graphs, adjusted interval digraphs, complements of threshold tolerance graphs (known as co-TT graphs), bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray bigraphs. (The last three classes coincide, but have been investigated in different contexts.) We show that all of the above classes are united by a common ordering characterization, the existence of a min ordering. However, because the presence or absence of reflexive relationships (loops) affects whether a graph or digraph has a min ordering, to obtain this result, we must define the graphs and digraphs to have those loops that are implied by their definitions. These have been largely ignored in previous work. We propose a common generalization of all these graph and digraph classes, namely signed-interval digraphs, characterized by the existence of a compact representation, a signed-interval model, which is a generalization of known representations of the graph classes. We show that the signed-interval digraphs are precisely those digraphs that are characterized by the existence of a min ordering when the loops implied by the model are considered part of the graph. We also offer an alternative geometric characterization of these digraphs. We show that co-TT graphs are the symmetric signed-interval digraphs, the adjusted interval digraphs are the reflexive signed-interval digraphs, and the interval graphs are the intersection of these two classes, namely, the reflexive and symmetric signed-interval digraphs. Similar results hold for bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray bigraphs.

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 unify several seemingly different graph and digraph classes under one umbrella. These classes are all broadly speaking different generalizations of interval graphs, and include, in addition to interval graphs, also adjusted interval digraphs, threshold graphs, complements of threshold tolerance graphs (known as `co-TT' graphs), bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray graphs. (The last three classes coincide, but have been investigated in different contexts.) This common view is made possible by introducing loops. We also show that all the above classes are united by a common ordering characterization, the existence of a min ordering. We propose a common generalization of all these graph and digraph classes, namely signed-interval digraphs, and show that they are precisely the digraphs that are characterized by the existence of a min ordering. We also offer an alternative geometric characterization of these digraphs. For most of the above example graph and digraph classes, we show that they are exactly those signed-interval digraphs that satisfy a suitable natural restriction on the digraph, like having all loops, or having a symmetric edge-set, or being bipartite. (For instance co-TT graphs are precisely those signed-interval digraphs that have each edge symmetric.) We also offer some discussion of recognition algorithms and characterizations, saving the details for future papers.

Tucker characterized the minimal forbidden submatrices of binary matrices that do not have the consecutive-ones property. We give a linear-time algorithm to find such a minimal one in any binary matrix that does not have the consecutive-ones property. Lekkerkerker and Boland characterized the minimal forbidden induced subgraphs for the class of interval graphs. We give a linear-time algorithm to find such a minimal one in any graph that is not an interval graph.

The interval graph for a set of intervals on a line consists of one vertex for each interval and an edge for each intersecting pair of intervals. A probe interval graph is a variant that is motivated by an application to genomics, where the intervals are partitioned into two sets: probes and nonprobes. The graph has an edge between two vertices if they intersect and at least one of them is a probe. We give a linear-time algorithm for determining whether a given graph and partition of vertices into probes and nonprobes is a probe interval graph. If it is, we give a layout of intervals that proves this. We can also determine whether the layout of the intervals is uniquely constrained within the same time bound. As part of the algorithm, we solve the consecutive-ones probe matrix problem in linear time, develop algorithms for operating on PQ trees, and give results that relate PQ trees for different submatrices of a consecutive-ones matrix.

Routing policies play an essential role in how traffic is forwarded across the Internet. The network would not be commercially viable without these routing policies, but policies also introduce inefficiencies and fail to fully exploit the underlying network topology. Our work assumes routes are selected according to some policy such as a valley-free routing policy. However, we apply policy at an aggregate traffic level and don't require individual packets to follow paths that match the policy. Our approach never reduces, and usually increases, the connectivity and capacity of the network, and does not infringe on the underlying motivations that led to the routing policy. By adopting this approach, we also provide polynomial algorithms for otherwise NP-hard problems, including finding maximum policy-observing routing capacity between two sets of ASes, minimizing cuts separating all policy-observing paths between two sets of ASes, and maximizing sets of edge-or vertex-disjoint policy-observing paths.

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.

A graph G is a circular-arc graph if it is the intersection graph of a set of arcs on a circle. That is, there is one arc for each vertex of G, and two vertices are adjacent in G if the corresponding arcs intersect. We give a linear time bound for recognizing this class of graphs. When G is a member of the class, the algorithm gives a certificate in the form of a set of arcs that realize it.

Given a finite set of texts S = { w 1, … , w k } over some fixed finite alphabet Σ, a complete inverted file for S is an abstract data type that provides the functions find ( w ), which returns the longest prefix of w that occurs (as a subword of a word) in S ; freq ( w ), which returns the number of times w occurs in S ; and locations ( w ), which returns the set of positions where w occurs in S . A data structure that implements a complete inverted file for S that occupies linear space and can be built in linear time, using the uniform-cost RAM model, is given. Using this data structure, the time for each of the above query functions is optimal. To accomplish this, techniques from the theory of finite automata and the work on suffix trees are used to build a deterministic finite automaton that recognizes the set of all subwords of the set S . This automaton is then annotated with additional information and compacted to facilitate the desired query functions. The result is a data structure that is smaller and more flexible than the suffix tree.

Given a finite set of texts S = {ω1, ..., ωk} over some fixed finite alphabet Σ, a complete inverted file for S is an abstract data type that provides the functions find(ω), which returns the longest prefix of ω which occurs in S; freq(ω), which returns the number of times ω occurs in S; and locations(ω) which returns the set of positions at which ω occurs. We give a data structure to implement a complete inverted file for S which occupies linear space and can be built in linear time, using the uniform cost RAM model. Using this data structure, the time for each of the above query functions is optimal. To accomplish this, we use techniques from the theory of finite automata to build a deterministic finite automaton which recognizes the set of all sub words of the set S. This automaton is then annotated with additional information and compacted to facilitate the desired query functions.