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
Publicado:	2015
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:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v115_n12_p913_Lin 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

id	paper:paper_00200190_v115_n12_p913_Lin
record_format	dspace
spelling	paper:paper_00200190_v115_n12_p913_Lin2023-06-08T14:40:21Z A faster algorithm for the cluster editing problem on proper interval graphs Cluster editing problem Graph algorithms Linear space algorithm Proper interval models Algorithms Cluster editing Graph algorithms Interval models Linear space algorithms Linear spaces Proper interval graphs Time algorithms Clustering algorithms 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. 2015 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v115_n12_p913_Lin http://hdl.handle.net/20.500.12110/paper_00200190_v115_n12_p913_Lin
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Cluster editing problem Graph algorithms Linear space algorithm Proper interval models Algorithms Cluster editing Graph algorithms Interval models Linear space algorithms Linear spaces Proper interval graphs Time algorithms Clustering algorithms
spellingShingle	Cluster editing problem Graph algorithms Linear space algorithm Proper interval models Algorithms Cluster editing Graph algorithms Interval models Linear space algorithms Linear spaces Proper interval graphs Time algorithms Clustering algorithms A faster algorithm for the cluster editing problem on proper interval graphs
topic_facet	Cluster editing problem Graph algorithms Linear space algorithm Proper interval models Algorithms Cluster editing Graph algorithms Interval models Linear space algorithms Linear spaces Proper interval graphs Time algorithms Clustering algorithms
description	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.
title	A faster algorithm for the cluster editing problem on proper interval graphs
title_short	A faster algorithm for the cluster editing problem on proper interval graphs
title_full	A faster algorithm for the cluster editing problem on proper interval graphs
title_fullStr	A faster algorithm for the cluster editing problem on proper interval graphs
title_full_unstemmed	A faster algorithm for the cluster editing problem on proper interval graphs
title_sort	faster algorithm for the cluster editing problem on proper interval graphs
publishDate	2015
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v115_n12_p913_Lin http://hdl.handle.net/20.500.12110/paper_00200190_v115_n12_p913_Lin
_version_	1768542392938397696

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

Ejemplares similares