Minimum entropy coloring

DOI10.1007/s10878-008-9152-2zbMath1163.90765OpenAlexW2093744170MaRDI QIDQ1016051

Gwenaël Joret, Samuel Fiorini, Jean Cardinal

Publication date: 4 May 2009

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

Full work available at URL: https://doi.org/10.1007/s10878-008-9152-2

zbMATH Keywords

entropycomplexitygraph coloring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Coloring of graphs and hypergraphs (05C15)

Related Items (4)

Sorting under partial information (without the ellipsoid algorithm). ⋮ Minimum Entropy Combinatorial Optimization Problems ⋮ Minimum entropy combinatorial optimization problems ⋮ Clique partitioning with value-monotone submodular cost

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Entropy and sorting.
• Zero knowledge and the chromatic number
• Geometric algorithms and combinatorial optimization.
• On certain polytopes associated with graphs
• On the equality of the partial Grundy and upper ochromatic numbers of graphs
• Efficient labeling procedures for image partition encoding.
• Feasible edge colorings of trees with cardinality constraints
• Algorithmic graph theory and perfect graphs
• A short proof of the NP-completeness of minimum sum interval coloring
• An Efficient Test for Circular-Arc Graphs
• The Complexity of Coloring Circular Arcs and Chords
• The zero-error side information problem and chromatic numbers (Corresp.)
• Lossless and near-lossless source coding for multiple access networks
• Source coding and graph entropies
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• Automata, Languages and Programming

This page was built for publication: Minimum entropy coloring