Clique partitioning of interval graphs with submodular costs on the cliques
Dion Gijswijt; Vincent Jost; Maurice Queyranne
RAIRO - Operations Research (2007)
- Volume: 41, Issue: 3, page 275-287
- ISSN: 0399-0559
Access Full Article
topAbstract
topHow to cite
topGijswijt, Dion, Jost, Vincent, and Queyranne, Maurice. "Clique partitioning of interval graphs with submodular costs on the cliques." RAIRO - Operations Research 41.3 (2007): 275-287. <http://eudml.org/doc/250125>.
@article{Gijswijt2007,
abstract = {
Given a graph G = (V,E) and a “cost function” $f: 2^V\rightarrow\mathbb\{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.
},
author = {Gijswijt, Dion, Jost, Vincent, Queyranne, Maurice},
journal = {RAIRO - Operations Research},
keywords = {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; partition into cliques; interval graphs; circular arc graphs; probabilist coloring; chromatic entropy; partial -coloring; batch-scheduling; submodular functions; bipartite matchings},
language = {eng},
month = {8},
number = {3},
pages = {275-287},
publisher = {EDP Sciences},
title = {Clique partitioning of interval graphs with submodular costs on the cliques},
url = {http://eudml.org/doc/250125},
volume = {41},
year = {2007},
}
TY - JOUR
AU - Gijswijt, Dion
AU - Jost, Vincent
AU - Queyranne, Maurice
TI - Clique partitioning of interval graphs with submodular costs on the cliques
JO - RAIRO - Operations Research
DA - 2007/8//
PB - EDP Sciences
VL - 41
IS - 3
SP - 275
EP - 287
AB -
Given a graph G = (V,E) and a “cost function” $f: 2^V\rightarrow\mathbb{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.
LA - eng
KW - 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; partition into cliques; interval graphs; circular arc graphs; probabilist coloring; chromatic entropy; partial -coloring; batch-scheduling; submodular functions; bipartite matchings
UR - http://eudml.org/doc/250125
ER -
References
top- N. Alon and A. Orlitsky, Source coding and graph entropies. IEEE Trans Inform Theory42 (1996) 1329–1339.
- L. Becchetti, P. Korteweg, A. Marchetti-Spaccamela, M. Skutella, L. Stougie and A. Vitaletti, Latency contrained aggregation in sensor networks. Workshop of Combinatorial Optimization, Aussois (2006).
- M. Boudhar, Dynamic Scheduling on a Single Batch Processing Machine with Split Compatibility Graphs. J. Math. Model. Algorithms2 (2003) 17–35.
- P. Brucker and S. Knust, Complexity results of scheduling problems. www.mathematik.uni-osnabrueck.de/research/OR/class/
- K. Cameron, A min-max relation for the partial q-colourings of a graph. II: Box perfection. Discrete Math.74 (1989) 15–27.
- J. Cardinal, S. Fiorini and G. Joret, Minimum entropy coloring. ISAAC, Lect. Notes Comput. Sci.3827 (2005) 819–828.
- F. Della Croce, B. Escoffier, C. Murat and V. Th. Paschos, Probabilistic coloring of bipartite and split graphs. ICCSA'05, Lect. Notes Comput. Sci.3483 (2005) 202–211 (see also Cahiers du Lamsade No. 218).
- M. Demange, D. de Werra, J. Monnot and V.T. Paschos, Time slot scheduling of compatible jobs. Cahiers du Lamsade No. 182, (2001), (accepted in J. Scheduling).
- E. Desgrippes, Coordination entre la production et la distribution dans une chaîne logistique. Laboratoire GILCO - Grenoble (2005).
- J. Edmonds and R. Giles, A min-max relation for submodular functions on graphs. Ann. Discrete Math.1 (1977) 185–204.
- B. Escoffier, J. Monnot and V. Th. Paschos, Weighted Coloring: Further Complexity and Approximability Results. ICTCS (2005) 205–214.
- G. Finke, V. Jost, M. Queyranne and A. Sebő, Batch processing with interval graph compatibilities between tasks. Cahier du Leibniz No. 108, Laboratoire Leibniz-IMAG, Grenoble (2004) (accepted in Discrete Appl. Math.).
- M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press (1980).
- D.J. Guan and Xuding Zhu, A Coloring Problem for Weighted Graphs. Inf. Process. Lett.61 (1997) 77–81.
- Y.T. Herer and M. Penn, Characterizations of natural submodular graphs: A polynomially solvable class of the TSP. Proc. Am. Math. Soc.123 (1995) 673–679.
- V. Jost, Ordonnancement chromatique: Polyèdres, Complexité et Classification. Ph.D. thesis, Laboratoire Leibniz-IMAG - UJF - Grenoble (2006).
- A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency. Springer (2003).
- M. Yannakakis and F. Gavril, The maximum k-colorable subgraph problem for chordal graphs. Inf. Process. Lett.24 (1987) 133–137.
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.