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

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. © 2015 Elsevier B.V. All rights reserved.

Guardado en:

Detalles Bibliográficos
Autores principales:	Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L.
Formato:	JOUR
Materias:	Cluster editing problem Graph algorithms Linear space algorithm Proper interval models Algorithms Cluster editing Interval models Linear space algorithms Linear spaces Proper interval graphs Time algorithms Clustering algorithms
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_00200190_v115_n12_p913_Lin
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

Descripción
Sumario:	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. © 2015 Elsevier B.V. All rights reserved.