The Graph Sandwich Problem for P-4-sparse graphs

dc.creatorDantas, S
dc.creatorKlein, S
dc.creatorde Mello, CP
dc.creatorMorgana, A
dc.date2009
dc.date38869
dc.date2014-11-15T00:07:43Z
dc.date2015-11-26T16:08:51Z
dc.date2014-11-15T00:07:43Z
dc.date2015-11-26T16:08:51Z
dc.date.accessioned2018-03-28T22:57:26Z
dc.date.available2018-03-28T22:57:26Z
dc.identifierDiscrete Mathematics. Elsevier Science Bv, v. 309, n. 11, n. 3664, n. 3673, 2009.
dc.identifier0012-365X
dc.identifierWOS:000266670000020
dc.identifier10.1016/j.disc.2008.01.014
dc.identifierhttp://www.repositorio.unicamp.br/jspui/handle/REPOSIP/73705
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/73705
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/73705
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1266468
dc.descriptionThe 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.
dc.description309
dc.description11
dc.descriptionSI
dc.description3664
dc.description3673
dc.languageen
dc.publisherElsevier Science Bv
dc.publisherAmsterdam
dc.publisherHolanda
dc.relationDiscrete Mathematics
dc.relationDiscret. Math.
dc.rightsfechado
dc.rightshttp://www.elsevier.com/about/open-access/open-access-policies/article-posting-policy
dc.sourceWeb of Science
dc.subjectAlgorithms
dc.subjectComputational complexity
dc.subjectPartition problems
dc.subjectGraph sandwich problems
dc.subjectCographs
dc.subjectP-4-sparse graphs
dc.subjectRecognition Algorithm
dc.subjectP4-sparse Graphs
dc.subjectLinear-time
dc.titleThe Graph Sandwich Problem for P-4-sparse graphs
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución