Clique Clustering Yields a PTAS for max-Coloring Interval Graphs

DOI10.1007/978-3-642-22006-7_16MaRDI QIDQ3012804zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

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

Cites work

• scientific article; zbMATH DE number 6469191 (Why is no real title available?)
• A coloring problem for weighted graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Automata, Languages and Programming
• Batch Coloring Flat Graphs and Thin
• Batch processing with interval graph compatibilities between tasks
• Bounded Max-colorings of Graphs
• Capacitated max-batching with interval graph compatibilities
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Geometric algorithms and combinatorial optimization
• Latency Constrained Aggregation in Sensor Networks
• Max-coloring and online coloring with bandwidths on interval graphs
• Max-coloring paths: tight bounds and extensions
• On the Max Coloring Problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
• Weighted coloring: further complexity and approximability results
• Zero knowledge and the chromatic number

Cited in

(10)

• On the max coloring problem
• On the 12-representability of induced subgraphs of a grid graph
• 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)