Clique clustering yields a PTAS for max-coloring interval graphs

DOI10.1007/S00453-017-0362-9zbMATH Open1391.68060OpenAlexW2748900204MaRDI QIDQ722535FDOQ722535

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

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

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)

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
• Max-coloring paths: tight bounds and extensions
• Automata, Languages and Programming
• A quasi-PTAS for unsplittable flow on line graphs
• OPTVersusLOADin Dynamic Storage Allocation
• Capacitated max-batching with interval graph compatibilities

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
• Title not available (Why is that?)

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)