A note on transitive orientations with maximum sets of sources and sinks (Q1613367)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on transitive orientations with maximum sets of sources and sinks |
scientific article |
Statements
A note on transitive orientations with maximum sets of sources and sinks (English)
0 references
29 August 2002
0 references
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.
0 references
comparability graph
0 references
transisive orientation
0 references
source
0 references
sink
0 references
algorithms
0 references