Clique clustering yields a PTAS for max-coloring interval graphs

DOI10.1007/s00453-017-0362-9zbMath1391.68060OpenAlexW2748900204MaRDI QIDQ722535

Tim Nonner

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

zbMATH Keywords

combinatorial optimizationapproximation schemesgraph algorithmsapproximation algorithmsinterval graphs

Mathematics Subject Classification ID

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