|
|||||
|
|
Sources and Sinks in Comparability Graphs |
|
| Authors: | Celina M H de Figueiredo John Gimbel Célia P Mello Jayme L Szwarcfiter |
| Institution: | (1) Instituto de Matemática, Universidade Federal do Rio de Janeiro, Caixa Postal 68530, 21945-970 Rio de Janeiro, RJ, Brazil;(2) Mathematical Sciences, University of Alaska, Fairbanks, Alaska, 99775, U.S.A;(3) Instituto de Computação, Universidade Estadual de Campinas, Caixa Postal 6176, 13081-970 Campinas, SP, Brazil;(4) Núcleo de Computação Eletrônica and Instituto de Matemática, Universidade Federal do Rio de Janeiro, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil |
| Abstract: | We prove that a subset S of vertices of a comparability graph G is a source set if and only if each vertex of S is a source and there is no odd induced path in G between two vertices of S. We also characterize pairs of subsets corresponding to sources and sinks, respectively. Finally, an application to interval graphs is obtained. |
| Keywords: | algorithms comparability graphs sources sinks |
| 本文献已被 SpringerLink 等数据库收录！ | |