Descripción
|
|
---|---|
El problema de maximizar el número de vértices que no son visibles dos a dos en un polígono simple P, (Maximum Hidden Vertex Set) es un problema NP-duro. En este trabajo se resuelve el problema para dos tipos de polígonos: espirales e histogramas. Para los primeros se obtiene un algoritmo lineal que resuelve el problema MHVS y cotas para el máximo número h de vértices ocultos. Para polígonos histograma se demuestra que h = r − (p − 1), siendo p el número de lados fondo. | |
Internacional
|
No |
Nombre congreso
|
VI Jornadas de Matemática Discreta y Algorítmica, JMDA08 |
Tipo de participación
|
960 |
Lugar del congreso
|
Lleida |
Revisores
|
Si |
ISBN o ISSN
|
978-84-8409-263-6 |
DOI
|
|
Fecha inicio congreso
|
21/07/2008 |
Fecha fin congreso
|
23/07/2008 |
Desde la página
|
85 |
Hasta la página
|
94 |
Título de las actas
|
Actas de las Jornadas de Matemática Discreta y Algorítmica, JMDA'08 |