Capacitated max-batching with interval graph compatibilities

DOI10.1007/978-3-642-13731-0_18zbMATH Open1284.05217OpenAlexW2152452513MaRDI QIDQ3569889FDOQ3569889

Authors: Tim Nonner 

Publication date: 22 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13731-0_18

Recommendations

• Capacitated max-batching with interval graph compatibilities
• Batch processing with interval graph compatibilities between tasks
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• Clique clustering yields a PTAS for max-coloring interval graphs
• Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (4)

• Clique partitioning with value-monotone submodular cost
• Capacitated max-batching with interval graph compatibilities
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• Bounded max-colorings of graphs

This page was built for publication: Capacitated max-batching with interval graph compatibilities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569889)