University of AmsterdamUniversity of AmsterdamUvA

  • Terms of use
  • Contact

UvA-DARE (Digital Academic Repository)

  • Home
  • Advanced Search
  • Browse
  • My selection

Search UvA-DARE

Author
D.C. Gijswijt
V. Jost
M. Queyranne
Year
2007
Title
Clique partitioning of interval graphs with submodular costs on the cliques.
Journal
RAIRO - Operations Research
Volume | Issue number
41 | 3
Pages (from-to)
275-288
Document type
Article
Faculty
Faculty of Science (FNWI)
Institute
Korteweg-de Vries Institute for Mathematics (KdVI)
Abstract
Abstract:
Given a graph G = (V,E) and a "cost function" f:2^V -> R (provided by an oracle), the problem [PCliqW] consists in finding a partition into cliques of V(G) 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 G is an interval graph and f 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 in co-interval graphs such as max-coloring, "Greene-Kleitman's dual", probabilist coloring and chromatic entropy. In the last two cases, this is the first polytime algorithm for co-interval graphs. In contrast, NP-hardness of related problems is discussed. We also describe an ILP formulation for [PCliqW] which gives a common polyhedral framework to express min-max relations such as \overline{\chi}=\alpha for perfect graphs and the polymatroid intersection theorem. This approach allows to provide a min-max formula for [PCliqW] if G is the line-graph of a bipartite graph and f is submodular. However, this approach fails to provide a min-max relation for [PCliqW] if G is an interval graphs and f is value-polymatroidal.

Key words: Partition into cliques, Interval graphs, Circular arc graphs, Max-coloring, Probabilist coloring, Chromatic entropy, Partial q-coloring, Batch-scheduling, Submodular functions, Bipartite matchings, Split graphs

URL
go to publisher's site
Link
Link
Language
Undefined/Unknown
Permalink
http://hdl.handle.net/11245/1.276164

Disclaimer/Complaints regulations

If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.

PrintPrint this pageShareShare via emailShare on facebookShare on linkedinShare on twitter
  • University library
  • About UvA-DARE
  • Disclaimer
Copyright UvA 2014