A note on transitive orientations with maximum sets of sources and sinks (Q1613367): Difference between revisions
From MaRDI portal
Removed claims |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Celina M. Herrera de Figueiredo / rank | |||
Normal rank | |||
Property / author | |||
Property / author: John G. Gimbel / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Célia Picinin de Mello / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Jayme Luiz Szwarcfiter / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4954442 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5501779 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sources and sinks in comparability graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3128916 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5501778 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Modular decomposition and transitive orientation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Comparability and Permutation Graphs / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0166-218x(01)00283-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2034559501 / rank | |||
Normal rank |
Latest revision as of 12:05, 30 July 2024
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