×

Selection of programme slots of television channels for giving advertisement: a graph theoretic approach. (English) Zbl 1115.05087

Summary: The present paper aims at developing a linear time algorithm to find a solution to the ‘maximum weight 1 colouring’ problem for an interval graph with interval weight. This algorithm has been applied to solve the problem that involves selecting different programme slots telecast on different television channels in a day so as to reach the maximum number of viewers. It is shown that all programmes of all television channels can be modelled as a weighted interval graph with interval numbers as weights. The programme slots are taken as the vertices of the graph and if the time durations of two programme slots have non-empty intersection, the corresponding vertices are considered to be connected by an edge. The number of viewers of a programme is taken as the weight of the vertex. In reality, the number of viewers of a programme is not a fixed one; generally, it lies in an interval. Thus, the weights of the vertices are taken as interval numbers. We assume that a company sets the objective of selecting the popular programme in different channels so as to make its commercial advertisement reach the maximum number of viewers. However, the constraint imposed is that all selected programmes are mutually exclusive in respect of time scheduling. The objective of the paper is, therefore, to help the companies to select the programme slots, which are mutually exclusive with respect to the time schedule of telecasting time, in such a way that the total number of viewers of the selected programme slots rises to the optimum level. It is shown that the solution of this problem is obtained by solving the maximum weight colouring problem on an interval graph. An algorithm is designed to solve this optimization problem using \(O(n)\) time, where \(n\) represents the total number of programmes of all channels.

MSC:

05C90 Applications of graph theory
05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
68W05 Nonnumerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balas, E.; Xue, J., Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs, SIAM J. Comput., 20, 209-221 (1991) · Zbl 0722.68086
[2] Bodlaender, H.; Kloks, Ton, A simple linear time algorithm for triangulating three-colored graphs, J. Algorithms, 15, 160-172 (1993) · Zbl 0785.68042
[3] Boyar, J. F.; Karloff, H. J., Coloring planar graphs in parallel, J. Algorithms, 8, 470-479 (1987) · Zbl 0636.68088
[4] Broersma, H.; Kloks, T.; Kratsch, D.; Müller, H., Independents sets in asteroidal triple free graphs, SIAM J. Discrete Math., 12, 276-287 (1999) · Zbl 0918.68072
[5] Chankong, V.; Haimes, Y. Y., Multiobjective Decision Making Theory and Methodology, Series in System Science and Engineering, vol. 8 (1983), North-Holland: North-Holland New York · Zbl 0525.90085
[6] Chan, T. M., A note on maximum independent sets in rectangle intersection graphs, Inform. Process. Lett., 89, 19-23 (2004) · Zbl 1178.68674
[7] Chanas, S.; Delgado, M.; Verdgay, J. L.; Vila, M. A., Ranking fuzzy interval numbers in the setting of random sets, Inform. Sci., 69, 3, 201-217 (1993) · Zbl 0778.94013
[8] Chanas, S.; Zielinski, P., Ranking fuzzy interval numbers in the setting of random sets-further results, Inform. Sci., 117, 3, 191-200 (1999) · Zbl 0995.94043
[9] L. Chen, Logarithmic time NC algorithms for comparability graphs and circle graphs, in: LNCS, vol. 497, ICCI’91, 1991, pp. 383-394.; L. Chen, Logarithmic time NC algorithms for comparability graphs and circle graphs, in: LNCS, vol. 497, ICCI’91, 1991, pp. 383-394.
[10] Chen, L., Optimal parallel time bounds for the maximum clique problem on intervals, Inform. Process. Lett., 42, 197-201 (1992) · Zbl 0772.68049
[11] Churchman, C. W., The Systems Approach (1968), Dell: Dell New York · Zbl 0153.48902
[12] K. Disk, T. Hagerup, W. Rytter, Optimal parallel algorithms for the recognition and colouring outerplanar graphs, in: LNCS, vol. 379, Mathematical Foundations of Computer Science, 1989, pp. 207-217.; K. Disk, T. Hagerup, W. Rytter, Optimal parallel algorithms for the recognition and colouring outerplanar graphs, in: LNCS, vol. 379, Mathematical Foundations of Computer Science, 1989, pp. 207-217. · Zbl 0755.68059
[13] Dubois, D.; Prade, H., Fuzzy Sets and Systems: Theory and Applications (1980), Academic Press: Academic Press New York · Zbl 0444.94049
[14] Dubois, D.; Prade, H., Ranking fuzzy numbers in the setting of possibility theory, Inform. Sci., 30, 183-224 (1983) · Zbl 0569.94031
[15] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[16] Gupta, U. I.; Lee, D. T.; Leung, J. Y.-T., Efficient algorithms for interval graphs and circular-arc graphs, Network, 12, 459-467 (1982) · Zbl 0493.68066
[17] Ganesan, K.; Veeramani, P., On arithmetic operations of interval numbers, Int. J. Uncertainty, Fuzzyness Knowledge Based Syst., 13, 6, 619-631 (2005) · Zbl 1084.65046
[18] Gardi, F., Mutual exclusion scheduling with interval graphs or related classed: complexity and algorithms, 4OR: A Quartely J. Oper. Res., 4, 1, 87-90 (2006) · Zbl 1107.05033
[19] Gyarfas, A.; Lehel, J., Covering and coloring problems for relatives of intervals, Dist. Math., 55, 167-180 (1985) · Zbl 0569.05020
[20] Halldorsson, M. M., A still better performance guarantee for approximate graph coloring, Inform. Process. Lett., 45, 19-23 (1993) · Zbl 0768.68043
[21] Ho, C. W.; Lee, R. C.T., Efficient parallel algorithms for finding maximal cliques, clique trees and minimum coloring on chordal graphs, Inform. Process. Lett., 28, 301-309 (1988) · Zbl 0658.68079
[22] Hota, M.; Pal, M.; Pal, T. K., An efficient algorithm to generate all maximal independent sets on trapezoid graphs, Int. J. Comput. Math., 70, 587-599 (1999) · Zbl 0923.68094
[23] Hota, M.; Pal, M.; Pal, T. K., An efficient algorithm for finding a maximum weight \(k\)-independent set on trapezoid graphs, Comput. Optimiz. Appl., 18, 49-62 (2001) · Zbl 0963.90065
[24] Jansen, K., The mutual exclusion scheduling problem for permutation and comparability graphs, Inform. Comput., 180, 2, 71-81 (2003) · Zbl 1054.68019
[25] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thacher, J. W., Complexity of Computer Computations (1972), Plenum Press) · Zbl 0366.68041
[26] Lin, R.; Olariu, S., Fast parallel algorithms for cographs, (LNCS, vol. 472 (1990), FST & TCS), 176-189 · Zbl 0733.68063
[27] Manacher, G. L.; Mankus, T. A., A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone, Networks, 39, 2, 68-72 (2002) · Zbl 0994.05142
[28] Naor, J.; Naor, M.; Schaffer, A. A., Fast parallel algorithms for chordal graphs, SIAM J. Comput., 18, 327-349 (1989) · Zbl 0672.05055
[29] Roberts, F. S., Graph Theory and its Application to Problems of Society (1978), SIAM: SIAM Philadelphia, PA
[30] Olariu, S., An optimal greedy heuristic to color interval graphs, Inform. Process. Lett., 37, 21-25 (1991) · Zbl 0711.68083
[31] Pal, M.; Bhattacharjee, G. P., An optimal parallel algorithm to color an interval graph, Parallel Process. Lett., 6, 439-449 (1996)
[32] Pal, M., A parallel algorithm to generate all maximal independent sets on permutation graphs, Int. J. Comput. Math., 67, 261-274 (1998) · Zbl 0896.68077
[33] Rajeani, P., Optimal parallel 3-coloring algorithm for rooted and its applications, Inform. Process. Lett., 41, 153-156 (1992)
[34] Saha, A.; Pal, M.; Pal, T. K., Maximum weight \(k\)-independent set problem on permutation graphs, Int. J. Comput. Math., 80, 12, 1477-1487 (2003) · Zbl 1100.68597
[35] Saha, A.; Pal, M.; Pal, T. K., An efficient PRAM algorithm for maximum-weight independent set on permutation graphs, J. Appl. Math. Comput., 19, 1+2, 77-92 (2005) · Zbl 1082.05089
[36] Sengupta, A.; Pal, T. K., Theory and methodology on comparing interval numbers, Eur. J. Oper. Res., 127, 28-43 (2000) · Zbl 0991.90080
[37] M. Slusarek, A coloring algorithm for interval graphs, in: LNCS, vol. 379, Mathematical Foundations of Computer Science, 1989, pp. 471-480.; M. Slusarek, A coloring algorithm for interval graphs, in: LNCS, vol. 379, Mathematical Foundations of Computer Science, 1989, pp. 471-480. · Zbl 0755.68112
[38] Vishwanathan, S., Randomized online graph coloring, J. Algorithms, 13, 657-669 (1992) · Zbl 0768.68185
[39] Yannakakis, M.; Gavril, F., The maximum \(k\)-colorable subgraph problem for chordal graphs, Inform. Process. Lett., 24, 133-137 (1987) · Zbl 0653.68070
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.