Sobre grafos cubridores de los grafos de comparabilidad

Un grafo es de comparabilidad si es posible orientar sus aristas en forma transitiva. Las primeras preguntas que surgen naturalmente son: el problema del reconocimiento, dado un grafo, ¿es de comparabilidad? Y si se tiene un grafo que es de comparabilidad, ¿cómo encontrar sus orientaciones transitiv...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Dobson, María Patricia
Otros Autores:	Swarcfiter, Jayme Luiz
Formato:	Tesis Tesis de doctorado
Lenguaje:	Español
Publicado:	2006
Materias:	Ciencias Exactas grafos grafos de comparabilidad grafos Treelike cubrimientos y restricciones
Acceso en línea:	http://sedici.unlp.edu.ar/handle/10915/2331 https://doi.org/10.35537/10915/2331
Aporte de:	SEDICI (UNLP) de Universidad Nacional de La Plata

id	I19-R120-10915-2331
record_format	dspace
spelling	I19-R120-10915-23312023-11-01T20:07:02Z http://sedici.unlp.edu.ar/handle/10915/2331 https://doi.org/10.35537/10915/2331 Sobre grafos cubridores de los grafos de comparabilidad Dobson, María Patricia 2006 2006 2008-05-16T03:00:00Z Swarcfiter, Jayme Luiz Gutiérrez, Marisa es Ciencias Exactas grafos grafos de comparabilidad grafos Treelike cubrimientos y restricciones Un grafo es de comparabilidad si es posible orientar sus aristas en forma transitiva. Las primeras preguntas que surgen naturalmente son: el problema del reconocimiento, dado un grafo, ¿es de comparabilidad? Y si se tiene un grafo que es de comparabilidad, ¿cómo encontrar sus orientaciones transitivas? Brevemente, podría decirse que el presente trabajo se ocupa de problemas mucho más específicos: dado un grafo de comparabilidad, ¿existe una orientación que verifique una cierta propiedad dada? y en este contexto se estudian dos problemas. El primer problema tratado en este trabajo es saber cuáles grafos de comparabilidad admiten una orientación cuyo grafo cubridor es un árbol. A dicha clase de grafos la llamamos treelike. El otro problema tratado en el presente trabajo es, dado un conjunto de aristas fijo en un grafo de comparabilidad, ¿existe una orientación del grafo tal que su grafo cubridor contenga a dicho conjunto? Este problema, que en cierto modo generaliza al anterior, tiene además aplicaciones en problemas de programación de tareas. Tesis digitalizada en SEDICI gracias a la Biblioteca del Departamento de Matemática de la Facultad de Ciencias Exactas (UNLP). Doctor en Ciencias Exactas, área Matemática Universidad Nacional de La Plata Facultad de Ciencias Exactas Tesis Tesis de doctorado http://creativecommons.org/licenses/by-nc-sa/4.0/ Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) application/pdf
institution	Universidad Nacional de La Plata
institution_str	I-19
repository_str	R-120
collection	SEDICI (UNLP)
language	Español
topic	Ciencias Exactas grafos grafos de comparabilidad grafos Treelike cubrimientos y restricciones
spellingShingle	Ciencias Exactas grafos grafos de comparabilidad grafos Treelike cubrimientos y restricciones Dobson, María Patricia Sobre grafos cubridores de los grafos de comparabilidad
topic_facet	Ciencias Exactas grafos grafos de comparabilidad grafos Treelike cubrimientos y restricciones
description	Un grafo es de comparabilidad si es posible orientar sus aristas en forma transitiva. Las primeras preguntas que surgen naturalmente son: el problema del reconocimiento, dado un grafo, ¿es de comparabilidad? Y si se tiene un grafo que es de comparabilidad, ¿cómo encontrar sus orientaciones transitivas? Brevemente, podría decirse que el presente trabajo se ocupa de problemas mucho más específicos: dado un grafo de comparabilidad, ¿existe una orientación que verifique una cierta propiedad dada? y en este contexto se estudian dos problemas. El primer problema tratado en este trabajo es saber cuáles grafos de comparabilidad admiten una orientación cuyo grafo cubridor es un árbol. A dicha clase de grafos la llamamos treelike. El otro problema tratado en el presente trabajo es, dado un conjunto de aristas fijo en un grafo de comparabilidad, ¿existe una orientación del grafo tal que su grafo cubridor contenga a dicho conjunto? Este problema, que en cierto modo generaliza al anterior, tiene además aplicaciones en problemas de programación de tareas.
author2	Swarcfiter, Jayme Luiz
author_facet	Swarcfiter, Jayme Luiz Dobson, María Patricia
format	Tesis Tesis de doctorado
author	Dobson, María Patricia
author_sort	Dobson, María Patricia
title	Sobre grafos cubridores de los grafos de comparabilidad
title_short	Sobre grafos cubridores de los grafos de comparabilidad
title_full	Sobre grafos cubridores de los grafos de comparabilidad
title_fullStr	Sobre grafos cubridores de los grafos de comparabilidad
title_full_unstemmed	Sobre grafos cubridores de los grafos de comparabilidad
title_sort	sobre grafos cubridores de los grafos de comparabilidad
publishDate	2006
url	http://sedici.unlp.edu.ar/handle/10915/2331 https://doi.org/10.35537/10915/2331
work_keys_str_mv	AT dobsonmariapatricia sobregrafoscubridoresdelosgrafosdecomparabilidad
_version_	1807220193411203072

Sobre grafos cubridores de los grafos de comparabilidad

Ejemplares similares