{"entities":{"Q1975379":{"pageid":1986121,"ns":120,"title":"Item:Q1975379","lastrevid":71200044,"modified":"2026-04-13T20:21:23Z","type":"item","id":"Q1975379","labels":{"en":{"language":"en","value":"New results on induced matchings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1428630"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$CB9C6BFA-F429-4ED7-AA76-2ADFBE52AF94","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b522a1bce2f71db6de89c3ed12eef18b59534510","datavalue":{"value":{"text":"New results on induced matchings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1975379$FEAA916B-7A5D-4A2A-8EF9-251928D4E878","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5de819702fcbeed40236f513f89ce27c5dba1f9c","datavalue":{"value":"0951.68104","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1975379$1F150C40-61D8-4DD0-8A80-98E86BCE1E43","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"05daa264ea729f822161068e6d3a58ab2de8a23c","datavalue":{"value":"10.1016/S0166-218X(99)00194-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1975379$A937704C-807F-492B-B5A6-49DC1CFAD21E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b8eeeb529fb23a3ef59896edd03b07a25ad48fec","datavalue":{"value":{"entity-type":"item","numeric-id":251894,"id":"Q251894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$0C378E95-EF77-4699-AC41-F637714A4C2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"41540b69f430be2b29c8a8724f6e0407f350b8af","datavalue":{"value":{"entity-type":"item","numeric-id":287448,"id":"Q287448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$50B4FA32-CDD3-4BEB-AC8D-3CC8AA70BD31","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$6CB822D5-0D9C-4742-919D-C8EEC812410B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b5292801f0dd79298539819e0a4ac0e822803e06","datavalue":{"value":{"time":"+2000-12-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1975379$035685F1-8F55-4926-B3E2-53EB6F7C9EDB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c9021d244d03455d65deae2d14ee85671f2e1ebf","datavalue":{"value":"The paper concerns graphs \\(G=\\langle V,E\\rangle.\\) The induced matching \\(M\\subseteq E\\) contains a subset of edges of \\(E\\) that no two edges \\(e_{i}\\) and \\(e_{j}\\) in \\(M \\) share a common vertex \\(v\\in V\\) and there is no \\(e\\in E\\) connecting \\(e_{i}\\) and \\(e_{j}.\\) So, induced matching is matching that no two edges are connected in \\(G\\). The general problem of finding maximum induced matching is NP-complete and is also related to independent set and to clique. The text concerns polynomial time algorithms for wide classes of graphs. The authors recalling earlier results on maximum independent set conclude that polynomial time algorithms exist for circular arc and for chordal graphs. It is proved that maximum induced matching can be found in polynomial time for trapezoid graphs or for cocomparability graphs. For interval graphs or for trees maximum induced matching can be found in linear time and the algorithms are provided. The defined maximum induced matching is valid for graph theory since it can be used as a ``'measurement'' of graph irredundancy. Moreover, it can be used for modelling tasks concerning network communication, VLSI design, and other combinatorial tasks.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1975379$3A070E20-1752-4D20-AFA2-7C2921CAAEF5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1975379$791AF2F6-1B6B-43DE-9AD6-31F3C03CA68F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1975379$6AEBA2AB-41F5-4B54-B09E-B64407264223","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1975379$AEAFA14D-6373-43C2-A4F7-CADCDA949E2C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"525563348ebbd56e10a1cd2101c9cdf64e624fa0","datavalue":{"value":"1428630","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1975379$CD14F77D-7027-4F08-9A10-16CA6B1732DF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1975379$C51A0735-D7A9-4088-9582-31BD7EDF4E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6072fa2abea179a7709e57b96ad2802601bb845","datavalue":{"value":"perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1975379$ED0248CC-602E-46D9-BAA8-098414F1FC8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcc771f9c4cbb132a4fb9368403bb895cba44b70","datavalue":{"value":"matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1975379$7903DF87-2885-49EE-8956-48C17F8FCB99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24e4ced037335a8769537cc3e025579ea618bc03","datavalue":{"value":"induced matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1975379$3CDBD786-D7AC-4D9F-B0C1-3B161A08AC8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95ae1c5ff7f75c1b18d69d37b00e674a7134fd14","datavalue":{"value":"strong matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1975379$5F1FF293-1254-4BB3-9A45-4B7BFE9FCD14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1975379$D5F296D9-6C0A-4AF1-B994-B538C5B4ED6B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cc368e3db50c98d6dbe7e70c58f215b9063f9066","datavalue":{"value":{"entity-type":"item","numeric-id":1406029,"id":"Q1406029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$69AFE8A7-8C27-40B2-9EB6-5B7FA996C144","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$F92955CA-0A87-4BD1-AEE9-BC9787A69C0D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9914f8121a32baf6895c6797ec99c63c32102968","datavalue":{"value":{"entity-type":"item","numeric-id":1242450,"id":"Q1242450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$701B168D-2C7D-4451-BC1C-3C92967566DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55f40720899f5b124da6b573e677ed96f208cc49","datavalue":{"value":{"entity-type":"item","numeric-id":1262877,"id":"Q1262877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$F633CBB3-2F91-478A-BA08-67B051C9780C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef772f6e1f76bbabf157965708eb7681dc17830f","datavalue":{"value":{"entity-type":"item","numeric-id":4250178,"id":"Q4250178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$A41BC523-9675-4990-8453-44F9134A1055","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79cc333a398e9d6212f316ca27b812994cbe7ce9","datavalue":{"value":{"entity-type":"item","numeric-id":1111577,"id":"Q1111577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$409EA721-C3D6-4923-98AD-06FC89F8531B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5412029a0de44f9f3f2a7784aa6f0e11fb01c84","datavalue":{"value":{"entity-type":"item","numeric-id":678864,"id":"Q678864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$DCF0905C-CAA2-4A3A-95CC-0CAE08D7A67B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c202e03beada7e3d7ff0037eed9f003b31649a3b","datavalue":{"value":{"entity-type":"item","numeric-id":3139292,"id":"Q3139292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$F18DFD49-669A-49A8-AF9B-C2B7442B25CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c33959e8c3fbe7080f98305389592daf8f06321e","datavalue":{"value":{"entity-type":"item","numeric-id":5634016,"id":"Q5634016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$7A0487AC-4BCB-4B3D-84BB-E29C650792DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c17b1143dff0bc685088f8d62dbc046a1f96e02e","datavalue":{"value":{"entity-type":"item","numeric-id":5732670,"id":"Q5732670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$71F3458F-08C7-4D88-9373-3A936AD46A39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c998f37ea2af5fb09fab159d72a9dd7f47c2d7d1","datavalue":{"value":{"entity-type":"item","numeric-id":1235707,"id":"Q1235707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$03D3B11F-77D3-4D06-BB1A-6A6BFFA0C216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$6DBD467A-E84E-4D8E-8458-99B102126282","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45194377a8ee1081a86c5efc74b5bc9ac7dc5648","datavalue":{"value":{"entity-type":"item","numeric-id":3796775,"id":"Q3796775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$E988B5F9-3D91-485E-9701-32B7316C8F9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b8d121c8bcbb47877b3d998d2df25af035ad302","datavalue":{"value":{"entity-type":"item","numeric-id":686248,"id":"Q686248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$C093D542-AF8C-4E80-9DBE-8C51A0100E42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d22d1a66627507c9e175f0940657f78d850ce78c","datavalue":{"value":{"entity-type":"item","numeric-id":3956413,"id":"Q3956413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$DC5C0A2D-5055-4FEB-BA60-9E3A6D594B4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"676b8c781ab70d54f57dfba962d77328726030e4","datavalue":{"value":{"entity-type":"item","numeric-id":1199945,"id":"Q1199945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$B9B13B22-4D8D-44A0-8850-4D72B03125B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf54b83cd5d8b947d8f3677c5adccd88ca3ec5a0","datavalue":{"value":{"entity-type":"item","numeric-id":1183454,"id":"Q1183454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$1C4E45B9-4BF4-4AFC-A26E-EC372697DFDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9eecfbd0fe0fb880a6b3405cc8df01efea6f4f48","datavalue":{"value":{"entity-type":"item","numeric-id":3495653,"id":"Q3495653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975379$25C55C86-4B18-48DB-B469-69076DEC8A35","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5744f463747bbf1206d167bb1467a97e5b94b68f","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00194-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1975379$77581F88-53BF-4E04-9CAA-2D27AB4F5B7B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"570a3efd6b9904a46776f8a5adb6e776d0b9608d","datavalue":{"value":"W1974366154","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1975379$6B516BA1-9614-4D92-A82D-5503F8CC6F56","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3790cf6f8d44854427e31fcc2307aafd324e0faf","datavalue":{"value":{"entity-type":"item","numeric-id":1262877,"id":"Q1262877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"438462cadbe7ffc9b9f37c791223176fdbaf8963","datavalue":{"value":{"amount":"+0.8696186542510986","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1975379$A606480E-B8E0-4442-BFB3-62E7596BE29E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cba01ec3e19dd81eb237521e9d15c8ee42c32387","datavalue":{"value":{"entity-type":"item","numeric-id":1427466,"id":"Q1427466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53e384cda96f452184b10f5977e56943584fb1c8","datavalue":{"value":{"amount":"+0.8595710396766663","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1975379$E336E07E-CC7F-4666-9024-E8A546481604","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f3920fd052247c885c133a40542fde7fcdb3590","datavalue":{"value":{"entity-type":"item","numeric-id":2971661,"id":"Q2971661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94aa33ca78e40bb6a876f644b6731124998284c5","datavalue":{"value":{"amount":"+0.8587195873260498","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1975379$80985E6D-67BB-49C6-A4DB-670A558C780E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea9180b088f808f52637222f0211f7040651a092","datavalue":{"value":{"entity-type":"item","numeric-id":4500845,"id":"Q4500845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"411d9815132d58b4a2fb1afb4d05c7fa75a367bf","datavalue":{"value":{"amount":"+0.8570906519889832","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1975379$226B56F3-6678-4BF3-B5B8-3EE94F53B5F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e837f7980e4135f4e57861bec408a90db30eb53","datavalue":{"value":{"entity-type":"item","numeric-id":1762983,"id":"Q1762983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf6e454c8752f8fc9961b008de5423ac3cf41767","datavalue":{"value":{"amount":"+0.8480140566825867","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1975379$D4212D68-03CA-4E52-8BB6-34DC460C40C5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"New results on induced matchings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/New_results_on_induced_matchings"}}}}}