{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:30:07Z","timestamp":1725535807334},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642020285"},{"type":"electronic","value":"9783642020292"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-02029-2_11","type":"book-chapter","created":{"date-parts":[[2009,7,27]],"date-time":"2009-07-27T14:12:39Z","timestamp":1248703959000},"page":"116-126","source":"Crossref","is-referenced-by-count":2,"title":["On Distance-3 Matchings and Induced Matchings"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Brandst\u00e4dt","sequence":"first","affiliation":[]},{"given":"Raffaele","family":"Mosca","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"11_CR1","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1109\/JSAC.2004.830909","volume":"22","author":"H. Balakrishnan","year":"2004","unstructured":"Balakrishnan, H., Barrett, C.L., Anil Kumar, V.S., Marathe, M.V., Thite, S.: The Distance-2 Matching Problem and Its Relationship to the MAC-Layer Capacity of Ad Hoc Wireless Networks. IEEE J. on Selected Areas in Communications\u00a022(6), 1069\u20131079 (2004)","journal-title":"IEEE J. on Selected Areas in Communications"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/S0166-218X(02)00571-1","volume":"129","author":"A. Brandst\u00e4dt","year":"2003","unstructured":"Brandst\u00e4dt, A., Dragan, F.F.: On the linear and circular structure of (claw,net)-free graphs. Discrete Applied Mathematics\u00a0129, 285\u2013303 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"1662","DOI":"10.1137\/S0097539799357775","volume":"30","author":"A. Brandst\u00e4dt","year":"2000","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., K\u00f6hler, E.: Linear time algorithms for Hamiltonian problems on (claw,net)-free graphs. SIAM J. Computing\u00a030, 1662\u20131677 (2000)","journal-title":"SIAM J. Computing"},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/11496915_20","volume-title":"Integer Programming and Combinatorial Optimization","author":"A. Brandst\u00e4dt","year":"2005","unstructured":"Brandst\u00e4dt, A., Ho\u00e0ng, C.T.: On clique separators, nearly chordal graphs and the Maximum Weight Stable Set problem. In: J\u00fcnger, M., Kaibel, V. (eds.) IPCO 2005. LNCS, vol.\u00a03509, pp. 265\u2013275. Springer, Heidelberg (2005); Theoretical Computer Science, vol. 389, pp. 295\u2013306 (2007)"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Ho\u00e0ng, C.T.: Maximum Induced Matchings for Chordal Graphs in Linear Time, appeared online. In: Algorithmica (2008)","DOI":"10.1007\/s00453-007-9045-2"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Klembt, T., Lozin, V.V., Mosca, R.: Maximum stable sets in subclasses of apple-free graphs, appeared online. In: Algorithmica (2008)","DOI":"10.1007\/s00453-008-9176-0"},{"key":"11_CR7","series-title":"SIAM Monographs on Discrete Math. Appl","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Math. Appl, vol.\u00a03. SIAM, Philadelphia (1999)"},{"key":"11_CR8","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Clique Separator Decomposition and Modular Decomposition for the Maximum Induced Matching Problem (2008) (manuscript)"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1137\/S0895480197326346","volume":"12","author":"A. Broersma","year":"1999","unstructured":"Broersma, A., Kloks, T., Kratsch, D., M\u00fcller, H.: Independent sets in asteroidal-triple-free graphs. SIAM J. Discrete Math.\u00a012, 276\u2013287 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0166-218X(92)90275-F","volume":"24","author":"K. Cameron","year":"1989","unstructured":"Cameron, K.: Induced matchings. Discrete Applied Math.\u00a024, 97\u2013102 (1989)","journal-title":"Discrete Applied Math."},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.disc.2003.05.001","volume":"278","author":"K. Cameron","year":"2004","unstructured":"Cameron, K.: Induced matchings in intersection graphs. Discrete Mathematics\u00a0278, 1\u20139 (2004)","journal-title":"Discrete Mathematics"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0012-365X(02)00803-8","volume":"266","author":"K. Cameron","year":"2003","unstructured":"Cameron, K., Sritharan, R., Tang, Y.: Finding a maximum induced matching in weakly chordal graphs. Discrete Math.\u00a0266, 133\u2013142 (2003)","journal-title":"Discrete Math."},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0166-218X(03)00390-1","volume":"132","author":"J.-M. Chang","year":"2003","unstructured":"Chang, J.-M.: Induced matchings in asteroidal-triple-free graphs. Discrete Applied Math.\u00a0132, 67\u201378 (2003)","journal-title":"Discrete Applied Math."},{"key":"11_CR14","first-page":"161","volume":"67","author":"J.-M. Chang","year":"2003","unstructured":"Chang, J.-M., Ho, C.W., Ko, M.T.: Powers of asteroidal-triple-free graphs with applications. Ars Combinatoria\u00a067, 161\u2013173 (2003)","journal-title":"Ars Combinatoria"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Chudnovsky, M., Seymour, P.: The Structure of Clawfree Graphs, Surveys in Combinatorics 2005. London Math. Soc. Lecture Note Series, vol.\u00a0327 (2005)","DOI":"10.1017\/CBO9780511734885.008"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jda.2004.05.001","volume":"3","author":"W. Duckworth","year":"2005","unstructured":"Duckworth, W., Manlove, D., Zito, M.: On the Approximability of the Maximum Induced Matching Problem. J. of Discrete Algorithms\u00a03, 79\u201391 (2005)","journal-title":"J. of Discrete Algorithms"},{"key":"11_CR17","first-page":"67","volume":"21","author":"P. Duchet","year":"1984","unstructured":"Duchet, P.: Classical perfect graphs. Annals of Discrete Math.\u00a021, 67\u201396 (1984)","journal-title":"Annals of Discrete Math."},{"key":"11_CR18","first-page":"297","volume-title":"The theory and applications of graphs (Kalamazoo, Mich. 1980)","author":"D. Duffus","year":"1981","unstructured":"Duffus, D., Jacobson, M.S., Gould, R.J.: Forbidden subgraphs and the Hamiltonian theme. In: The theory and applications of graphs (Kalamazoo, Mich. 1980), pp. 297\u2013316. Wiley, New York (1981)"},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0012-365X(88)90196-3","volume":"72","author":"P. Erd\u00f6s","year":"1988","unstructured":"Erd\u00f6s, P.: Problems and results in combinatorial analysis and graph theory. Discrete Math.\u00a072, 81\u201392 (1988)","journal-title":"Discrete Math."},{"key":"11_CR20","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0012-365X(89)90163-5","volume":"78","author":"R.J. Faudree","year":"1989","unstructured":"Faudree, R.J., Gy\u00e1rfas, A., Schelp, R.H., Zuza, Z.: Induced matchings in bipartite graphs. Discrete Mathematics\u00a078, 83\u201387 (1989)","journal-title":"Discrete Mathematics"},{"key":"11_CR21","first-page":"211","volume-title":"Proceedings of the Fifth British Combinatorial Conference","author":"A. Frank","year":"1975","unstructured":"Frank, A.: Some polynomial algorithms for certain graphs and hypergraphs. In: Proceedings of the Fifth British Combinatorial Conference, pp. 211\u2013226. Univ. Aberdeen, Aberdeen (1975); Congressus Numerantium No. XV, Utilitas Math., Winnipeg, Man (1976)"},{"key":"11_CR22","first-page":"239","volume":"89","author":"G. Fricke","year":"1992","unstructured":"Fricke, G., Laskar, R.: Strong matchings on trees. Congressus Numerantium\u00a089, 239\u2013243 (1992)","journal-title":"Congressus Numerantium"},{"key":"11_CR23","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, London (1980)"},{"key":"11_CR24","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/0196-6774(88)90023-5","volume":"9","author":"M.C. Golumbic","year":"1988","unstructured":"Golumbic, M.C., Hammer, P.L.: Stability in circular-arc graphs. J. Algorithms\u00a09, 314\u2013320 (1988)","journal-title":"J. Algorithms"},{"key":"11_CR25","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0166-218X(93)90223-B","volume":"44","author":"M.C. Golumbic","year":"1993","unstructured":"Golumbic, M.C., Laskar, R.C.: Irredundancy in circular-arc graphs. Discrete Applied Math.\u00a044, 79\u201389 (1993)","journal-title":"Discrete Applied Math."},{"key":"11_CR26","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/S0166-218X(99)00194-8","volume":"101","author":"M.C. Golumbic","year":"2000","unstructured":"Golumbic, M.C., Lewenstein, M.: New results on induced matchings. Discrete Applied Math.\u00a0101, 157\u2013165 (2000)","journal-title":"Discrete Applied Math."},{"key":"11_CR27","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"M.C. Golumbic","year":"2000","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Internat. J. of Foundations of Computer Science\u00a011, 423\u2013443 (2000)","journal-title":"Internat. J. of Foundations of Computer Science"},{"issue":"2","key":"11_CR28","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1002\/jgt.3190170204","volume":"17","author":"P. Hor\u00e1k","year":"1993","unstructured":"Hor\u00e1k, P., Qing, H., Trotter, W.T.: Induced matchings in cubic graphs. J. Graph Theory\u00a017(2), 151\u2013160 (1993)","journal-title":"J. Graph Theory"},{"key":"11_CR29","doi-asserted-by":"publisher","first-page":"2755","DOI":"10.1016\/j.disc.2006.04.022","volume":"306","author":"A. Kelmans","year":"2006","unstructured":"Kelmans, A.: On Hamiltonicity of (claw,net)-free graphs. Discrete Math.\u00a0306, 2755\u20132761 (2006)","journal-title":"Discrete Math."},{"key":"11_CR30","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1137\/S089548019828371X","volume":"16","author":"C.W. Ko","year":"2003","unstructured":"Ko, C.W., Shepherd, F.B.: Bipartite domination and simultaneous matroid covers. SIAM J. Discrete Math.\u00a016, 517\u2013523 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"11_CR31","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00453-003-1035-4","volume":"37","author":"D. Kobler","year":"2003","unstructured":"Kobler, D., Rotics, U.: Finding maximum induced matchings in subclasses of claw-free and P 5-free graphs and in graphs with matching and induced matching of equal maximum size. Algorithmica\u00a037, 327\u2013346 (2003)","journal-title":"Algorithmica"},{"key":"11_CR32","unstructured":"K\u00f6hler, E.: Graphs without asteroidal triples, Ph.D. Thesis, FB Mathematik, TU Berlin (1999)"},{"key":"11_CR33","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/S0020-0190(01)00185-5","volume":"81","author":"V.V. Lozin","year":"2002","unstructured":"Lozin, V.V.: On maximum induced matchings in bipartite graphs. Information Processing Letters\u00a081, 7\u201311 (2002)","journal-title":"Information Processing Letters"},{"key":"11_CR34","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"R.M. McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.: Modular decomposition and transitive orientation. Discrete Mathematics\u00a0201, 189\u2013241 (1999)","journal-title":"Discrete Mathematics"},{"key":"11_CR35","first-page":"257","volume":"19","author":"R.H. M\u00f6hring","year":"1984","unstructured":"M\u00f6hring, R.H., Radermacher, F.J.: Substitution decomposition for discrete structures and connections with combinatorial optimization. Annals of Discrete Mathematics\u00a019, 257\u2013356 (1984)","journal-title":"Annals of Discrete Mathematics"},{"key":"11_CR36","unstructured":"Orlovich, Y., Finke, G., Gordon, V., Zverovich, I.E.: Approximability for the minimum and maximum induced matching problems, TR 130, Laboratoire Leibiz-IMAG, Grenoble (2005)"},{"key":"11_CR37","unstructured":"Orlovich, Y., Zverovich, I.E.: Well-matched graphs, RRR 12-2004 (2004)"},{"key":"11_CR38","unstructured":"Orlovich, Y., Zverovich, I.E.: Maximal induced matchings of minimum\/maximum size, DIMACS TR 2004-26 (2004)"},{"key":"11_CR39","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0012-365X(93)90590-P","volume":"120","author":"A. Steger","year":"2004","unstructured":"Steger, A., Yu, M.: On induced matchings. Discrete Math.\u00a0120, 291\u2013295 (2004)","journal-title":"Discrete Math."},{"key":"11_CR40","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0020-0190(82)90077-1","volume":"15","author":"L.J. Stockmeyer","year":"1982","unstructured":"Stockmeyer, L.J., Vazirani, V.V.: NP-completeness of some generalizations of the maximum matching problem. Information Processing Letters\u00a015, 14\u201319 (1982)","journal-title":"Information Processing Letters"},{"key":"11_CR41","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"R.E. Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Decomposition by clique separators. Discrete Math.\u00a055, 221\u2013232 (1985)","journal-title":"Discrete Math."},{"key":"11_CR42","volume-title":"Topics on perfect graphs","author":"S.H. Whitesides","year":"1984","unstructured":"Whitesides, S.H.: A method for solving certain graph recognition and optimization problems, with applications to perfect graphs. In: Berge, C., Chv\u00e1tal, V. (eds.) Topics on perfect graphs. North-Holland, Amsterdam (1984)"},{"key":"11_CR43","first-page":"58","volume":"7","author":"M. Zito","year":"2000","unstructured":"Zito, M.: Linear time maximum induced matching algorithm for trees. Nordic J. Comput.\u00a07, 58\u201363 (2000)","journal-title":"Nordic J. Comput."}],"container-title":["Lecture Notes in Computer Science","Graph Theory, Computational Intelligence and Thought"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02029-2_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,21]],"date-time":"2020-05-21T00:42:28Z","timestamp":1590021748000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02029-2_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642020285","9783642020292"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02029-2_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}