The optimal cost chromatic partition problem for trees and interval graphs

DOI10.1007/3-540-62559-3_23MaRDI QIDQ6550551zbMATH OpenFDO

Authors Leo Kroon, Arunabha Sen, Haiyong Deng, Asim Roy

Publication date 5 June 2024

Full work available at URL https://doi.org/10.1007/3-540-62559-3_23

Mathematics Subject Classification ID

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

Recommendations

• Approximation results for the optimum cost chromatic partition problem
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• scientific article; zbMATH DE number 1163713
• On a graph partition problem with application to VLSI layout
• On the sum coloring problem on interval graphs

Cites work

• Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times
• An analysis of shift class design problems
• Approximation Algorithms for Fixed Job Schedule Problems
• Games of Boldness, Where the Player Performing the Hardest Task Wins
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 3887724 (Why is no real title available?)
• scientific article; zbMATH DE number 3902681 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• License class design: Complexity and algorithms
• On a graph partition problem with application to VLSI layout
• On certain polytopes associated with graphs
• On the computational complexity of (maximum) class scheduling
• On the computational complexity of (maximum) shift class scheduling
• Perfect zero–one matrices
• Scheduling jobs with fixed start and end times
• The Complexity of Coloring Circular Arcs and Chords
• The Fixed Job Schedule Problem with Spread-Time Constraints
• The Fixed Job Schedule Problem with Working-Time Constraints
• The maximum k-colorable subgraph problem for chordal graphs
• The Strong Perfect Graph Conjecture for Planar Graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs

Cited in

(2)

• An improved bi-criteria evolutionary approach for the sum coloring of graphs
• An improved bi-criteria evolutionary approach for the sum coloring of graphs

This page was built for publication: The optimal cost chromatic partition problem for trees and interval graphs

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