ARAÚJO, R. T. Convexidades de caminhos e convexidades geométricas. 2014. 52 f. Dissertação (Mestrado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2014. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T18:18:58Z
No. of bitstreams: 1
2014_dis_rtaraújo.pdf: 997190 bytes, checksum: 1adad553da251fa0f87bb80fbe452db4 (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-09-23T16:28:22Z (GMT) No. of bitstreams: 1
2014_dis_rtaraújo.pdf: 997190 bytes, checksum: 1adad553da251fa0f87bb80fbe452db4 (MD5) / Made available in DSpace on 2015-09-23T16:28:22Z (GMT). No. of bitstreams: 1
2014_dis_rtaraújo.pdf: 997190 bytes, checksum: 1adad553da251fa0f87bb80fbe452db4 (MD5)
Previous issue date: 2014 / In this dissertation we present complexity results related to the hull number and the convexity number for P3 convexity. We show that the hull number and the convexity number are NP-hard even for bipartite graphs. Inspired by our research in convexity based on paths, we introduce a new convexity, where we defined as convexity of induced paths of order three or P∗ 3 . We show a relation between the geodetic convexity and the P∗ 3 convexity when the graph is a join of a Km with a non-complete graph. We did research in geometric convexity and from that we characterized graph classes under some convexities such as the star florest in P3 convexity, chordal cographs in P∗ 3 convexity, and the florests in TP convexity. We also demonstrated convexities that are geometric only in specific graph classes such as cographs in P4+-free convexity, F free graphs in F-free convexity and others. Finally, we demonstrated some results of geodesic convexity and P∗ 3 in graphs with few P4’s.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.repositorio.ufc.br:riufc/13355 |
| Date | January 2014 |
| Creators | Araújo, Rafael Teixeira de |
| Contributors | Sampaio , Rudini Menezes |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0023 seconds