Weighted coloring: further complexity and approximability results
DOI10.1016/J.IPL.2005.09.013zbMATH Open1181.68173OpenAlexW1498089635MaRDI QIDQ1045908FDOQ1045908
Authors: Bruno Escoffier, Jérôme Monnot, 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
Recommendations
approximation algorithmsinterval graphsNP-complete problemspartial \(k\)-treeweighted coloringline graph of bipartite graphs
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- The Complexity of Coloring Circular Arcs and Chords
- A coloring problem for weighted graphs
- Title not available (Why is that?)
- Generalized coloring for tree-like graphs
- Title not available (Why is that?)
- Scheduling on a batch machine with job compatibilities
- Automata, Languages and Programming
- Algorithms and Computation
- Algorithmic complexity of list colorings
Cited In (39)
- Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
- “Rent-or-Buy” Scheduling and Cost Coloring Problems
- Batch Coloring Flat Graphs and Thin
- Solving the minimum-weighted coloring problem
- Coloring fuzzy circular interval graphs
- Interval scheduling with economies of scale
- Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes
- On the Max Coloring Problem
- On the max coloring problem
- Clique partitioning with value-monotone submodular cost
- A coloring problem for weighted graphs
- Saving colors and max coloring: some fixed-parameter tractability results
- Clique clustering yields a PTAS for max-coloring interval graphs
- Theoretical Computer Science
- Polynomial approximation: a structural and operational study. (Abstract of thesis)
- Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with 5-vertex prohibitions
- Exact weighted vertex coloring via branch-and-price
- Max-coloring paths: tight bounds and extensions
- Bounds and fixed-parameter algorithms for weighted improper coloring
- Dual parameterization of weighted coloring
- Dual parameterization of weighted coloring
- Open shop scheduling with synchronization
- Max-coloring of vertex-weighted graphs
- Title not available (Why is that?)
- Models and heuristic algorithms for a weighted vertex coloring problem
- Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs
- Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
- The assignment problem with nearly Monge arrays and incompatible partner indices
- Bounded max-colorings of graphs
- Weighted graph colorings
- Weighted-set graph colorings
- On the max-weight edge coloring problem
- Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
- Parameterized complexity of list coloring and max coloring
- On the Maximum Edge Coloring Problem
- A survey on vertex coloring problems
- Approximating the max-edge-coloring problem
- Improved approximation algorithms for the max edge-coloring problem
- Saving colors and max coloring: some fixed-parameter tractability results
This page was built for publication: Weighted coloring: further complexity and approximability results
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1045908)
