Currently displaying 1 – 1 of 1

Showing per page

Order by Relevance | Title | Year of publication

Clique partitioning of interval graphs with submodular costs on the cliques

Dion GijswijtVincent JostMaurice Queyranne — 2007

RAIRO - Operations Research

Given a graph and a “cost function” f : 2 V (provided by an oracle), the problem [PCliqW] consists in finding a partition into cliques of of minimum cost. Here, the cost of a partition is the sum of the costs of the cliques in the partition. We provide a polynomial time dynamic program for the case where is an interval graph and belongs to a subclass of submodular set functions, which we call “value-polymatroidal”. This provides a common solution for various generalizations of the coloring problem...

Page 1

Download Results (CSV)