A note on transitive orientations with maximum sets of sources and sinks期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

A note on transitive orientations with maximum sets of sources and sinks

Authors:	Celina M H de Figueiredo John Gimbel C lia P Mello and Jayme L Szwarcfiter

Institution:	^a Instituto de Matemática and COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 68530, 21945-970, Rio de Janeiro, RJ, Brazil ^b Mathematical Sciences, University of Alaska, Fairbanks, Alaska 99775, USA ^c Instituto de Computação, Universidade Estadual de Campinas, Caixa Postal 6176, 13081-970, Campinas, SP, Brazil ^d Núcleo de Computação Eletrônica, Instituto de Matemática and COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 2324, 20001-970, Rio de Janeiro, RJ, Brazil

Abstract:	Given a transitive orientation of a comparability graph G, a vertex of G is a source (sink) if it has indegree (outdegree) zero in , respectively. A source set of G is a subset of vertices formed by sources of some transitive orientation . A pair of subsets S,TV(G) is a source–sink pair of G when the vertices of S and T are sources and sinks, of some transitive orientation , 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.

Keywords:	Algorithms Comparability graphs Modular decomposition Source sets Transitive orientation
本文献已被 ScienceDirect 等数据库收录！