Cluster editing problem for points on the real line: a polynomial time algorithm

DOI10.1016/j.ipl.2010.08.002zbMath1379.68258OpenAlexW2052386658MaRDI QIDQ1675767

Bassel Mannaa

Publication date: 3 November 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.08.002

zbMATH Keywords

dynamic programmingclusteringgraph algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

A new temporal interpretation of cluster editing ⋮ Cluster Editing ⋮ Even faster parameterized cluster deletion and cluster editing ⋮ A faster algorithm for the cluster editing problem on proper interval graphs ⋮ Complexity of the cluster deletion problem on subclasses of chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter enumerability of cluster editing and related problems
• Approximation algorithms for geometric median problems
• Cluster graph modification problems
• Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
• Aggregating inconsistent information

This page was built for publication: Cluster editing problem for points on the real line: a polynomial time algorithm