{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:24:21Z","timestamp":1774369461475,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540651956","type":"print"},{"value":"9783540494942","type":"electronic"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/10692760_3","type":"book-chapter","created":{"date-parts":[[2010,6,30]],"date-time":"2010-06-30T12:35:37Z","timestamp":1277901337000},"page":"26-37","source":"Crossref","is-referenced-by-count":6,"title":["The Vertex-Disjoint Triangles Problem"],"prefix":"10.1007","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C. Pandu","family":"Rangan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. S.","family":"Chang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G. J.","family":"Chang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C. K.","family":"Wong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM\u00a041, 153\u2013180 (1994)","journal-title":"Journal of the ACM"},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D.G. Cornell","year":"1985","unstructured":"Cornell, D.G., Perl, Y., Stewart, L.K.: A Linear recognition algorithm for cographs. SIAM Jl. on Computing\u00a014, 926\u2013934 (1985)","journal-title":"SIAM Jl. on Computing"},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0167-6377(82)90016-5","volume":"1","author":"G. Cornuejols","year":"1982","unstructured":"Cornuejols, G., Hartvigsen, D., Pulleyblank, W.: Packing Subgraphs in a Graph. Operations Research Letters\u00a01, 139\u2013143 (1982)","journal-title":"Operations Research Letters"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Dahlhaus, E., Karpinski, M.: Matching and Multidimensional Matching in Chordal and Strongly Chordal Graphs. Discerete Applied Math.\u00a0(84), 79\u201391 (1998)","DOI":"10.1016\/S0166-218X(98)00006-7"},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees and flowers. Canadian J. Math.\u00a017, 449\u2013469 (1965)","journal-title":"Canadian J. Math."},{"key":"3_CR6","volume-title":"Computers and Intractability: A guide to the theory of NP-completeness.","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A guide to the theory of NP-completeness. Freeman, San Francisco (1979)"},{"key":"3_CR7","volume-title":"Algorithmic graph theory and Perfect graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic graph theory and Perfect graphs. Academic Press, New York (1980)"},{"key":"3_CR8","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison- Wesley, Reading (1969)"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0020-0190(81)90073-9","volume":"12","author":"P. Hell","year":"1981","unstructured":"Hell, P., Kirkpatrick, D.G.: On generalized matching problems. Info. Proc. Letters\u00a012, 33\u201335 (1981)","journal-title":"Info. Proc. Letters"},{"key":"3_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/BFb0049428","volume-title":"Algorithms - ESA \u201994","author":"H.B. Hunt III","year":"1994","unstructured":"Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: A unified approach to approximation schemes for NP- and PSPACE-hard problems for geometric graphs. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol.\u00a0855, pp. 424\u2013435. Springer, Heidelberg (1994)"},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"C.A.J. Hurkens","year":"1989","unstructured":"Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Mathematics\u00a02, 68\u201372 (1989)","journal-title":"SIAM J. Discrete Mathematics"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V. Kann","year":"1991","unstructured":"Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Information Processing Letters\u00a037, 27\u201335 (1991)","journal-title":"Information Processing Letters"},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1137\/0212040","volume":"12","author":"D.G. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.G., Hell, P.: On the complexity of general graph factor problems. SIAM JI. on Computing\u00a012, 601\u2013609 (1983)","journal-title":"SIAM JI. on Computing"},{"key":"3_CR14","unstructured":"Micali, S., Vazirani, V.V.: An O( <math display='block'> <mrow> <mi>O<\/mi><mrow><mo>(<\/mo> <mrow> <msqrt> <mrow> <mrow><mo>|<\/mo> <mi>V<\/mi> <mo>|<\/mo><\/mrow> <\/mrow> <\/msqrt> <mrow><mo>|<\/mo> <mi>E<\/mi> <mo>|<\/mo><\/mrow> <\/mrow> <mo>)<\/mo><\/mrow> <\/mrow> <\/math> $\\sqrt{|V|}{|E|}$ ) algorithm for finding maximum matching in general graphs. In: Proc. 21st Annual Symposium on the foundation of Comp. Sci., pp. 17\u201327 (1980)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/10692760_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T12:08:33Z","timestamp":1559218113000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/10692760_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540651956","9783540494942"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/10692760_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]}}}