EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 31 / No 1 (1997) RAIRO-Oper. Res., 31 1 (1997) 45-66 References
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] [Google Scholar]
  • [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] [Google Scholar]
  • [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] [Google Scholar]
  • [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] [Google Scholar]
  • [Bo2] H. L. BODLAENDER, A tourist guide through treewidth, Acta Cybernetica, 1993, 11, pp. 1-23. [MR: 1268488] [Zbl: 0804.68101] [Google Scholar]
  • [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] [Google Scholar]
  • [Br] A. BRANDSTÄDT, Special graph classes - a survey. Report SM-DU-199, Universität-Gesamthochschule Duisburg, 1991. [Google Scholar]
  • [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] [Google Scholar]
  • [Di] P. F. DIETZ, Intersection graph algorithms, Ph. D. thesis, Comput. Sci. Dept., Cornell Univ., Ithaka, NY 1984. [Google Scholar]
  • [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] [Google Scholar]
  • [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] [Google Scholar]
  • [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] [Google Scholar]
  • [Go] M. C. GOLUMBIC, Algorithm graph theory and perfect graphs, Academic Press, New York, 1980. [MR: 562306] [Zbl: 0541.05054] [Google Scholar]
  • [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] [Google Scholar]
  • [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] [Google Scholar]
  • [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. [Google Scholar]
  • [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] [Google Scholar]
  • [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] [Google Scholar]
  • [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] [Google Scholar]

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.