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

DOI10.1016/J.IPL.2015.07.009MaRDI QIDQ495665zbMATH OpenOpenAlexFDO

Authors Min Chih Lin, Francisco J. Soulignac, Jayme L. 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

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

Recommendations

• Cluster editing problem for points on the real line: a polynomial time algorithm
• Efficient algorithms for cluster editing
• Exact algorithms for cluster editing: Evaluation and experiments
• Exact Algorithms for Cluster Editing: Evaluation and Experiments
• Cluster editing

Cites work

• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A \(2k\) kernel for the cluster editing problem
• A golden ratio parameterized algorithm for cluster editing
• Applying modular decomposition to parameterized cluster editing problems
• Cluster editing
• Cluster editing problem for points on the real line: a polynomial time algorithm
• Cluster editing with locally bounded modifications
• Cluster editing with locally bounded modifications revisited
• Cluster graph modification problems
• Exact algorithms for cluster editing: Evaluation and experiments
• Fixed-parameter enumerability of cluster editing and related problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph-based data clustering with overlaps
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• NP-hard problems in hierarchical-tree clustering

Cited in

(2)

• A PTAS for the Cluster Editing Problem on Planar Graphs
• Cluster editing problem for points on the real line: a polynomial time algorithm

This page was built for publication: A faster algorithm for the cluster editing problem on proper interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q495665)