On the helly property of some intersection graphs

Santos, Tanilson Dias dos

Please use this identifier to cite or link to this item: http://hdl.handle.net/11612/3663

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	Szwarcfiter, Jayme Luiz	-
dc.contributor.author	Santos, Tanilson Dias dos	-
dc.date.accessioned	2022-02-25T13:00:01Z	-
dc.date.available	2022-02-25T13:00:01Z	-
dc.date.issued	2020-09-23	-
dc.identifier.citation	SANTOS, Tanilson Dias dos. On the helly property of some intersection graphs. 2020. 94 f. Tese (Doutorado em Engenharia de Sistemas e Computação) – Universidade Federal do Rio de Janeiro, Programa de Pós-Graduação em Engenharia de Sistemas e Computação, Rio de Janeiro, 2020.	pt_BR
dc.identifier.uri	http://hdl.handle.net/11612/3663	-
dc.description.abstract	An EPG graph G is an edge-intersection graph of paths on a grid. In this doctoral thesis we will mainly explore the EPG graphs, in particular B1-EPG graphs. However, other classes of intersection graphs will be studied such as VPG, EPT and VPT graph classes, in addition to the parameters Helly number and strong Helly number to EPG and VPG graphs. We will present the proof of NP-completeness to Helly-B1-EPG graph recognition problem. We investigate the parameters Helly number and the strong Helly number in both graph classes, EPG and VPG in order to determine lower bounds and upper bounds for this parameters. We completely solve the problem of determining the Helly and strong Helly numbers, for Bk-EPG, and Bk-VPG graphs, for each value k. Next, we present the result that every Chordal B1-EPG graph is simultaneously in the VPT and EPT graph classes. In particular, we describe structures that occur in B1-EPG graphs that do not support a Helly-B1-EPG representation and thus we define some sets of subgraphs that delimit Helly subfamilies. In addition, features of some non-trivial graph families that are properly contained in Helly-B1 EPG are also presented.	pt_BR
dc.language.iso	en_US	pt_BR
dc.publisher	Universidade Federal do Rio de Janeiro	pt_BR
dc.rights	Creative Commons	pt_BR
dc.subject	EPG; EPT; Grafos de Interseção; NP-completude; Propriedade Helly; VPG; VPT; Helly property; Intersection graphs; NP-completeness	pt_BR
dc.title	On the helly property of some intersection graphs	pt_BR
dc.type	Tese	pt_BR
dc.contributor.advisor-co	Souza, Uéverton dos Santos	-
dc.description.resumo	EPG é um grafo de aresta-interseção de caminhos sobre uma grade. Nesta tese de doutorado exploraremos principalmente os grafos EPG, em particular os grafos B1-EPG. Entretanto, outras classes de grafos de interseção serão estu dadas, como as classes de grafos VPG, EPT e VPT, além dos parâmetros número de Helly e número de Helly forte nos grafos EPG e VPG. Apresentaremos uma prova de NP-completude para o problema de reconhecimento de grafos B1-EPG Helly. Investigamos os parâmetros número de Helly e o número de Helly forte nessas duas classes de grafos, EPG e VPG, a fim de determinar limites inferiores e superi ores para esses parâmetros. Resolvemos completamente o problema de determinar o número de Helly e o número de Helly forte para os grafos Bk-EPG e Bk-VPG, para cada valor k. Em seguida, apresentamos o resultado de que todo grafo B1-EPG Chordal está simultaneamente nas classes de grafos VPT e EPT. Em particular, descrevemos estruturas que ocorrem em grafos B1-EPG que não suportam uma representação B1-EPG-Helly e assim definimos alguns conjuntos de subgrafos que delimitam sub famílias Helly. Além disso, também são apresentadas características de algumas famílias de grafos não triviais que estão propriamente contidas em B1-EPG-Helly	pt_BR
dc.publisher.country	Brasil	pt_BR
dc.publisher.program	Programa de Pós-Graduação em Filosofia em Engenharia de Sistemas e Computação	pt_BR
dc.publisher.campus	Rio de Janeiro	pt_BR
dc.subject.cnpq	CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO	pt_BR
Appears in Collections:	Teses

Files in This Item:

File	Description	Size	Format
Tanilson Dias dos Santos - Tese.pdf		1.83 MB	Adobe PDF	View/Open

Show simple item record