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.
Gimbel J.
Mello C.P.
Szwarcfiter J.L.
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.
Rights: fechado
Identifier DOI: 
Date Issue: 1999
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-1842583901.pdf352.6 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.