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:
| Autores principales: | , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_00200190_v115_n12_p913_Lin |
| Aporte de: |
| id |
todo:paper_00200190_v115_n12_p913_Lin |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_00200190_v115_n12_p913_Lin2023-10-03T14:16:40Z A faster algorithm for the cluster editing problem on proper interval graphs Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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 Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. 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. |
| format |
JOUR |
| author |
Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. |
| author_facet |
Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. |
| author_sort |
Lin, M.C. |
| 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 |
| url |
http://hdl.handle.net/20.500.12110/paper_00200190_v115_n12_p913_Lin |
| work_keys_str_mv |
AT linmc afasteralgorithmfortheclustereditingproblemonproperintervalgraphs AT soulignacfj afasteralgorithmfortheclustereditingproblemonproperintervalgraphs AT szwarcfiterjl afasteralgorithmfortheclustereditingproblemonproperintervalgraphs AT linmc fasteralgorithmfortheclustereditingproblemonproperintervalgraphs AT soulignacfj fasteralgorithmfortheclustereditingproblemonproperintervalgraphs AT szwarcfiterjl fasteralgorithmfortheclustereditingproblemonproperintervalgraphs |
| _version_ |
1807322687710691328 |