Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: A Note On Transitive Orientations With Maximum Sets Of Sources And Sinks
Author: De Figueiredo C.M.H.
Gimbel J.
Mello C.P.
Szwarcfiter J.L.
Abstract: Given a transitive orientation G → of a comparability graph G, a vertex of G is a source (sink) if it has indegree (outdegree) zero in G →, respectively. A source set of G is a subset of vertices formed by sources of some transitive orientation G →. A pair of subsets S,T⊆V(G) is a source-sink pair of G when the vertices of S and T are sources and sinks, of some transitive orientation G →, respectively. We describe algorithms for finding a transitive orientation with a maximum source-sink pair in a comparability graph. The algorithms are applications of modular decomposition and are all of linear-time complexity. © 2002 Elsevier Science B.V.
Rights: fechado
Identifier DOI: 10.1016/S0166-218X(01)00283-9
Date Issue: 2002
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-84867995436.pdf69.46 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.