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
From MaRDI portal
Publication:2345859
DOI10.1016/j.ipl.2015.02.007zbMath1328.68144OpenAlexW2145102334MaRDI QIDQ2345859
Mario Valencia-Pabon, Guillermo Durán, Amedeo Napoli, Flavia Bonomo-Braberman
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
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (5)
The maximum independent union of cliques problem: complexity and exact approaches ⋮ Complexity of the cluster deletion problem on subclasses of chordal graphs ⋮ Unnamed Item ⋮ Cluster deletion on interval graphs and split related graphs ⋮ A new approximate cluster deletion algorithm for diamond-free graphs
Cites Work
- The cluster deletion problem for cographs
- Correlation clustering
- Cluster editing with locally bounded modifications
- On the minimum sum coloring of \(P_4\)-sparse graphs
- A Helly theorem for convexity in graphs
- A tree representation for \(P_ 4\)-sparse graphs
- On chromatic sums and distributed resource allocation
- Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
- Cluster graph modification problems
- Even faster parameterized cluster deletion and cluster editing
- Minimum Sum Coloring of P4-sparse graphs
- Recognizing $P_4 $-Sparse Graphs in Linear Time
- Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\cal NP$-Complete
- Approximation results for the optimum cost chromatic partition problem
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
