The disjoint cliques problem

Klaus Jansen; Petra Scheffler; Gerhard Woeginger

RAIRO - Operations Research - Recherche Opérationnelle (1997)

  • Volume: 31, Issue: 1, page 45-66
  • ISSN: 0399-0559

How to cite

top

Jansen, Klaus, Scheffler, Petra, and Woeginger, Gerhard. "The disjoint cliques problem." RAIRO - Operations Research - Recherche Opérationnelle 31.1 (1997): 45-66. <http://eudml.org/doc/105140>.

@article{Jansen1997,
author = {Jansen, Klaus, Scheffler, Petra, Woeginger, Gerhard},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {interval graph; cograph; directed path graph; partial -trees; pairwise disjoint cliques; NP-completeness},
language = {eng},
number = {1},
pages = {45-66},
publisher = {EDP-Sciences},
title = {The disjoint cliques problem},
url = {http://eudml.org/doc/105140},
volume = {31},
year = {1997},
}

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
PB - EDP-Sciences
VL - 31
IS - 1
SP - 45
EP - 66
LA - eng
KW - interval graph; cograph; directed path graph; partial -trees; pairwise disjoint cliques; NP-completeness
UR - http://eudml.org/doc/105140
ER -

References

top
  1. [Arn] S. ARNBORG, Efficient algorithms for combinatorial problems on graphs with bounded decomposability. A survey, BIT, 1985, 25, pp. 2-23. Zbl0573.68018MR785803
  2. [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. Zbl1310.68083
  3. [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. Zbl0618.68058MR890873
  4. [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. Zbl0864.68074
  5. [Bo2] H. L. BODLAENDER, A tourist guide through treewidth, Acta Cybernetica, 1993, 11, pp. 1-23. Zbl0804.68101MR1268488
  6. [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. Zbl0367.68034MR433962
  7. [Br] A. BRANDSTÄDT, Special graph classes - a survey. Report SM-DU-199, Universität-Gesamthochschule Duisburg, 1991. 
  8. [CPS] D. G. CORNEIL, Y. PERL and L. K. STEWART, A linear recognition algorithm for cographs, SIAM J. Comput, 1985, 4, pp. 926-934. Zbl0575.68065MR807891
  9. [Di] P. F. DIETZ, Intersection graph algorithms, Ph. D. thesis, Comput. Sci. Dept., Cornell Univ., Ithaka, NY 1984. 
  10. [Fr] A. FRANK, On chain and antichain families of a partially ordered set, J. Combinatorial Theory (B), 1980, 29, pp. 176-184. Zbl0443.06003MR586432
  11. [GJ] M. R. GAREY and D. S. JOHNSON, Computers and Intractability, A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. Zbl0411.68039MR519066
  12. [Ga] F. GAVRIL, Algorithms for maximum k-colorings and k-coverings of transitive graphs, Networks, 1987, 17, pp. 465-470. Zbl0642.05021MR912032
  13. [Go] M. C. GOLUMBIC, Algorithm graph theory and perfect graphs, Academic Press, New York, 1980. Zbl0541.05054MR562306
  14. [Ja] K. JANSEN, Scheduling of incompatible jobs on unrelated machines, International Journal of Foundations of Computer Science, 1993, 4, pp. 275-291. Zbl0799.90066MR1279494
  15. [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. Zbl0814.68064MR1371491
  16. [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. 
  17. [RS] N. ROBERTSON and P. SEYMOUR, Graph Minors. II. Algorithmic aspects of tree-width, Journal of Algorithms, 1986, 7, pp. 309-322. Zbl0611.05017MR855559
  18. [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. Zbl0684.68061MR1004243
  19. [YG] M. YANNAKAKIS and F. GAVRIL, The maximum k-colorable subgraph problem for chordal graphs, Information Processing Letters, 1987, 24, pp. 133-137. Zbl0653.68070MR882643

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.