Free Access
Issue
RAIRO-Oper. Res.
Volume 31, Number 1, 1997
Page(s) 45 - 66
DOI https://doi.org/10.1051/ro/1997310100451
Published online 10 February 2017
  • [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. [Zbl: 1310.68083]
  • [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]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.