Linear-time Algorithms for Maximum Sets of Sources and sinks

✍ Scribed by Celina M.H. de Figueiredo; John Gimbel; Célia Picinin de Mello; Jayme L. Szwarcfiter

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 255 KB
• Volume: 3
• Category: Article
• ISSN: 1571-0653
• DOI: 10.1016/s1571-0653(05)80062-9

✦ Synopsis

Let G denote a simple non-trivial connected undirected graph, with vertex set V (G) and edge set E(G). Write n = jV (G)j and m = jE(G)j. L e t G represent an acyclic orientation of G. We say that G is transitive when (v w) (w z) 2 E( G) implies (v z) 2 E( G), for all v w z2 V (G) and we say that G is a comparability graph when it admits a transitive orientation. If v has indegree or outdegree zero in G, then v is a source or a sink, respectively. A source (sink) of G is a vertex which is a source (sink) of some transitive orientation of G. A source (sink) set of G is a subset of vertices which are simultaneously sources (sinks) in some transitive orientation of the graph. 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, respectively, of some transitive orientation of G. A source set S is exact when G admits a transitive orientation G having the vertices of S as the only sources of G. Analogously, w e de ne exact source-sink pair.