A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to P₄-sparse graphs

DOI10.1016/J.IPL.2015.02.007MaRDI QIDQ2345859zbMATH OpenOpenAlexFDO

Authors Guillermo Durán, Amedeo Napoli, Mario Valencia-Pabon, Flavia Bonomo

Publication date 21 May 2015

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

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

zbMATH Keywords

\(P_4\)-sparsecluster deletiongraph algorithmssum coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Minimum sum coloring of \(P_{4}\)-sparse graphs
• On the minimum sum coloring of P₄-sparse graphs
• Cluster deletion revisited
• Cluster deletion on interval graphs and split related graphs
• A polynomial-time algorithm for cluster deletion on (diamond, Butterfly)-free graphs

Cites work

• A Helly theorem for convexity in graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Approximation results for the optimum cost chromatic partition problem
• Cluster editing with locally bounded modifications
• Cluster graph modification problems
• Correlation clustering
• Even faster parameterized cluster deletion and cluster editing
• Minimum sum coloring of \(P_{4}\)-sparse graphs
• On chromatic sums and distributed resource allocation
• On the minimum sum coloring of P₄-sparse graphs
• Recognizing P₄ -Sparse Graphs in Linear Time
• Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is \cal NP-Complete
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• The cluster deletion problem for cographs

Cited in

(10)

• Cluster deletion on interval graphs and split related graphs
• The maximum independent union of cliques problem: complexity and exact approaches
• A new approximate cluster deletion algorithm for diamond-free graphs
• Complexity of the cluster deletion problem on subclasses of chordal graphs
• Cluster deletion on interval graphs and split related graphs
• When can cluster deletion with bounded weights be solved efficiently?
• An exact algorithm for the minimum sum coloring problem on partially decomposable graphs
• A fast local search algorithm for minimum sum coloring problem on massive graphs
• When can cluster deletion with bounded weights be solved efficiently?
• On the minimum sum coloring of P₄-sparse graphs

This page was built for publication: 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

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