Clique clustering yields a PTAS for max-coloring interval graphs

DOI10.1007/S00453-017-0362-9MaRDI QIDQ722535zbMATH OpenOpenAlexFDO

Authors 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 algorithmsapproximation schemesgraph algorithmsinterval graphs

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?)
• OPTVersusLOADin Dynamic Storage Allocation
• A coloring problem for weighted graphs
• A quasi-PTAS for unsplittable flow on line 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

(5)

• On the Max Coloring Problem
• On the max coloring problem
• Capacitated max-batching with interval graph compatibilities
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• scientific article; zbMATH DE number 1588325 (Why is no real title available?)

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 Q722535)