|
|||||
|
|
On transitive orientations with restricted covering graphs |
|
| Authors: | Maria Patricia Dobson Marisa Gutierrez |
| Affiliation: | a Departamento de Matemática, Universidad Nacional de Rosario, Argentina b Departamento de Matemática, Universidad Nacional de La Plata, Argentina c Laboratoire d'Informatique Algorithmique: Fondements et Applications, Université Paris 7-Denis Diderot, Paris, France d Instituto de Matemática, NCE and COPPE, Universidade Federal do Rio de Janeiro, Brasil |
| Abstract: | We consider the problem of finding a transitive orientation of a comparability graph, such that the edge set of its covering graph contains a given subset of edges. We propose a solution which employs the classical technique of modular tree decomposition. The method leads to a polynomial time algorithm to construct such an orientation or report that it does not exist. |
| Keywords: | Comparability graphs Combinatorial problems Modular decomposition |
| 本文献已被 ScienceDirect 等数据库收录！ | |