Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/73705
Type: Artigo de periódico
Title: The Graph Sandwich Problem for P-4-sparse graphs
Author: Dantas, S
Klein, S
de Mello, CP
Morgana, A
Abstract: The P-4-sparse Graph Sandwich Problem asks, given two graphs G(1) = (V, E-1) and G(2) = (V, E-2), whether there exists a graph G = (V, E) such that E-1 subset of E subset of E-2 and G is P-4-sparse. In this paper we present a polynomial-time algorithm for solving the Graph Sandwich Problem for P-4-sparse graphs. (C) 2008 Elsevier B.V. All rights reserved.
Subject: Algorithms
Computational complexity
Partition problems
Graph sandwich problems
Cographs
P-4-sparse graphs
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/j.disc.2008.01.014
Date Issue: 2009
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOS000266670000020.pdf532.41 kBAdobe PDFView/Open


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