Weighted coloring: further complexity and approximability results

DOI10.1016/j.ipl.2005.09.013zbMath1181.68173OpenAlexW1498089635MaRDI QIDQ1045908

Jérôme Monnot, Bruno Escoffier, Vangelis Th. Paschos

Publication date: 18 December 2009

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

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/2128

zbMATH Keywords

NP-complete problemsapproximation algorithmsinterval graphspartial \(k\)-treeweighted coloringline graph of bipartite graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Related Items (29)

Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results ⋮ The assignment problem with nearly Monge arrays and incompatible partner indices ⋮ Polynomial approximation: a structural and operational study. (Abstract of thesis) ⋮ On the max-weight edge coloring problem ⋮ Batch Coloring Flat Graphs and Thin ⋮ Improved approximation algorithms for the max edge-coloring problem ⋮ Open shop scheduling with synchronization ⋮ Exact weighted vertex coloring via branch-and-price ⋮ Max-coloring paths: tight bounds and extensions ⋮ Bounded max-colorings of graphs ⋮ A survey on vertex coloring problems ⋮ Dual parameterization of Weighted Coloring ⋮ Clique Clustering Yields a PTAS for max-Coloring Interval Graphs ⋮ Saving colors and max coloring: some fixed-parameter tractability results ⋮ On the max coloring problem ⋮ Approximating the max-edge-coloring problem ⋮ On the Maximum Edge Coloring Problem ⋮ On the Max Coloring Problem ⋮ Clique clustering yields a PTAS for max-coloring interval graphs ⋮ Ruling out FPT algorithms for weighted coloring on forests ⋮ Max-coloring of vertex-weighted graphs ⋮ “Rent-or-Buy” Scheduling and Cost Coloring Problems ⋮ Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs ⋮ Weighted coloring on planar, bipartite and split graphs: Complexity and approximation ⋮ Models and heuristic algorithms for a weighted vertex coloring problem ⋮ Dual parameterization of weighted coloring ⋮ Clique partitioning with value-monotone submodular cost ⋮ Parameterized complexity of list coloring and max coloring ⋮ Interval scheduling with economies of scale

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A coloring problem for weighted graphs
• Algorithmic complexity of list colorings
• Generalized coloring for tree-like graphs
• The Complexity of Coloring Circular Arcs and Chords
• Algorithms and Computation
• Automata, Languages and Programming

This page was built for publication: Weighted coloring: further complexity and approximability results