{"entities":{"Q1062758":{"pageid":1073510,"ns":120,"title":"Item:Q1062758","lastrevid":66062313,"modified":"2026-04-12T07:16:52Z","type":"item","id":"Q1062758","labels":{"en":{"language":"en","value":"Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3915625"}},"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":"Q1062758$D1C6B874-8482-4E80-AF74-76CC0081FCB4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a303c2f10a18c2fe30a58c6910d620a9e2dd0e62","datavalue":{"value":{"text":"Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1062758$A8A62F3B-8262-49AB-AA5D-A558C894638D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"26191e8991ae4ee525fba5d88cbaa9c6f76f7cb9","datavalue":{"value":"0573.68018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062758$EFC8C0A6-C3CF-4706-8B4E-955ADA240556","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ce38bed62e209268977fafa896249533125d432e","datavalue":{"value":"10.1007/BF01934985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062758$D9A339A2-E2B9-4DFC-A991-67BF2D5E9B42","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"57b62ee012be02b7b149d7a5975d257a2f361b4e","datavalue":{"value":{"entity-type":"item","numeric-id":324652,"id":"Q324652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$068C3395-7C9B-4344-9CF9-9CDD9DD5983C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$D43D39C6-8F76-4E5D-B06A-136B468A7DB7","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":"Q1062758$847727AE-AC5E-47F0-A3F2-3E5599CF7A4F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"455ba71d42d1a621315b0aaf3891d0e11d83c4a4","datavalue":{"value":"The paper is concerned with polynomial-time algorithms for restricted versions of some NP-hard problems on graphs. It surveys the use of table- based reduction methods for solving combinatorial problems defined on graphs and hypergraphs of bounded dimension and for problems defined on clique separable graphs and complement decomposable graphs. Some examples illustrate the use of the methods described.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062758$AC78BB7E-B58D-49C0-875B-D7125351365C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062758$DFC157D5-A9BB-4036-96E5-26BFE1D5ED91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062758$CA766D99-02FE-4C20-B0BE-7DF990362E78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"24aafcf24a21bd70cd3b62d3f5f72a6d0d82d816","datavalue":{"value":"68-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062758$F075F16C-C4DA-4F37-AFA5-B6E9D66F8318","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"258591ebafb2c67352732a74f071c25c1125bf5c","datavalue":{"value":"3915625","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062758$F161934C-4146-46D2-AFE9-755D395B78CF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a92166f5adeebffc8c81c6abb980ed495030be8","datavalue":{"value":"polynomial-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062758$9FA219B1-F455-4EBD-9E98-D3759D019A07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca20218efd60b9bdfe1c15b4397bf6e91b7136b7","datavalue":{"value":"NP-hard problems on graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062758$17F1621F-BE2F-4229-B0BA-EBA0BA159FA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4e1d06f55edbd0f7c99039382ef337b2ee831c3","datavalue":{"value":"table-based reduction methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062758$2F1B3265-DD92-4796-870A-25BA897C2D02","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":"Q1062758$85B2B2AE-6BBC-4447-B2A7-761405B14D5B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$A492E864-0956-45BD-9681-EB6574D7B9F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c48ac94745ee4e50d47f881eb245fd96b78fa84","datavalue":{"value":{"entity-type":"item","numeric-id":3876780,"id":"Q3876780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$27A3EE11-E5C0-4BD3-906E-D8CD4986F6CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65b7df10e50543a35272ff7cb0beb183c498b5a8","datavalue":{"value":{"entity-type":"item","numeric-id":3334090,"id":"Q3334090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$18F5C043-96D7-4ED2-8CED-7DDC7C5DCBF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"184e4bf6104dca6f9ecd549a6b36ad541c46b076","datavalue":{"value":{"entity-type":"item","numeric-id":3042845,"id":"Q3042845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$5513A902-3E9A-4CF5-96C2-91D293465ACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf73aba229b23f389841856465d1ea7418d3ff2b","datavalue":{"value":{"entity-type":"item","numeric-id":3042417,"id":"Q3042417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$951A056F-A0DD-4BB7-BBD0-5D4D81C83CF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32a35cfc8f9a27bf32fd7d5c16650da6b4bbbd0c","datavalue":{"value":{"entity-type":"item","numeric-id":5625203,"id":"Q5625203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$DB2A2EBB-B89C-4AD6-AD3D-1435D40E3319","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"678e7a4be408fd6129f52f04fe687f74c25ca083","datavalue":{"value":{"entity-type":"item","numeric-id":2554881,"id":"Q2554881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$41602AA5-0227-444F-B7B8-9B8C8AE124CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$96F9B47D-D976-4726-915C-43DAE602C151","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c0e6b90c16ae5fa1eac19212a306cb84ffec72b","datavalue":{"value":{"entity-type":"item","numeric-id":5613969,"id":"Q5613969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$BF427AC8-2B46-4D1C-80E5-5FD07ED32324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df25916ae88cfd882e8cb6b5b5569c6957043ab0","datavalue":{"value":{"entity-type":"item","numeric-id":2394739,"id":"Q2394739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$6F0B7E36-7A66-48A5-B4F6-50444DB6DE3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3322157bf6a01189b1807437698fe608048635ac","datavalue":{"value":{"entity-type":"item","numeric-id":4167597,"id":"Q4167597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$11434688-B976-414D-B4D1-18321C866B47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93abefd43f60c4734d29bc653212ccc79b537d1c","datavalue":{"value":{"entity-type":"item","numeric-id":4165413,"id":"Q4165413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$2FCDDF78-126C-424F-BE33-CC43E1238093","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":"Q1062758$23D42346-BA75-4673-816C-150EEF9C772D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a75bd964d7ed7750fbed3c811ae6e56f673f406","datavalue":{"value":{"entity-type":"item","numeric-id":5905222,"id":"Q5905222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$DE1C8289-5CA9-4084-8F19-5980E1BE9EA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66420b49775113a4962c131a254f6f2ef559bdab","datavalue":{"value":{"entity-type":"item","numeric-id":82025,"id":"Q82025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$2A9D8B0C-C90B-45CC-9DB9-0A6EC82DFBDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a3f4f623c55f4103180bc7ed3e80e030c1afd8b","datavalue":{"value":{"entity-type":"item","numeric-id":2545884,"id":"Q2545884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$06B3F42A-2CBC-4969-A61D-400A38C0F230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e76d15f0e9844553eca361034c3e508123e3ba11","datavalue":{"value":{"entity-type":"item","numeric-id":1844861,"id":"Q1844861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$173435A9-8E26-4EB4-B834-407E6C56F4A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20b2b580ff6212d994da9a35b4fa1d9c0f475295","datavalue":{"value":{"entity-type":"item","numeric-id":4158780,"id":"Q4158780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$204381D7-06E7-45B1-A46E-4E570BFBAA3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e23f273863469871a199ac4a03061a146b588596","datavalue":{"value":{"entity-type":"item","numeric-id":3937164,"id":"Q3937164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$96FCBFE6-1CCF-43CA-8DCE-40C6473E5FCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c71680a4ab9e1f4beb0d4c1abad68c079fb9c955","datavalue":{"value":{"entity-type":"item","numeric-id":3945592,"id":"Q3945592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$69EA287F-4E79-415A-BCDA-38CFBDF8761E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39c83322ec89a0879c019f012ce18dfec20bc796","datavalue":{"value":{"entity-type":"item","numeric-id":1062072,"id":"Q1062072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$E50A7AF9-7ABB-419E-97DE-DA87FAE5B221","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad9cfae9fc9d02b6b7648a5f38f2a07226c5c18d","datavalue":{"value":{"entity-type":"item","numeric-id":3311677,"id":"Q3311677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$DED9C11C-A844-481F-916B-ED91EB84F949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67b9b8eafd1b87c89b391a5a966c0dde6e01b96f","datavalue":{"value":{"entity-type":"item","numeric-id":1149784,"id":"Q1149784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$2421C33B-3B7E-4AAC-841A-211D73492ABD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c20b9c062c65fa50baeb0cadac82aad397e032bf","datavalue":{"value":{"entity-type":"item","numeric-id":3960122,"id":"Q3960122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062758$9C742E66-5991-4A81-A854-DF647ED21975","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2c0533c39d60622530362fd1ba73316433bdddf","datavalue":{"value":{"entity-type":"item","numeric-id":3029044,"id":"Q3029044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"501f5fb7c4fd0645c985c5b499d4c42271f4bd13","datavalue":{"value":{"amount":"+0.7700448036193848","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":"Q1062758$68BB477B-5C9C-4CA2-89AC-FC4DD75A7C21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d43ba8f777784d77186190fd0a6f9d68b0a3a7f","datavalue":{"value":{"entity-type":"item","numeric-id":3789084,"id":"Q3789084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78e95d2d147e758d492f7176c825b514c364c762","datavalue":{"value":{"amount":"+0.7652019262313843","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":"Q1062758$D95F68D5-220F-4692-8D75-720438E8D8EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"706a41968fff52ed820ad56ee4399055b9c0303b","datavalue":{"value":{"entity-type":"item","numeric-id":1899445,"id":"Q1899445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e59df2d4b4ac6f7bcf5584518c04ebcacb0f9fa","datavalue":{"value":{"amount":"+0.7617716193199158","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":"Q1062758$A600D363-A8E6-41C1-A039-A83263EE4F31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6161aa5260c6e95651068eec571edc564671ede","datavalue":{"value":{"entity-type":"item","numeric-id":4407447,"id":"Q4407447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff3e2dfe66ee0202c62719151a2265dbaea71c24","datavalue":{"value":{"amount":"+0.7604564428329468","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":"Q1062758$F715E5E4-B680-41B4-BD4B-F9D3CC7E1B0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d51bcedbddd193fa414d6e14771039b2435f2b64","datavalue":{"value":{"entity-type":"item","numeric-id":3795218,"id":"Q3795218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe48e694e20575853febcd786bf189b21f8887d3","datavalue":{"value":{"amount":"+0.7576591968536377","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":"Q1062758$645832A0-2C0C-4F52-B583-FDF9A2D5777E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_algorithms_for_combinatorial_problems_on_graphs_with_bounded_decomposability_-_a_survey"}}}}}