The disjoint cliques problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 31 (1997) no. 1, pp. 45-66.
@article{RO_1997__31_1_45_0,
     author = {Jansen, Klaus and Scheffler, Petra and Woeginger, Gerhard},
     title = {The disjoint cliques problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {45--66},
     publisher = {EDP-Sciences},
     volume = {31},
     number = {1},
     year = {1997},
     zbl = {0881.90123},
     mrnumber = {1436181},
     language = {en},
     url = {http://archive.numdam.org/item/RO_1997__31_1_45_0/}
}
TY  - JOUR
AU  - Jansen, Klaus
AU  - Scheffler, Petra
AU  - Woeginger, Gerhard
TI  - The disjoint cliques problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 1997
DA  - 1997///
SP  - 45
EP  - 66
VL  - 31
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/RO_1997__31_1_45_0/
UR  - https://zbmath.org/?q=an%3A0881.90123
UR  - https://www.ams.org/mathscinet-getitem?mr=1436181
LA  - en
ID  - RO_1997__31_1_45_0
ER  - 
Jansen, Klaus; Scheffler, Petra; Woeginger, Gerhard. The disjoint cliques problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 31 (1997) no. 1, pp. 45-66. http://archive.numdam.org/item/RO_1997__31_1_45_0/

[Arn] S. Arnborg, Efficient algorithms for combinatorial problems on graphs with bounded decomposability. A survey, BIT, 1985, 25, pp. 2-23. | MR 785803 | Zbl 0573.68018

[BGLR] M. Bellare, S. Goldwasser, C. Lund and A. Russell, Efficient probabilistically checkable proofs and applications to approximation, 25th ACM Symposium on the Theory of Computing, 1993, pp. 294-304.

[BLW] M. W. Bern, E. L. Lawler and A. L. R. Wong, Linear-time computations of subgraphs of decomposable graphs, Journal of Algorithms, 1987, 8,pp. 216-235. | MR 890873 | Zbl 0618.68058

[Bo1] H. L. Bodlaender, A linear time algorithm for finding tree-decomposition of small treewidth, 25th Symposium on the Theory of Computing, 1993, pp. 226-234. | Zbl 0864.68074

[Bo2] H. L. Bodlaender, A tourist guide through treewidth, Acta Cybernetica, 1993, 11, pp. 1-23. | MR 1268488 | Zbl 0804.68101

[BL] S. Booth and S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. Syst. Sci., 1976, 13, pp. 335-379. | MR 433962 | Zbl 0367.68034

[Br] A. Brandstädt, Special graph classes - a survey. Report SM-DU-199, Universität-Gesamthochschule Duisburg, 1991.

[CPS] D. G. Corneil, Y. Perl and L. K. Stewart, A linear recognition algorithm for cographs, SIAM J. Comput, 1985, 4, pp. 926-934. | MR 807891 | Zbl 0575.68065

[Di] P. F. Dietz, Intersection graph algorithms, Ph. D. thesis, Comput. Sci. Dept., Cornell Univ., Ithaka, NY 1984.

[Fr] A. Frank, On chain and antichain families of a partially ordered set, J. Combinatorial Theory (B), 1980, 29, pp. 176-184. | MR 586432 | Zbl 0443.06003

[GJ] M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. | MR 519066 | Zbl 0411.68039

[Ga] F. Gavril, Algorithms for maximum k-colorings and k-coverings of transitive graphs, Networks, 1987, 17, pp. 465-470. | MR 912032 | Zbl 0642.05021

[Go] M. C. Golumbic, Algorithm graph theory and perfect graphs, Academic Press, New York, 1980. | MR 562306 | Zbl 0541.05054

[Ja] K. Jansen, Scheduling of incompatible jobs on unrelated machines, International Journal of Foundations of Computer Science, 1993, 4, pp. 275-291. | MR 1279494 | Zbl 0799.90066

[LY] C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, 25th ACM Symposium on the Theory of Computing, 1993, pp. 286-293. | MR 1371491 | Zbl 0814.68064

[MV] S. Micali and V. V. Vazirani, An O(√!V!!E!) algorithm for finding maximum matchings in general graphs, in: Proc. 21st Ann. IEEE Symp. Foundations of Computer Science, Long Beach, California, 1980, pp. 17-27.

[RS] N. Robertson and P. Seymour, Graph Minors. II. Algorithmic aspects of tree-width, Journal of Algorithms, 1986, 7, pp. 309-322. | MR 855559 | Zbl 0611.05017

[Sch] P. Scheffler, Die Baumweite von Graphen als Maß für die Kompliziertheit algorithmischer Probleme. Report RMATH-04/89, K-Weierstraß-Institut für Mathematik, Berlin, 1989. | MR 1004243 | Zbl 0684.68061

[YG] M. Yannakakis and F. Gavril, The maximum k-colorable subgraph problem for chordal graphs, Information Processing Letters, 1987, 24, pp. 133-137. | MR 882643 | Zbl 0653.68070