Clique Clustering Yields a PTAS for max-Coloring Interval Graphs

DOI10.1007/978-3-642-22006-7_16zbMath1332.68090OpenAlexW3214761MaRDI QIDQ3012804

Tim Nonner

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_16

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)

Related Items (7)

Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results ⋮ Capacitated max-batching with interval graph compatibilities ⋮ Bounded max-colorings of graphs ⋮ Saving colors and max coloring: some fixed-parameter tractability results ⋮ On the max coloring problem ⋮ Clique partitioning with value-monotone submodular cost ⋮ On the 12-representability of induced subgraphs of a grid graph

Cites Work

• Unnamed Item
• A coloring problem for weighted graphs
• 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
• Batch processing with interval graph compatibilities between tasks
• Bounded Max-colorings of 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
• Capacitated max -Batching with Interval Graph Compatibilities
• Max-Coloring Paths: Tight Bounds and Extensions
• Approximation schemes for covering and packing problems in image processing and VLSI
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• On the Max Coloring Problem
• 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