Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/101217
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.
Editor: 
Rights: fechado
Identifier DOI: 
Address: http://www.scopus.com/inward/record.url?eid=2-s2.0-1842583901&partnerID=40&md5=fdc7f86bebcb608d3ce1e4c83425c01a
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.