Registro:
| Documento: | Tesis de Grado |
| Título: | Biclique coloreo de grafos |
| Título alternativo: | Graph biclique coloring |
| Autor: | Terlisky, Pablo Ezequiel |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2010 |
| Fecha en portada: | 20 Julio 2010 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Groshaus, Marina Esther |
| Director Asistente: | Soulignac, Francisco Juan |
| Jurado: | Factorovich, Pablo Matías; Lin, Min Chih |
| Idioma: | Español |
| Palabras clave: | TEORIA DE GRAFOS; COLOREO DE GRAFOS; CLIQUE COLOREO; BICLIQUE COLOREO; COMPLEJIDAD DE BICLIQUE COLOREO; BICLIQUES; GRAFOS SPLIT; GRAFOS THRESHOLD; GRAFOS BLOQUE; GRAFOS (W4, DART, GEM) FREEGRAPH THEORY; GRAPH COLORING; CLIQUE-COLORING; BICLIQUE COLORING; COMPLEXITY OF BICLIQUE COLORING; BICLIQUES; SPLIT GRAPHS; THRESHOLD GRAPHS; BLOCK GRAPHS; (W4, DART, GEM) FREE GRAPHS |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000746_Terlisky |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000746_Terlisky.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000746_Terlisky |
| Ubicación: | Dep.COM 000746 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Terlisky, Pablo Ezequiel. (2010). Biclique coloreo de grafos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000746_Terlisky |
Resumen:
Un k-clique-coloreo de un grafo es una asignación de k colores a sus vértices de manera que toda clique tiene al menos dos vértices con colores distintos. El problema de determinar si un grafo es k-clique coloreable es Σp 2 -Completo, aunque es más fácil para ciertas clases de grafos. En esta tesis, definimos el problema de k-biclique-coloreo como el análogo del de k-clique-coloreo en el contexto de bicliques. Probamos que el problema de determinar si un grafo es k-biclique-coloreable es Σp 2 -Completo para k ≥ 2, y mostramos algunas clases de grafos para las que el problema está en NP o es polinomial.
Abstract:
A k-clique-coloring of a graph is an assignment of k colors to its vertices such that every clique has at least two vertices with different colors. For k ≥ 2, the problem of kclique-coloring a graph is Σp 2 -complete, though it is easier for some graph classes. In this work, we define the k-biclique-coloring problem as the analogue of the k-clique-coloring for bicliques. We prove that the k-biclique-coloring problem is Σp 2 -complete for k ≥ 2, and show some graph classes for which the problem is in NP or polynomial.
Citación:
---------- APA ----------
Terlisky, Pablo Ezequiel. (2010). Biclique coloreo de grafos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000746_Terlisky
---------- CHICAGO ----------
Terlisky, Pablo Ezequiel. "Biclique coloreo de grafos". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2010.https://hdl.handle.net/20.500.12110/seminario_nCOM000746_Terlisky
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000746_Terlisky.pdf
Distrubución geográfica
