On the max coloring problem
From MaRDI portal
Publication:690449
DOI10.1016/j.tcs.2012.07.037zbMath1252.68140OpenAlexW2156187051MaRDI QIDQ690449
Publication date: 27 November 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.07.037
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Capacitated max-batching with interval graph compatibilities ⋮ Improved bounds for randomized preemptive online matching ⋮ Max-coloring paths: tight bounds and extensions ⋮ Clique clustering yields a PTAS for max-coloring interval graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A coloring problem for weighted graphs
- On the max-weight edge coloring problem
- An improved algorithm for online coloring of intervals with bandwidth
- Time slot scheduling of compatible jobs
- Approximation algorithm for minimizing total latency in machine scheduling with deliveries
- A note on first-fit coloring of interval graphs
- Approximating the max-edge-coloring problem
- Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
- Weighted coloring: further complexity and approximability results
- An on-line graph coloring algorithm with sublinear performance ratio
- Scheduling a batching machine
- Geometric algorithms and combinatorial optimization.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Coloring interval graphs with First-Fit
- Improved approximation algorithms for the max edge-coloring problem
- Batch processing with interval graph compatibilities between tasks
- Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
- Approximating interval coloring and max-coloring in chordal graphs
- Batch Coloring Flat Graphs and Thin
- Max-Coloring Paths: Tight Bounds and Extensions
- On-line and first fit colorings of graphs
- The Linearity of First-Fit Coloring of Interval Graphs
- On some packing problem related to dynamic storage allocation
- Automata, Languages and Programming
- Automata, Languages and Programming
- Approximation and Online Algorithms
- 25 pretty graph colouring problems
