Tractabilidades e intractabilidades en grafos de intersección geométrica
Autores: Uehara, Ryuhei
Idioma: Inglés
Editor: MDPI
Año: 2013
Acceso abierto
Artículo científico
2013
Tractabilidades e intractabilidades en grafos de intersección geométrica
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Gráfico
Intersección
Objetos
Vértices
Representaciones geométricas
Tratabilidad
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 28
Citaciones: Sin citaciones
Un grafo se dice que es un grafo de intersección si hay un conjunto de objetos tal que cada vértice corresponde a un objeto y dos vértices son adyacentes si y solo si los objetos correspondientes tienen una intersección no vacía. Hay varias clases de grafos naturales que tienen representaciones de intersección geométrica. Las representaciones geométricas a veces ayudan a demostrar la tratabilidad/intratabilidad de problemas en clases de grafos. En este artículo, mostramos algunos resultados demostrados utilizando representaciones geométricas.
Descripción
Un grafo se dice que es un grafo de intersección si hay un conjunto de objetos tal que cada vértice corresponde a un objeto y dos vértices son adyacentes si y solo si los objetos correspondientes tienen una intersección no vacía. Hay varias clases de grafos naturales que tienen representaciones de intersección geométrica. Las representaciones geométricas a veces ayudan a demostrar la tratabilidad/intratabilidad de problemas en clases de grafos. En este artículo, mostramos algunos resultados demostrados utilizando representaciones geométricas.