Please use this identifier to cite or link to this item:
|Type:||Artigo de periódico|
|Title:||Even And Odd Pairs In Comparability And In P4-comparability Graphs|
|Author:||De Figueiredo C.M.H.|
|Abstract:||We characterize even and odd pairs in comparability and in P4-comparability graphs. The characterizations lead to simple algorithms for deciding whether a given pair of vertices forms an even or odd pair in these classes of graphs. The complexities of the proposed algorithms are O(n+m) for comparability graphs and O(n2w) for P4-comparability graphs. The former represents an improvement over a recent algorithm of complexity O(nm). © 1999 Elsevier Science B.V. All rights reserved.|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.