A new approximate cluster deletion algorithm for diamond-free graphs

DOI10.1007/s10878-019-00477-zzbMath1434.90172OpenAlexW2988952497WikidataQ126853192 ScholiaQ126853192MaRDI QIDQ2292150

Wady Naanaa, Sabrine Malek

Publication date: 3 February 2020

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-019-00477-z

zbMATH Keywords

polynomial algorithmdiamond-free graphsmaximal cliquesuboptimal algorithm(Butterflycluster deletion (CD)diamond)-free graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Uses Software

• Algorithm 457
• ProClust

Cites Work

• The cluster deletion problem for cographs
• Graph-based data clustering with overlaps
• Complexity of the cluster deletion problem on subclasses of chordal graphs
• Cluster editing with locally bounded modifications
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• A note on the problem of reporting maximal cliques
• A more effective linear kernelization for cluster editing
• On generating all maximal independent sets
• Cluster graph modification problems
• A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to \(P_4\)-sparse graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Algorithm Theory - SWAT 2004
• Parameterized Algorithms
• Maximum matching and a polyhedron with 0,1-vertices
• Algorithm 457: finding all cliques of an undirected graph
• On the relation of strong triadic closure and cluster deletion
• Complexity classification of some edge modification problems

This page was built for publication: A new approximate cluster deletion algorithm for diamond-free graphs