A note on transitive orientations with maximum sets of sources and sinks (Q1613367): Difference between revisions

Let \(\overrightarrow{G}\) be a transitive orientation of a comparability graph \(G\). A vertex in \(G\) is called a source (respectively a sink) if its indegree (respectively outdegree) in \(\overrightarrow{G}\) is equal to zero. A pair of subsets \(S,T\) of \(V(G)\) is a source-sink pair of \(G\) if the vertices of \(S\) and \(T\) are sources and sinks, respectively, of some transitive orientation \(\overrightarrow{G}\) of \(G\). The authors prove recurrence equations for computing the maximum cardinality of a source-sink pair, for a given comparability graph. Moreover, they describe a linear-time algorithm that finds a transitive orientation of \(G\), for which the source-sink pair achieves the maximum cardinality.