| Compartilhamento |
|
Exportar este item:
Use este identificador para citar ou linkar para este item:
http://www.bdtd.uerj.br/handle/1/7660| Tipo do documento: | Dissertação |
| Título: | Um problema extremal em contagem de intervalo |
| Título(s) alternativo(s): | An extremal problem on the interval count |
| Autor: | Medeiros, Lívia Salgado  |
| Primeiro orientador: | Oliveira, Fabiano de Souza |
| Primeiro coorientador: | Szwarcfiter, Jayme Luiz |
| Primeiro membro da banca: | Faria, Luerbio |
| Segundo membro da banca: | Cerioli, Márcia Rosana |
| Resumo: | Esta dissertação apresenta um estudo sobre o problema da contagem de intervalo para grafos e ordens de intervalo. A contagem de intervalo de um dado grafo (resp. ordem) é o menor número de tamanhos de intervalo necessário em um modelo deste grafo (resp.ordem). No primeiro instante, a pesquisa foi direcionada a uma revisão da literatura sobre o problema da contagem de intervalo e seus principais resultados. Em seguida, tratamos do problema extremal que consiste em determinar o menor grafo ou ordem que possui a contagem de intervalo igual a dado natural k. Em particular, estudamos uma conjectura acerca deste problema extremal, verificando sua validade quando restrita às classes das ordens trivialmente perfeitas e de divisão. São apresentados resultados também acerca das classes de ordens e grafos que podem ser representados por dois tamanhos específicos, no que se refere à hierarquia de inclusão entre tais classes |
| Abstract: | This dissertation presents a study on the problem of interval count for interval graphs and interval orders. Firstly, the research was directed to a review of the existing literature on the problem of interval count and its main results. Then, we deal with an extremal problem which consists in determining the smallest order or graph that has interval count equal to k. In particular, we study a conjecture about this extremal problem, verifying its validity when it is restricted to the classes of trivially perfect and split classes. It is also presented results about the classes of orders or graphs that can be represented by two specific sizes, with respect to the inclusion hierarchy among those classes |
| Palavras-chave: | Extremal Problem Interval Count Interval Graphs Interval Orders Split Graph Trivially Perfect Graph Contagem de Intervalo Grafos de Intervalo Grafo de Divisão Grafo Trivialmente Perfeito Ordens de Intervalo Problema Extremal Teoria dos grafos Algoritmos |
| Área(s) do CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Idioma: | por |
| País: | BR |
| Instituição: | Universidade do Estado do Rio de Janeiro |
| Sigla da instituição: | UERJ |
| Departamento: | Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística |
| Programa: | Programa de Pós-Graduação em Ciências Computacionais |
| Citação: | MEDEIROS, Lívia Salgado. Um problema extremal em contagem de intervalo. 2018. 66 f. Dissertação (Mestrado em Modelagem matemático-estatístico-computacional) - Universidade do Estado do Rio de Janeiro, Rio de Janeiro, 2018. |
| Tipo de acesso: | Acesso Aberto |
| URI: | http://www.bdtd.uerj.br/handle/1/7660 |
| Data de defesa: | 14-Nov-2018 |
| Aparece nas coleções: | Mestrado em Ciências Computacionais |
Arquivos associados a este item:
| Arquivo | Tamanho | Formato | |
|---|---|---|---|
| Dissertacao_Livia_CComp_2018.pdf | 1,68 MB | Adobe PDF | Baixar/Abrir Pré-Visualizar |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.