nach oben

Journal of Scheduling

Erschienen in:

18.12.2018

Inductive \(k\)-independent graphs and c-colorable subgraphs in scheduling: a review

verfasst von: Matthias Bentert, René van Bevern, Rolf Niedermeier

Erschienen in: Journal of Scheduling | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Inductive \(k\)-independent graphs generalize chordal graphs and have recently been advocated in the context of interference-avoiding wireless communication scheduling. The NP-hard problem of finding maximum-weight induced c-colorable subgraphs, which is a generalization of finding maximum independent sets, naturally occurs when selecting \(c\) sets of pairwise non-conflicting jobs (modeled as graph vertices). We investigate the parameterized complexity of this problem on inductive \(k\)-independent graphs. We show that the Maximum Independent Set problem is W[1]-hard even on 2-simplicial 3-minoes—a subclass of inductive 2-independent graphs. In contrast, we prove that the more general Max-Weightc-Colorable Subgraph problem is fixed-parameter tractable on edge-wise unions of cluster and chordal graphs, which are 2-simplicial. In both cases, the parameter is the solution size. Aside from this, we survey other graph classes between inductive \(1\)-independent and inductive \(2\)-independent graphs with applications in scheduling.

Vorheriger Artikel Journal of scheduling (2019)

Nächster Artikel A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Ásgeirsson et al. (2017) interested in maximum-weight unions of c independent sets. In the graph theory literature, the problem is known as Max-Weight\(c\)-Colorable Subgraph; we prefer to stick to the established graph theory notion.

We are not aware that \(A\bowtie B\) or an alike notation has been used before. Rather, previous work has been coming up with ad hoc names for the classes \(A\bowtie B\) for various \(A\) and \(B\), often referring to one and the same class by several names.

Akcoglu, K., Aspnes, J., DasGupta, B., & Kao, M. Y. (2002). Opportunity-cost algorithms for combinatorial auctions. In Applied optimization 74: Computational methods in decision-making, economics and finance (pp. 455–479). Dordrecht: Kluwer. https://doi.org/10.1007/978-1-4757-3613-7_23

Alon, N., Yuster, R., & Zwick, U. (1995). Color-coding. Journal of the ACM, 42(4), 844–856. https://doi.org/10.1145/210332.210337.CrossRef

Arkin, E. M., & Silverberg, E. B. (1987). Scheduling jobs with fixed start and end times. Discrete Applied Mathematics, 18(1), 1–8. https://doi.org/10.1016/0166-218X(87)90037-0.CrossRef

Ásgeirsson, E. I., Halldórsson, M. M., & Tonoyan, T. (2017). Universal framework for wireless scheduling problems. In 44th international colloquium on automata, languages, and programming, ICALP, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (pp 129:1–129:15). https://doi.org/10.4230/LIPIcs.ICALP.2017.129.

Baker, B. S., & Coffman, E. G. (1996). Mutual exclusion scheduling. Theoretical Computer Science, 162(2), 225–243. https://doi.org/10.1016/0304-3975(96)00031-X.CrossRef

Bansal, N., Blum, A., & Chawla, S. (2004). Correlation clustering. Machine Learning, 56(1), 89–113. https://doi.org/10.1023/B:MACH.0000033116.57574.95.CrossRef

van Bevern, R., Komusiewicz, C., & Sorge, M. (2017). A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experiments. Networks, 70(3), 262–278. https://doi.org/10.1002/net.21742 (WARP 2 special issue).

van Bevern, R., Mnich, M., Niedermeier, R., & Weller, M. (2015). Interval scheduling and colorful independent sets. Journal of Scheduling, 18, 449–469. https://doi.org/10.1007/s10951-014-0398-5.CrossRef

Birand, B., Chudnovsky, M., Ries, B., Seymour, P., Zussman, G., & Zwols, Y. (2012). Analyzing the performance of greedy maximal scheduling via local pooling and graph theory. IEEE/ACM Transactions on Networks, 20(1), 163–176. https://doi.org/10.1109/TNET.2011.2157831.CrossRef

Blair, J. R. S., & Peyton, B. (1993). An introduction to chordal graphs and clique trees. In Graph theory and sparse matrix computation, IMA volumes in mathematics and its applications (vol. 56, pp 1–29). Berlin: Springer. https://doi.org/10.1007/978-1-4613-8369-7_1.

Booth, K. S., & Lueker, G. S. (1976). Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 13(3), 335–379. https://doi.org/10.1016/S0022-0000(76)80045-1.CrossRef

Corneil, D. G., Olariu, S., & Stewart, L. (2009). The LBFS structure and recognition of interval graphs. SIAM Journal on Discrete Mathematics, 23(4), 1905–1953.CrossRef

Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., et al. (2015). Parameterized algorithms. Berlin: Springer. https://doi.org/10.1007/978-3-319-21275-3.CrossRef

Dirac, G. A. (1961). On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 25(1), 71–76. https://doi.org/10.1007/BF02992776.CrossRef

Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity. Berlin: Springer. https://doi.org/10.1007/978-1-4471-5559-1.CrossRef

Faenza, Y., Oriolo, G., & Stauffer, G. (2011). An algorithmic decomposition of claw-free graphs leading to an \(O(n^3)\)-algorithm for the weighted stable set problem. In Proceedings of the 22nd ACM–SIAM symposium on discrete algorithms (SODA’11) (pp. 630–646). Philadelphia: SIAM. https://doi.org/10.1137/1.9781611973082.49.

Fellows, M. R., Hermelin, D., Rosamond, F., & Vialette, S. (2009). On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1), 53–61. https://doi.org/10.1016/j.tcs.2008.09.065.CrossRef

Fellows, M. R., Jansen, B. M. P., & Rosamond, F. A. (2013). Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. European Journal of Combinatorics, 34(3), 541–566. https://doi.org/10.1016/j.ejc.2012.04.008.CrossRef

Flum, J., & Grohe, M. (2006). Parameterized complexity theory. Berlin: Springer. https://doi.org/10.1007/3-540-29953-X.CrossRef

Frank, A. (1975). Some polynomial algorithms for certain graphs and hypergraphs. In Proceedings of the 5th British combinatorial conference, congressus numerantium (vol. XV, pp. 211–226).

Gardi, F. (2009). Mutual exclusion scheduling with interval graphs or related classes, Part I. Discrete Applied Mathematics, 157(1), 19–35. https://doi.org/10.1016/j.dam.2008.04.016.CrossRef

Gaur, D. R., & Krishnamurti, R. (2003). Scheduling intervals using independent sets in claw-free graphs. In Proceedings of the international conference on computational science and its applications (ICCSA 2003) (pp. 254–262). Berlin: Springer. https://doi.org/10.1007/3-540-44839-X_28.

Gyárfás, A., & West, D. (1995). Multitrack interval graphs. Congressus Numerantium, 109, 109–116.

Halldórsson, M. M. (2016). Invited paper: Models for wireless algorithms. In Proceedings of the 14th international symposium on modeling and optimization in mobile, ad hoc, and wireless networks (WiOpt’16) (pp. 377–381). New York: IEEE. https://doi.org/10.1109/WIOPT.2016.7492945.

Halldórsson, M. M., & Karlsson, R. K. (2006). Strip graphs: Recognition and scheduling. In Proceedings of the 32nd international workshop on graph-theoretic concepts in computer science (WG’06), Lecture notes in computer science (vol. 4271, pp. 137–146). Berlin: Springer. https://doi.org/10.1007/11917496_13.

Halldórsson, M. M., & Tonoyan, T. (2015). How well can graphs represent wireless interference? In Proceedings of the 47th annual ACM symposium on theory of computing (STOC’15) (pp. 635–644). New York: ACM. https://doi.org/10.1145/2746539.2746585.

Höhn, W., König, F. G., Möhring, R. H., & Lübbecke, M. E. (2011). Integrated sequencing and scheduling in coil coating. Management Science, 57(4), 647–666. https://doi.org/10.1287/mnsc.1100.1302.CrossRef

Jamison, R. E., & Mulder, H. M. (2000). Tolerance intersection graphs on binary trees with constant tolerance 3. Discrete Mathematics, 215(1), 115–131. https://doi.org/10.1016/S0012-365X(99)00231-9.CrossRef

Jiang, M. (2010). On the parameterized complexity of some optimization problems related to multiple-interval graphs. Theoretical Computer Science, 411(49), 4253–4262. https://doi.org/10.1016/j.tcs.2010.09.001.CrossRef

Jiang, M. (2013). Recognizing \(d\)-interval graphs and d-track interval graphs. Algorithmica, 66(3), 541–563. https://doi.org/10.1007/s00453-012-9651-5.CrossRef

Kammer, F., Tholey, T., & Voepel, H. (2010). Approximation algorithms for intersection graphs. In Proceedings of the 13th international workshop on approximation algorithms for combinatorial optimization problems and 14th workshop on randomized techniques in computation: Algorithms and techniques (APPROX’10 and RANDOM’10), Lecture notes in computer science (vol. 6302, pp. 260–273). Berlin: Springer. https://doi.org/10.1007/978-3-642-15369-3_20.

Kolen, A. W. J., Lenstra, J. K., Papadimitriou, C. H., & Spieksma, F. C. R. (2007). Interval scheduling: A survey. Naval Research Logistics, 54(5), 530–543. https://doi.org/10.1002/nav.20231.CrossRef

Komusiewicz, C., & Niedermeier, R. (2012). New races in parameterized algorithmics. In Proceedings of the 37th international symposium on mathematical foundations of computer science (MFCS’12), Lecture notes in computer science (vol. 7464, pp. 19–30). Berlin: Springer. https://doi.org/10.1007/978-3-642-32589-2_2.

Köse, A., Evirgen, N., Gökcesu, H., Gökcesu, K., & Médard, M. (2017). Nearly optimal scheduling of wireless ad hoc networks in polynomial time. Available on arXiv:1712.00658.

Köse, A., & Médard, M. (2017). Scheduling wireless ad hoc networks in polynomial time using claw-free conflict graphs. In Proceedings of the 28th IEEE annual international symposium on personal, indoor, and mobile radio communications (PIMRC’17) (pp. 1–7). New York: IEEE. https://doi.org/10.1109/PIMRC.2017.8292404.

Metelsky, Y., & Tyshkevich, R. (2003). Line graphs of Helly hypergraphs. SIAM Journal on Discrete Mathematics, 16(3), 438–448. https://doi.org/10.1137/S089548019936521X.CrossRef

Misra, N., Panolan, F., Rai, A., Raman, V., & Saurabh, S. (2013). Parameterized algorithms for max colorable induced subgraph problem on perfect graphs. In Proceedings of the 39th international workshop on graph-theoretic concepts in computer science (WG’13) (pp. 370–381). Berlin: Springer. https://doi.org/10.1007/978-3-642-45043-3_32.

Mnich, M., & van Bevern, R. (2018). Parameterized complexity of machine scheduling: 15 open problems. Computers and Operations Research, 100, 254–261. https://doi.org/10.1016/j.cor.2018.07.020.CrossRef

Nakajima, K., & Hakimi, S. L. (1982). Complexity results for scheduling tasks with discrete starting times. Journal of Algorithms, 3(4), 344–361. https://doi.org/10.1016/0196-6774(82)90030-X.CrossRef

Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford: Oxford University Press. https://doi.org/10.1093/acprof:oso/9780198566076.001.0001.CrossRef

Niedermeier, R. (2010). Reflections on multivariate algorithmics and problem parameterization. In Proceedings of the 27th international symposium on theoretical aspects of computer science (STACS’10), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, LIPIcs (vol. 5, pp. 17–32). https://doi.org/10.4230/LIPIcs.STACS.2010.2495.

Papadimitriou, C., & Yannakakis, M. (1979). Scheduling interval-ordered tasks. SIAM Journal on Computing, 8(3), 405–409. https://doi.org/10.1137/0208031.CrossRef

Rose, D. J., Tarjan, R. E., & Lueker, G. S. (1976). Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5(2), 266–283. https://doi.org/10.1137/0205021.CrossRef

Shamir, R., Sharan, R., & Tsur, D. (2004). Cluster graph modification problems. Discrete Applied Mathematics, 144(1–2), 173–182. https://doi.org/10.1016/j.dam.2004.01.007.CrossRef

Sung, S. C., & Vlach, M. (2005). Maximizing weighted number of just-in-time jobs on unrelated parallel machines. Journal of Scheduling, 8(5), 453–460. https://doi.org/10.1007/s10951-005-2863-7.CrossRef

Wegner, G. (1961). Eigenschaften der Nerven homologisch-einfacher Familien im \(R^n\). Ph.D. Thesis, Universität Göttingen.

West, D. B., & Shmoys, D. B. (1984). Recognizing graphs with fixed interval number is NP-complete. Discrete Applied Mathematics, 8(3), 295–305. https://doi.org/10.1016/0166-218X(84)90127-6.CrossRef

Yannakakis, M., & Gavril, F. (1987). The maximum \(k\)-colorable subgraph problem for chordal graphs. Information Processing Letters, 24(2), 133–137. https://doi.org/10.1016/0020-0190(87)90107-4.CrossRef

Ye, Y., & Borodin, A. (2012). Elimination graphs. ACM Transactions on Algorithms, 8(2), 14:1–14:23. https://doi.org/10.1145/2151171.2151177.CrossRef

Titel: Inductive -independent graphs and c-colorable subgraphs in scheduling: a review
verfasst von: Matthias Bentert
René van Bevern
Rolf Niedermeier
Publikationsdatum: 18.12.2018
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 1/2019
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-018-0595-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2019

No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths

An efficient train scheduling algorithm on a single-track railway system

Journal of scheduling (2019)

Scheduling and rescheduling elective patients in operating rooms to minimise the percentage of tardy patients

The venue management problem: setting staffing levels, shifts and shift schedules at concession stands

A polynomial-time approximation scheme for the airplane refueling problem