Clique partitioning of interval graphs with submodular costs on the cliques

DOI10.1051/ro:2007024zbMath1213.90214OpenAlexW2157164380MaRDI QIDQ3004202

Vincent Jost, Dion C. Gijswijt, Maurice Queyranne

Publication date: 1 June 2011

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/105374

zbMATH Keywords

interval graphssubmodular functionsbipartite matchingscircular arc graphsSplit graphspartition into cliquespartial \(q\)-coloringbatch-schedulingMax-coloringchromatic entropyprobabilist coloring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Max point-tolerance graphs ⋮ A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs ⋮ Capacitated max-batching with interval graph compatibilities ⋮ A weakly robust PTAS for minimum clique partition in unit disk graphs ⋮ Minimum Entropy Combinatorial Optimization Problems ⋮ Minimum entropy combinatorial optimization problems ⋮ Minimizing total busy time in parallel scheduling with application to optical networks ⋮ “Rent-or-Buy” Scheduling and Cost Coloring Problems ⋮ Covering and packing of triangles intersecting a straight line ⋮ Latency Constrained Aggregation in Chain Networks Admits a PTAS ⋮ APPROXIMATING THE JOINT REPLENISHMENT PROBLEM WITH DEADLINES ⋮ Clique partitioning with value-monotone submodular cost ⋮ Interval scheduling with economies of scale

Cites Work

• Unnamed Item
• Unnamed Item
• A coloring problem for weighted graphs
• Probabilistic graph-coloring in bipartite and split graphs
• A min-max relation for the partial q-colourings of a graph. II: Box perfection
• Time slot scheduling of compatible jobs
• The maximum k-colorable subgraph problem for chordal graphs
• Dynamic scheduling on a single batch processing machine with split compatibility graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Batch processing with interval graph compatibilities between tasks
• Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP
• Source coding and graph entropies
• Theoretical Computer Science
• Latency Constrained Aggregation in Sensor Networks
• Algorithms and Computation

This page was built for publication: Clique partitioning of interval graphs with submodular costs on the cliques