Artículo

A faster algorithm for the cluster editing problem on proper interval graphs

Lin, Min ChihIcon ; Soulignac, Francisco JuanIcon ; Szwarcfiter, Jayme L.
Fecha de publicación: 12/2015
Editorial: Elsevier Science
Revista: Information Processing Letters
ISSN: 0020-0190
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

Resumen

We develop a linear-space O(n+m) time algorithm to solve the cluster editing problem for proper interval models, where n and m are the number of vertices and edges of the represented graph.
Palabras clave: GRAPH ALGORITHMS , CLUSTER EDITING PROBLEM , PROPER INTERVAL MODELS , LINEAR SPACE ALGORITHM
 
Archivos asociados
Thumbnail
 
Tamaño: 227.3Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Unported (CC BY-NC-SA 2.5)
Identificadores
URI: http://hdl.handle.net/11336/94321
DOI: http://dx.doi.org/10.1016/j.ipl.2015.07.009
URL: https://www.sciencedirect.com/science/article/pii/S0020019015001313
Colecciones
Articulos(SEDE CENTRAL)
Articulos de SEDE CENTRAL
Citación
Lin, Min Chih; Soulignac, Francisco Juan; Szwarcfiter, Jayme L.; A faster algorithm for the cluster editing problem on proper interval graphs; Elsevier Science; Information Processing Letters; 115; 12; 12-2015; 913-916
Compartir
Altmétricas