A note on transitive orientations with maximum sets of sources and sinks
type: Item
instance of: scholarly article
title: A note on transitive orientations with maximum sets of sources and sinks
zbMATH Open document ID: 1007.05087
DOI: 10.1016/S0166-218X(01)00283-9
published in: Discrete Applied Mathematics
publication date: 2002-08-29T00:00:00Z
review text: 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.
reviewed by: Zbigniew Lonc
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1792315
zbMATH Keywords: comparability graph
zbMATH Keywords: transisive orientation
zbMATH Keywords: source
zbMATH Keywords: sink
zbMATH Keywords: algorithms
author: Celina M. H. de Figueiredo
author: John Gimbel
author: Célia P. de Mello
author: Jayme L. Szwarcfiter
MaRDI profile type: Publication
cites work: Q4954442
cites work: Q5501779
cites work: Sources and sinks in comparability graphs
cites work: Q3128916
cites work: Q5501778
cites work: Modular decomposition and transitive orientation
cites work: On Comparability and Permutation Graphs
full work available at URL: s0166-218x(01)00283-9
OpenAlex ID: W2034559501
description: scientific article; zbMATH DE number 1792315