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},
     mrnumber = {1436181},
     zbl = {0881.90123},
     language = {en},
     url = {http://www.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
SP  - 45
EP  - 66
VL  - 31
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/RO_1997__31_1_45_0/
LA  - en
ID  - RO_1997__31_1_45_0
ER  - 
%0 Journal Article
%A Jansen, Klaus
%A Scheffler, Petra
%A Woeginger, Gerhard
%T The disjoint cliques problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 1997
%P 45-66
%V 31
%N 1
%I EDP-Sciences
%U http://www.numdam.org/item/RO_1997__31_1_45_0/
%G en
%F RO_1997__31_1_45_0
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://www.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 | Zbl

[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 | Zbl

[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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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