On the max coloring problem
DOI10.1016/J.TCS.2012.07.037zbMATH Open1252.68140OpenAlexW2156187051MaRDI QIDQ690449FDOQ690449
Authors: Leah Epstein, Asaf Levin 
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- Scheduling a batching machine
- Geometric algorithms and combinatorial optimization.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On some packing problem related to dynamic storage allocation
- Title not available (Why is that?)
- Coloring interval graphs with First-Fit
- The Linearity of First-Fit Coloring of Interval Graphs
- A coloring problem for weighted graphs
- 25 pretty graph colouring problems
- On-line and first fit colorings of graphs
- Batch processing with interval graph compatibilities between tasks
- Automata, Languages and Programming
- Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
- Weighted coloring: further complexity and approximability results
- Improved approximation algorithms for the max edge-coloring problem
- On the max-weight edge coloring problem
- Approximating the max-edge-coloring problem
- An on-line graph coloring algorithm with sublinear performance ratio
- Title not available (Why is that?)
- Batch Coloring Flat Graphs and Thin
- Automata, Languages and Programming
- Time slot scheduling of compatible jobs
- A note on first-fit coloring of interval graphs
- Approximation and Online Algorithms
- Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
- Approximating interval coloring and max-coloring in chordal graphs
- Max-coloring paths: tight bounds and extensions
- An improved algorithm for online coloring of intervals with bandwidth
- Approximation algorithm for minimizing total latency in machine scheduling with deliveries
Cited In (10)
- On the Max Coloring Problem
- Improved bounds for randomized preemptive online matching
- Clique clustering yields a PTAS for max-coloring interval graphs
- Capacitated max-batching with interval graph compatibilities
- Maximum number of colors: C-coloring and related problems
- Max-coloring paths: tight bounds and extensions
- Approximating interval coloring and max-coloring in chordal graphs
- Maximizing the number of q -colorings
- Maximizing the number of unused colors in the vertex coloring problem
- Automata, Languages and Programming
This page was built for publication: On the max coloring problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q690449)
