{"entities":{"Q1589639":{"pageid":1600379,"ns":120,"title":"Item:Q1589639","lastrevid":47546530,"modified":"2026-01-02T01:17:13Z","type":"item","id":"Q1589639","labels":{"en":{"language":"en","value":"A comparison of structural CSP decomposition methods"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1542379"}},"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":"Q1589639$C3C8AF4D-7CB2-4A41-98DC-6A199D974A86","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"711db7102961a71f59a6826bfa55a82d2e3aaf42","datavalue":{"value":{"text":"A comparison of structural CSP decomposition methods","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1589639$B1B29508-DE8F-4EBD-8095-F40A0E84BF90","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"631493b5fd467dd261789ec341c65a7f30230e3f","datavalue":{"value":"0952.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589639$79A6AAE0-DDB9-4AC7-B2E2-DEDC9A81885B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9edce02cdb4b9fdae0df1efb82fbc3ce2bd82b7a","datavalue":{"value":"10.1016/S0004-3702(00)00078-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589639$75172CDC-17BB-487D-86BD-3C21EFCDFA9F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"984e6510ec40a363d20e607cce2cc2f8b07918ae","datavalue":{"value":{"entity-type":"item","numeric-id":72340,"id":"Q72340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$1E310348-F1C3-43D3-9406-03B9559F6477","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1fc98fd02909f39fc4d6749553781a25cceed046","datavalue":{"value":{"time":"+2000-12-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1589639$8BB93BFB-B5A2-4419-97A3-B1CA693273F5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9debaaa72c4e0dc7e897382b5bc26adeccef5cfd","datavalue":{"value":"We compare tractable classes of Constraint Satisfaction Problems (CSPs). We first give a uniform presentation of the major structural CSP decomposition methods. We then introduce a new class of tractable CSPs based on the concept of hypertree decomposition recently developed in database theory, and analyze the cost of solving CSPs having bounded hypertree-width. We provide a framework for comparing parametric decomposition-based methods according to tractability criteria and compare the most relevant methods. We show that the method of hypertree decomposition dominates the others in the case of general CSPs (i.e., CSPs of unbounded arity). We also make comparisons for the restricted case of binary CSPs. Finally, we consider the application of decomposition methods to the dual graph of a hypergraph. In fact, this technique is often used to exploit binary decomposition methods for nonbinary CSPs. However, even in this case, the hypertree-decomposition method turns out to be the most general method.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589639$657986AA-6D30-4F19-8C90-32490F9ACFCE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf2726c5c2109371cc10358eaa69bc4df711caf7","datavalue":{"value":"68P15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589639$A52F630A-E194-47B1-97AF-5C301732DBC6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"32c61e02b5036793081b30a6c20682d525445f23","datavalue":{"value":"1542379","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589639$41A31C25-473C-4290-BDC1-0C8DA6C5DDE5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00fab533cd38d922e3a2c54a153ccdfb1b56ca89","datavalue":{"value":"constraint satisfaction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589639$8F2BF7EC-F793-4010-AC6B-7282162196ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b8894dbdfd3cb3d807881f7b26d08b6a31b97b7","datavalue":{"value":"decomposition methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589639$6EA9DE94-0D3D-4B48-A88F-697193E5A722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"370afb08886d454ad02a3e32ab188f88b9fed55c","datavalue":{"value":"hypergraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589639$EDBFC87F-83CB-478F-AB3C-2F8E694A0F14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f241116409f745de1649fa4f9ab9ac4030836d8","datavalue":{"value":"tractable cases","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589639$642238BF-C0F8-4208-9166-E53FD2EDF85D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88f898b7e123ec46c6abf6cb9931362a459aad51","datavalue":{"value":"degree of cyclicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589639$DE1E4045-69F5-4DD2-8D50-BFED8C19C370","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589639$01636BA5-EE13-4EE7-818C-0272D8BA60C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e1e21411b2f546a0087f38db49b740c02dc3cd8","datavalue":{"value":"hypertree width","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589639$4C01385D-8FA0-47BF-83BE-92C907FE5982","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68104529eb7057540cffab623968dd1e549a1d24","datavalue":{"value":"tree-clustering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589639$370DAE4C-6006-414D-9454-367D8E639594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"836241a6b1f4401a1c3e0909aac1205b2665c54b","datavalue":{"value":"cycle cutsets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589639$508E671B-A7F2-4DD0-93D4-79ADDB19C766","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8afed455d2696151af51258b4a000ac96ffbdf42","datavalue":{"value":"biconnected components","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589639$AB0C19E3-9CDB-42AE-B362-D86C3EAF2986","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1299dde63997c44826117bc839944756e768ab67","datavalue":{"value":"Q29307483","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589639$F27F1D71-E3E1-4109-81E3-BCAB16D48E73","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ea9f01e952d7c8681ab3cdbdd2dab7be8167564","datavalue":{"value":{"entity-type":"item","numeric-id":202112,"id":"Q202112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$E8489C82-88B5-4A25-958A-F80A112A66E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2cd7123f74d155fe14856de0656eddfe851c66cd","datavalue":{"value":{"entity-type":"item","numeric-id":202113,"id":"Q202113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$9A1ADC6F-D57E-42CB-ABC1-A9FAA58E94B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc4d4b989f90c820cd25ada1b68dde36e393eb05","datavalue":{"value":{"entity-type":"item","numeric-id":235708,"id":"Q235708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$F060E4EA-D695-40A6-9EF2-CBC06CDFF4CE","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":"Q1589639$B6818C7F-845A-45A3-9F91-5F72DAC14073","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"be17e3e16f8de4b41a5e87255873ed44ec5fd55e","datavalue":{"value":{"entity-type":"item","numeric-id":3361904,"id":"Q3361904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$D536B3EC-13D2-4313-9FD0-EE3A6BB9AE41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a08cfcc5870263a5c9ca63fbdf30de9c21f5aec","datavalue":{"value":{"entity-type":"item","numeric-id":3026382,"id":"Q3026382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$E53A65AE-4B6A-4F2E-9DCC-48CBB0CF1176","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6abb5793049c0ca9e0241cd2fd5c47ebc81d9542","datavalue":{"value":{"entity-type":"item","numeric-id":3923637,"id":"Q3923637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$A840B7EC-A2F8-4332-9FEA-2A1BB0E30E28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9703c24b151b9b38b497672ae809a670e20ec2e","datavalue":{"value":{"entity-type":"item","numeric-id":1103421,"id":"Q1103421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$694F162A-2B44-4DFE-8154-7BF3C6AA0985","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d92b7073011bb1b4985d7d526f565ba0b3fbd9f1","datavalue":{"value":{"entity-type":"item","numeric-id":4699283,"id":"Q4699283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$DC2CF372-CB87-4063-B21C-E26FFD796CD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d282279ed10065867947540e184390ea8509d545","datavalue":{"value":{"entity-type":"item","numeric-id":1575132,"id":"Q1575132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$880DF899-D88F-4D94-A98D-545AC5D9F1CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afc61a2037feef2b958c658698dd68bdb6481612","datavalue":{"value":{"entity-type":"item","numeric-id":1102137,"id":"Q1102137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$4F8112AD-8E1A-4513-8157-F4EAFD195EE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc5bdfe9e8ce1cefa466590964d38f16789200ff","datavalue":{"value":{"entity-type":"item","numeric-id":1116363,"id":"Q1116363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$D2FBCDF3-5BCE-4180-A55D-99939F57A940","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df1958ff7e040b608ab81be40fc268247c86c0f1","datavalue":{"value":{"entity-type":"item","numeric-id":3933756,"id":"Q3933756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$E285907E-10DE-4F89-9FAD-CCDD05B14B02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e807cad96e78d6ed80e9767e538b1f542dbf4d4","datavalue":{"value":{"entity-type":"item","numeric-id":3771663,"id":"Q3771663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$72E9392E-1599-4636-AA6F-2E1742F45328","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":"Q1589639$5AD2D964-0FCF-450C-A281-26DD9935DB5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aad642519e322667af4527c63aeeb0f1c37296b4","datavalue":{"value":{"entity-type":"item","numeric-id":3028374,"id":"Q3028374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$BBDC91C9-B7C7-4E6C-9306-473B199DBFB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b070b31c61fde77c5210fef036722178c213942c","datavalue":{"value":{"entity-type":"item","numeric-id":696962,"id":"Q696962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$EB74D536-9D6B-4A7E-B925-0CD7E582EC77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"223c1aa612e1b1b8ad964e00e4658b940816eba6","datavalue":{"value":{"entity-type":"item","numeric-id":1321054,"id":"Q1321054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$DD56CA24-FE2D-43D0-9957-8CBAABEA7C31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"215fd7f718e277ec69a088e44c413ed0b740deff","datavalue":{"value":{"entity-type":"item","numeric-id":4376981,"id":"Q4376981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$1725890B-7EB5-43FC-B50A-858C6CB93E3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1caddd34f077d456b01045d3541e659029d97320","datavalue":{"value":{"entity-type":"item","numeric-id":1591157,"id":"Q1591157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$AA9D0CE4-F764-4108-8E4A-3DA9C63DDBC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54104d31282fdbf4e787a5193ad720b7f1b36289","datavalue":{"value":{"entity-type":"item","numeric-id":3750150,"id":"Q3750150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$51D1EF0F-E6F3-4603-9C57-966FA022C356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6760c1a0ed84f473ebf9c19dbb4d05bbf42b9a5e","datavalue":{"value":{"entity-type":"item","numeric-id":3751592,"id":"Q3751592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589639$B8201E35-7F4C-41FC-8483-115BCF7E9626","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"20aad0478924ec888bcf290cc7d96c9815c419b9","datavalue":{"value":"journals/ai/GottlobLS00","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589639$E32AF061-3E4A-4121-AE28-BFEF6EDC8240","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb7026cb07f787e60098243f775a4bc2b67841cd","datavalue":{"value":{"entity-type":"item","numeric-id":3524172,"id":"Q3524172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3b61666d982bb57fef3d1ebb2018135dd84446d","datavalue":{"value":{"amount":"+0.8621520400047302","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":"Q1589639$8584F469-6E3A-4B65-8858-E64C25E322B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7ddd709bc8bcb2a480a28c16b1027f4263050a5","datavalue":{"value":{"entity-type":"item","numeric-id":969532,"id":"Q969532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb6616fa75f980734ada81230ed13eb77a6b0289","datavalue":{"value":{"amount":"+0.852022111415863","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":"Q1589639$5CA26AFD-26B1-4261-B698-813A2442486C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6b46dc098abde56abf3234cf23a72f9ae456de6","datavalue":{"value":{"entity-type":"item","numeric-id":5504703,"id":"Q5504703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be0ddb5c3061a64c6bdffd69056111d1651426f0","datavalue":{"value":{"amount":"+0.846316933631897","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":"Q1589639$EEB836C6-657C-4569-9FA2-565BD5CE3BA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48b9c9defd3e7aa12b534a33114ae8427323b55a","datavalue":{"value":{"entity-type":"item","numeric-id":5703916,"id":"Q5703916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f41fe40fe8692ee684d5189d2d634c5c7bb4f103","datavalue":{"value":{"amount":"+0.8423793911933899","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":"Q1589639$13CE65AF-A5CC-468C-BB35-B80A776195A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ecd65770ccf59af0034e62c8ff04e4340d3da27","datavalue":{"value":{"entity-type":"item","numeric-id":931717,"id":"Q931717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61fa0b1d14eaa8b31b94ac578a457f81b28c13d9","datavalue":{"value":{"amount":"+0.8199335932731628","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":"Q1589639$17D334F7-B81B-4EDA-88A9-C62CEC0A32C1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1589639","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1589639"}}}}}