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

• 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.