{"entities":{"Q1068535":{"pageid":1079287,"ns":120,"title":"Item:Q1068535","lastrevid":66205716,"modified":"2026-04-12T08:15:12Z","type":"item","id":"Q1068535","labels":{"en":{"language":"en","value":"On the complexity of a family of generalized matching problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3932384"}},"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":"Q1068535$E6FD846D-D5CD-4DA4-B4BE-0937E0B09573","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fa022d9748226d099c295764de1efb4156b4e4f6","datavalue":{"value":{"text":"On the complexity of a family of generalized matching problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1068535$298CC37F-FAC4-41B0-BDA8-38BB129046C8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"49d28db596383473440f49862758d89c2358a4b5","datavalue":{"value":"0582.68014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068535$5409B31E-F618-445B-B803-15394D8685F4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fffe292eca64ef2fa28401b0eb81e820cf207b14","datavalue":{"value":"10.1016/0166-218X(85)90032-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068535$1E8CF9E6-C675-4234-9963-843CAC8641D1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"92231d63cabc3dcee3b00a19ed1ca19de20015c7","datavalue":{"value":{"entity-type":"item","numeric-id":678865,"id":"Q678865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068535$48F60A94-D092-410A-BB88-E29C8DA1AC88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb69352891d0a75c7f40ed920b09333ef25bf3d9","datavalue":{"value":{"entity-type":"item","numeric-id":185441,"id":"Q185441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068535$35C1B918-74C0-4783-A37D-7642AE9F4CA4","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":"Q1068535$7240A11D-329A-4D04-946C-9CCECE404C2A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1068535$75ED056C-5EDA-44CF-A3D0-99EC46879040","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"75974ea27f1fdaff89da8c4821eed817eeb8a1f3","datavalue":{"value":"We consider a family of generalized matching problems called k-feasible matching (k-FM) problems, where \\(k\\in \\{1,2,3,...\\}\\cup \\{\\infty \\}\\). We show each k-FM problem to be NP-complete even for very restricted cases. We develop a dynamic programming algorithm that solves in polynomial time the k-FM problem for graphs with width bounded by 2k. We also show that for any subset S of \\(\\{\\) 1,2,...\\(\\}\\) \\(\\cup \\{\\infty \\}\\), there is a set D of problem instances such that for k in S the k-FM problem is NP-complete on D, while for k not in S the k-FM problem is polynomially solvable on D.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068535$993E04DF-BFF5-44EF-8C04-0DDB55F1D52E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068535$7B6CA605-C565-4351-9934-E5CB56014395","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068535$CD66385C-307F-4242-A411-414F3DE96CA9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f1067baff69ea811118b8b7945265fddfdc2e22d","datavalue":{"value":"3932384","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068535$16F54CA5-5A8F-46AD-BEE5-D4306D4D3C7C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0de429593140647dc3a596da860845a1c045f74","datavalue":{"value":"mixed graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068535$573213BF-CD03-4FC1-8278-04C1E0F2A2CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068535$E9D8C635-7048-4822-90F0-8B2034420EA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c4e6f5ee3eb96ede7e096aad916387ba8743a62","datavalue":{"value":"dynamic programming algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068535$BEC077F5-C9B4-442B-80A4-33777F4495A0","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":"Q1068535$7AF2F1D5-B23F-4361-821E-3D9D5AF1D793","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"007c64cb1e51e420a82b1528582743678952b922","datavalue":{"value":{"entity-type":"item","numeric-id":2648578,"id":"Q2648578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068535$6051B318-3690-4961-9BA3-D3969252EDC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39738cea79e11456d6583aec1786d79af209b23","datavalue":{"value":{"entity-type":"item","numeric-id":5341586,"id":"Q5341586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068535$66D05808-8102-4892-89DA-291CEEB9CA17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89a031afe32dfcbf4f8fba11966dba55c1408ae","datavalue":{"value":{"entity-type":"item","numeric-id":4179026,"id":"Q4179026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068535$A13E0346-AC90-496E-A0F3-C07BBA389AC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068535$3709C115-9CDF-4BC5-B8AF-789C3BCAE07F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e68a7efc10f8e8ea4e36f7d70001059b8c12d905","datavalue":{"value":{"entity-type":"item","numeric-id":1241524,"id":"Q1241524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068535$4BF30F61-B476-4896-8F5C-0276BF2B7AF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b97f750e9c8b6509ac6238c920a51525b82dd93","datavalue":{"value":{"entity-type":"item","numeric-id":1068852,"id":"Q1068852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068535$6E974BA6-7733-410C-90EA-822F694F63B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068535$4D4FBECA-68B4-4B89-BCF6-EE51D9C7BA9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5322c6334ba1137bf5653782e31f911960a2cafa","datavalue":{"value":{"entity-type":"item","numeric-id":3939583,"id":"Q3939583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068535$21B9D11B-7FD5-4072-8D10-C606B022C256","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a73af81ab888b2965fe460eabf7089afc50641c","datavalue":{"value":{"entity-type":"item","numeric-id":3038617,"id":"Q3038617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068535$CE5C5B82-E237-4BB2-AFA5-D816A690AB28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"822dafee6fd3f972c1ebc6ec7de0721805d2c9d2","datavalue":{"value":{"entity-type":"item","numeric-id":3327716,"id":"Q3327716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068535$D0719F78-CB5D-4522-8D08-ACE1F891BF63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7628b399640b8b7904eac7b6685e6525d8cc73a","datavalue":{"value":{"entity-type":"item","numeric-id":4162941,"id":"Q4162941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068535$D1971A01-BFE3-4AA9-925F-D31EF548697B","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":"Q1068535$CF556686-3B2A-48FB-AF99-D4E21FF700F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49a089d2d23a33fbf3167ad429a459b6de513dd1","datavalue":{"value":{"entity-type":"item","numeric-id":1220386,"id":"Q1220386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068535$AEF63990-EEC1-48B0-B023-33E18277FB47","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a007b767f49f937e3fd1182cca0fb4e385bf1cba","datavalue":{"value":{"entity-type":"item","numeric-id":794163,"id":"Q794163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc8f9d4096828812eb744cd9d59ed6e1eae8c9b0","datavalue":{"value":{"amount":"+0.8207520246505737","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":"Q1068535$1CA3DA63-E3E8-47ED-9364-59CAD355AFC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"256ed105bf909030d0ea3699977565683c4f5943","datavalue":{"value":{"entity-type":"item","numeric-id":5402563,"id":"Q5402563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54ccbdce655ab5d6133a5f4a82f2458c791bd2b2","datavalue":{"value":{"amount":"+0.8030534982681274","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":"Q1068535$EFAC6844-EBE4-4EDB-B070-EDF708902EA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83ef1b4b9ae0fd5af09b93f2839c059806b0c686","datavalue":{"value":{"entity-type":"item","numeric-id":2756482,"id":"Q2756482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b19a8acb8c58f96caa60858eb5ca0127b092b6c","datavalue":{"value":{"amount":"+0.7969560623168945","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":"Q1068535$A6951528-BBB4-4DAB-9600-030FD613239F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b572233aba80cb9a9e9481a490c185367eb29fb6","datavalue":{"value":{"entity-type":"item","numeric-id":5900924,"id":"Q5900924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95366d3170d83cb294cb1b11591a08bc204232ad","datavalue":{"value":{"amount":"+0.7873431444168091","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":"Q1068535$7B3487BA-363F-48B8-B7CE-B6C00CA884B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14e8b337d79b999a6c7ca25bdf4615a8c4426792","datavalue":{"value":{"entity-type":"item","numeric-id":3139770,"id":"Q3139770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c95621b78bb7f8fb3ad26d1ed775f476d369a14d","datavalue":{"value":{"amount":"+0.7829751968383789","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":"Q1068535$038DECAF-87FF-4BEE-BBCB-D856F5FA2520","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of a family of generalized matching problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_a_family_of_generalized_matching_problems"}}}}}