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.|
|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.|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.