Theoretical Computer Science

DOI10.1007/11560586MaRDI QIDQ5395073zbMATH OpenOpenAlexFDO

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

Publication date 1 November 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11560586

zbMATH Keywords

Approximation algorithminterval graphsline graph of bipartite graphsNP-complete problemspartial \(k\)-treeweighted coloring

Mathematics Subject Classification ID

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

Recommendations

• Weighted coloring: further complexity and approximability results
• scientific article; zbMATH DE number 1953087
• scientific article; zbMATH DE number 4144006
• Max-coloring of vertex-weighted graphs
• Weighted coloring in trees

Cited in

(18)

• Models and heuristic algorithms for a weighted vertex coloring problem
• Weighted coloring: further complexity and approximability results
• The weighted coloring problem for two graph classes characterized by small forbidden induced structures
• Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
• A comparison of integer programming models for the partial directed weighted improper coloring problem
• Improved approximations for weighted and unweighted graph problems
• Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs
• A coloring problem for weighted graphs
• A polyhedral study of the maximum stable set problem with weights on vertex-subsets
• Clique partitioning of interval graphs with submodular costs on the cliques
• Coloring fuzzy circular interval graphs
• A new polynomial-time algorithm for the maximum weighted (?(G) ? 1)-coloring problem in comparability graphs
• scientific article; zbMATH DE number 1953087 (Why is no real title available?)
• Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes
• Max-coloring of vertex-weighted graphs
• Mobility offer allocations in corporate settings
• Bounds and fixed-parameter algorithms for weighted improper coloring
• Weighted-set graph colorings

This page was built for publication: Theoretical Computer Science

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