{"entities":{"Q1810638":{"pageid":1821380,"ns":120,"title":"Item:Q1810638","lastrevid":48108058,"modified":"2026-01-03T16:23:10Z","type":"item","id":"Q1810638","labels":{"en":{"language":"en","value":"Finding a maximum induced matching in weakly chordal graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1924761"}},"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":"Q1810638$308D82BF-990E-4113-9FE7-691B90A8EB3E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e7113c89351261f761742a3662067bc0b87334e2","datavalue":{"value":{"text":"Finding a maximum induced matching in weakly chordal graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1810638$8BA39168-34ED-4F4E-869B-06D8602B3458","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f328fea55ed59e19aa4f5977acfecb9de06f2fde","datavalue":{"value":"1022.05064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1810638$FDCA0C0A-CA2E-4F68-98A7-060FE5281B2B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"97b04f5d428b49b4bb559c348e39bd2393c17d5f","datavalue":{"value":"10.1016/S0012-365X(02)00803-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1810638$4FB1E8B1-3AFC-426C-9303-1D9EB647AF0D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3b8576669bc0ecd8cf391048775047cac1b4b93","datavalue":{"value":{"entity-type":"item","numeric-id":168646,"id":"Q168646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$889519DF-7517-401E-A413-B94C3AF6AEA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aaea17b454761e4e721643e7b17e8efa2dae9e33","datavalue":{"value":{"entity-type":"item","numeric-id":198206,"id":"Q198206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$527F7870-687A-4953-966B-E7CC0F0ECED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0c00051fe5fa03618124570f91d35a4b9b7da895","datavalue":{"value":{"entity-type":"item","numeric-id":1810637,"id":"Q1810637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$CF5ED43D-835A-4D74-B002-205644465032","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$E64DC98A-7921-4F56-A33C-5FF71914ABF9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c2d0e39c696776e04b9e53093e3633112a8f4686","datavalue":{"value":{"time":"+2003-06-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1810638$60C0E0FF-35C6-4421-854E-8EB5D1B7695F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"49fb1f6a11f261100e7423a067e726d1213cb6c0","datavalue":{"value":"It is known that finding an induced matching of maximum cardinality in a graph is NP-hard. It is shown in this paper that a maximum induced matching in a weakly chordal graph can be found in polynomial time. This generalizes previously known results for the induced matching problem. This also demonstrates that the maximum induced matching problem in chordal bipartite graphs can be solved in polynomial time while the problem is known to be NP-hard for bipartite graphs in general.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810638$58D26FBE-DF82-44F6-BFF8-856B468491D0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2a9e190796e445b79b394886bb018cccd03bd7cb","datavalue":{"value":{"entity-type":"item","numeric-id":585164,"id":"Q585164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$2910980C-4E35-42B8-A0EF-4B6278F31A50","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1810638$4EC238EB-B9B1-428E-9C7C-14AB2C9CCFB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1810638$40A760C6-0283-405A-B42E-C1161214C580","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f9836a481924121e2a1a6e97d11bb0e514bd88cc","datavalue":{"value":"1924761","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1810638$4E214F7A-5220-42DF-983C-37B5CF6CD2E8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24e4ced037335a8769537cc3e025579ea618bc03","datavalue":{"value":"induced matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810638$61DBD1E1-8E90-4CA0-9A46-432CE080942C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95ae1c5ff7f75c1b18d69d37b00e674a7134fd14","datavalue":{"value":"strong matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810638$D6F57D76-57BC-4BD9-A5EE-DABC7E82EA27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69a5ab2c077a4acf425f34d37706d2b1f6342003","datavalue":{"value":"strong edge-colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810638$162C5B25-A889-49BC-935B-96EE1CE93FAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8773009372ada8b5ee77edb73206b62f8d2d70b6","datavalue":{"value":"strong chromatic index","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810638$17308C4A-65D4-49AA-A6AC-5AF30987AC0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"478f84e9c3e046bc46ddb3a0fb12fba70158332e","datavalue":{"value":"weakly chordal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810638$A5F156E1-CFB2-4676-B85B-59B51284D785","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0791cd1c5448535c60cdc35b44cd26117132492f","datavalue":{"value":"interval-filament graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810638$18F8AA85-B0FC-430E-8745-D41D8A1C1841","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25f8eba8c9d529f212c848e074f37e4d66acf3cf","datavalue":{"value":"intersection graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810638$45AF4EA0-BA39-4D80-BA66-ADA382E3D952","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810638$62B0E6D3-8624-4B96-8494-21F44D508091","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":"Q1810638$2FD01E52-2006-4F61-90C1-CD239485F186","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"282d88b529308441c287f6c692de7afeae122bdc","datavalue":{"value":{"entity-type":"item","numeric-id":4243764,"id":"Q4243764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$DA345141-16F1-42C2-B913-E9535A3C34A5","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":"Q1810638$07F7DD7E-3DA0-4D7F-818A-D03104AFF487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01616b46c2ed00862ee4173fc61849d6ed216b6e","datavalue":{"value":{"entity-type":"item","numeric-id":2816065,"id":"Q2816065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$FEF143B4-13E7-4BA6-A8D0-11726B6BA581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"001501abecb90c8508f686b8509a0057bfd4ebe0","datavalue":{"value":{"entity-type":"item","numeric-id":1414582,"id":"Q1414582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$915FFF9D-3CCB-4396-99FE-4E5F00AE575A","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":"Q1810638$572867D7-30E2-436C-BC1C-6280CCEE2006","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e15bca7e73f4a53f5f600337b773b742e755f30c","datavalue":{"value":{"entity-type":"item","numeric-id":294733,"id":"Q294733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$EAD9AB12-FFD0-46AA-B28A-00A7A6E18C6D","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":"Q1810638$29CA3E7F-EF16-48A3-8F78-862B7FBE5521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e85377583d461b3cae645b2aadcf878b4786d339","datavalue":{"value":{"entity-type":"item","numeric-id":1975379,"id":"Q1975379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$1C2335FE-E270-4A97-BC7B-A8C7D1D0D492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8cfed7f4900e3e265b78f148b39a5857eb957a6","datavalue":{"value":{"entity-type":"item","numeric-id":1172652,"id":"Q1172652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$EED03B3F-7D2C-4FBF-A163-70DD947F7530","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b276fdb2188dac0c4b19127d85e1049cb332b2c","datavalue":{"value":{"entity-type":"item","numeric-id":801088,"id":"Q801088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$DE245326-BD07-4084-86DA-4154E4425985","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bed7197995b093007527a5d546d60b05148a6d9e","datavalue":{"value":{"entity-type":"item","numeric-id":1822967,"id":"Q1822967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$A392582A-B350-46AC-BFFC-D4533990557D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1570ecc6fc5fdd94ea8f8f660a562a0c69ea2d5e","datavalue":{"value":{"entity-type":"item","numeric-id":4952597,"id":"Q4952597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$C55E71D0-AD5A-425E-B9E9-5C4DE30CBF9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62a2183d2e50683cbffb656d6d6cc0cc15e31ddf","datavalue":{"value":{"entity-type":"item","numeric-id":1201264,"id":"Q1201264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$27C25CED-4A26-4141-A22F-5A18170C2A2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3691556e169f89994b5f82e28e5fdff00d9ee0c","datavalue":{"value":{"entity-type":"item","numeric-id":1356563,"id":"Q1356563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$6EFC6248-1BB5-498F-8F20-EB72A91A87BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f3e95800479942d2644976ec5a278a6b049debc","datavalue":{"value":{"entity-type":"item","numeric-id":1891926,"id":"Q1891926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$95E7C877-7E33-4ECB-B4C3-D805A2514D8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3498f0fc8e71871e139619a5769a0845109f90c6","datavalue":{"value":{"entity-type":"item","numeric-id":1168728,"id":"Q1168728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810638$92973308-B3AC-4D8F-A4A3-D67805F158BC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ea01054f46db53c77113d4e3b92541e82096d84a","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(02)00803-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1810638$E56F7D2A-5FBE-4CF3-9DD0-03E83310A904","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b5a8ba7e0edff6df3ab9653e9b09bfbf3ca74f43","datavalue":{"value":"W1977889556","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1810638$F80B9B5D-02AE-4D64-B27C-430486BE446C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"784c68f2ba8d5fc31cddab31372956fd89faa048","datavalue":{"value":{"entity-type":"item","numeric-id":1847371,"id":"Q1847371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0bc89401b872630426fdfa1d72cbe411b2704eef","datavalue":{"value":{"amount":"+0.8560525178909302","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":"Q1810638$FEB5A6C1-4D13-47E7-97BF-3960A5CB61F9","rank":"normal"},{"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":"88b201245e68e70dfd5e158c3767f03ae2867228","datavalue":{"value":{"amount":"+0.8479160666465759","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":"Q1810638$D24A0FAA-0803-4E8C-9CAB-1DC107C08B2D","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":"437408aa319ce95c15b0fb0cd526d91d80cb5c63","datavalue":{"value":{"amount":"+0.8420866131782532","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":"Q1810638$DBDED644-9A43-49EE-82CC-4EE53F08AC50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"baaca4d83764fbb773770b66b50033836b7d3c6f","datavalue":{"value":{"entity-type":"item","numeric-id":1975379,"id":"Q1975379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17dbda8a2dea90b65e8a573287fa1eec9211e7e9","datavalue":{"value":{"amount":"+0.8396222591400146","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":"Q1810638$E6763FD7-BA67-4E19-91F1-37BB8ED6C101","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":"549cca15e0bec8c79bdf6962623063263fd58b02","datavalue":{"value":{"amount":"+0.822673499584198","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":"Q1810638$12DAB001-724F-4F06-A1EE-53A14FDADA95","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1810638","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1810638"}}}}}