| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427229 | Information Processing Letters | 2015 | 4 Pages |
Abstract
•O(n+m)O(n+m) time algorithm to solve cluster editing problem for proper interval graphs.•A variation of Mannaa's dynamic programming algorithm with O(n)O(n) space.•Using straight representation for proper interval graphs.
We develop a linear-space O(n+m)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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Min Chih Lin, Francisco J. Soulignac, Jayme L. Szwarcfiter,