Cross-identification of stellar catalogs with multiple stars: Complexity and Resolution
Archivos
Fecha
2018-08
Autores
Título de la revista
ISSN de la revista
Título del volumen
Editor
Elsevier
Resumen
Descripción
In this work, I present an optimization problem which consists of assigning entries
of a stellar catalog to multiple entries of another stellar catalog such that the probability
of such assignment is maximum. I show a way of modeling it as a Maximum
Weighted Stable Set Problem which is further used to solve a real astronomical
instance and I partially characterize the forbidden subgraphs of the resulting family
of graphs given by that reduction. Finally, I prove that the problem is NP-Hard.
Palabras clave
Cross-identification, Complexity, Maximum Weighted Stable Set Problem, Forbidden subgraphs, http://biblio-int.mincyt.gob.ar/ford/1.3