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 P-4-comparability graphs
Author: de Figueiredo, CMH
Gimbel, J
Mello, CP
Szwarcfiter, JL
Abstract: We characterize even and odd pairs in comparability and in P-4-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(n(2)m) for P-4-comparability graphs. The former represents an improvement over a recent algorithm of complexity O(nm). (C) 1999 Elsevier Science B.V. All rights reserved.
Subject: algorithms
comparability graphs
parity path problems
Country: Holanda
Editor: Elsevier Science Bv
Citation: Discrete Applied Mathematics. Elsevier Science Bv, v. 91, n. 41699, n. 293, n. 297, 1999.
Rights: fechado
Identifier DOI: 10.1016/S0166-218X(98)00139-5
Date Issue: 1999
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000078481300021.pdf352.6 kBAdobe PDFView/Open

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