Clique clustering yields a PTAS for max-coloring interval graphs
From MaRDI portal
Publication:722535
DOI10.1007/s00453-017-0362-9zbMath1391.68060OpenAlexW2748900204MaRDI QIDQ722535
Publication date: 26 July 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-017-0362-9
combinatorial optimizationapproximation schemesgraph algorithmsapproximation algorithmsinterval graphs
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Unnamed Item
- A coloring problem for weighted graphs
- Max-coloring paths: tight bounds and extensions
- On the max coloring problem
- Capacitated max-batching with interval graph compatibilities
- Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
- Weighted coloring: further complexity and approximability results
- Geometric algorithms and combinatorial optimization
- Zero knowledge and the chromatic number
- Bounded max-colorings of graphs
- Batch processing with interval graph compatibilities between tasks
- A quasi-PTAS for unsplittable flow on line graphs
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Max-coloring and online coloring with bandwidths on interval graphs
- Batch Coloring Flat Graphs and Thin
- Approximation schemes for covering and packing problems in image processing and VLSI
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- OPTVersusLOADin Dynamic Storage Allocation
- Latency Constrained Aggregation in Sensor Networks
- Automata, Languages and Programming
This page was built for publication: Clique clustering yields a PTAS for max-coloring interval graphs
