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

DOI10.1016/j.ipl.2015.07.009zbMath1338.68113OpenAlexW1424642028MaRDI QIDQ495665

Min Chih Lin, Francisco J. Soulignac, Jayme Luiz Szwarcfiter

Publication date: 15 September 2015

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

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

zbMATH Keywords

graph algorithmscluster editing problemlinear space algorithmproper interval models

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• A \(2k\) kernel for the cluster editing problem
• Graph-based data clustering with overlaps
• Exact algorithms for cluster editing: Evaluation and experiments
• Cluster editing with locally bounded modifications
• Fixed-parameter enumerability of cluster editing and related problems
• NP-hard problems in hierarchical-tree clustering
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Cluster editing problem for points on the real line: a polynomial time algorithm
• Cluster graph modification problems
• A golden ratio parameterized algorithm for cluster editing
• Applying modular decomposition to parameterized cluster editing problems
• Cluster Editing with Locally Bounded Modifications Revisited
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Cluster Editing