Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
DOI10.1007/978-3-642-22006-7_16zbMATH Open1332.68090OpenAlexW3214761MaRDI QIDQ3012804FDOQ3012804
Authors: 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
Recommendations
- Clique clustering yields a PTAS for max-coloring interval graphs
- The maximum clique problem in multiple interval graphs (extended abstract)
- The maximum clique problem in multiple interval graphs
- Approximability and inapproximability for maximum \(k\)-edge-colored clustering problem
- Graph clustering via generalized colorings
- Coloring the Maximal Cliques of Graphs
- A 0.3622-approximation algorithm for the maximum \(k\)-edge-colored clustering problem
- Clique partitioning of interval graphs with submodular costs on the cliques
- Improved approximations for the max \(k\)-colored clustering problem
- Maximum colorful cliques in vertex-colored graphs
Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Geometric algorithms and combinatorial optimization
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- A coloring problem for weighted graphs
- Approximation schemes for covering and packing problems in image processing and VLSI
- Latency Constrained Aggregation in Sensor Networks
- Zero knowledge and the chromatic number
- Batch processing with interval graph compatibilities between tasks
- Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
- Weighted coloring: further complexity and approximability results
- Max-coloring and online coloring with bandwidths on interval graphs
- Bounded Max-colorings of Graphs
- On the Max Coloring Problem
- Title not available (Why is that?)
- Batch Coloring Flat Graphs and Thin
- Automata, Languages and Programming
- Max-coloring paths: tight bounds and extensions
- Capacitated max-batching with interval graph compatibilities
Cited In (10)
- On the 12-representability of induced subgraphs of a grid graph
- On the max coloring problem
- Clique partitioning with value-monotone submodular cost
- Saving colors and max coloring: some fixed-parameter tractability results
- Clique clustering yields a PTAS for max-coloring interval graphs
- Capacitated max-batching with interval graph compatibilities
- Some approximation algorithms for the clique partition problem in weighted interval graphs
- Capacitated max-batching with interval graph compatibilities
- Bounded max-colorings of graphs
- Saving colors and max coloring: some fixed-parameter tractability results
This page was built for publication: Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012804)
