A new approximate cluster deletion algorithm for diamond-free graphs

DOI10.1007/S10878-019-00477-ZMaRDI QIDQ2292150zbMATH OpenOpenAlexWikidataFDO

Authors Sabrine Malek, Wady Naanaa

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

(Butterflycluster deletion (CD)diamond)-free graphsdiamond-free graphsmaximal cliquepolynomial algorithmsuboptimal algorithm

Mathematics Subject Classification ID

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

Recommendations

• A polynomial-time algorithm for cluster deletion on (diamond, Butterfly)-free graphs
• Cluster deletion revisited
• The cluster deletion problem for cographs
• Cluster graph modification problems
• Complexity of the cluster deletion problem on subclasses of chordal graphs

Cites work

• A more effective linear kernelization for cluster editing
• A New Algorithm for Generating All the Maximal Independent Sets
• A note on the problem of reporting maximal cliques
• 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
• Algorithm 457: finding all cliques of an undirected graph
• Algorithm Theory - SWAT 2004
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• Cluster editing with locally bounded modifications
• Cluster graph modification problems
• Complexity classification of some edge modification problems
• Complexity of the cluster deletion problem on subclasses of chordal graphs
• Graph-based data clustering with overlaps
• Maximum matching and a polyhedron with 0,1-vertices
• On generating all maximal independent sets
• Parameterized algorithms
• The cluster deletion problem for cographs

Cited in

(1)

• A polynomial-time algorithm for cluster deletion on (diamond, Butterfly)-free graphs

Describes a project that uses

Uses Software

• Algorithm 457
• ProClust

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

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