{"entities":{"Q1116705":{"pageid":1127454,"ns":120,"title":"Item:Q1116705","lastrevid":49254826,"modified":"2026-01-06T20:49:20Z","type":"item","id":"Q1116705","labels":{"en":{"language":"en","value":"Linear time algorithms for NP-hard problems restricted to partial k- trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4090821"}},"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":"Q1116705$E2AE1D5B-526B-4975-AB87-5018D8A7EB1F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"527a51dff17cb4e583196d5c4f248c51170facf9","datavalue":{"value":{"text":"Linear time algorithms for NP-hard problems restricted to partial k- trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116705$207EB7B6-5BDA-411B-B7AA-3F0A17FE529B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cba8d75a983b6d0013f786db7e5adea8cd2cf553","datavalue":{"value":"0666.68067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116705$F1112062-0B27-4124-BD5B-9EAB627CD597","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2058d0f80bf73c9538fbf1688a4f55847c47ea2e","datavalue":{"value":"10.1016/0166-218X(89)90031-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116705$D08740F5-B112-4ED3-A4ED-14E9C2D9E444","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":"Q1116705$D3ECA12B-09A1-409F-929A-3CA33D0AEB57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d176ad615a4e6a7168d3f60eb001c162327a80ae","datavalue":{"value":{"entity-type":"item","numeric-id":175510,"id":"Q175510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116705$00A9A67F-08E3-43FB-95AD-2164A2A9E905","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":"Q1116705$85BA0985-DFEE-4A02-9B97-D781BEAC24A1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1116705$7C7F734C-B002-403A-BCBD-64162F140447","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0fb1251a41249cee712fad9deb8119585e06beeb","datavalue":{"value":"We present and illustrate by a sequence of examples an algorithm paradigm for solving NP-hard problems on graphs resticted to partial graphs of k- trees and given with an embedding in a k-tree. Such algorithms, linear in the size of the graph but exponential or superexponential in k, exist for most NP-hard problems that have linear time algorithms for trees. The examples used are optimization problems involving independent sets, dominating sets, graph coloring, Hamiltonian circuits, network reliability and minimum vertex deletion forbidden subgraphs. The results generalize previous results for series-parallel graphs, bandwidth- constrained graphs, and non-serial dynamic programming.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116705$9C541593-3924-4567-8554-5501AAE2D7D0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116705$A0C2B34A-5227-4D9A-9917-F8461966CDB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116705$C49B9613-C087-41D6-8161-682707C4915A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116705$5ED48C65-38E6-4D30-806B-68C73F55821C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5a95d0325e6b9d1729971bfbc1e5aac8419ee71b","datavalue":{"value":"4090821","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116705$20A9A5F6-1C77-49E5-9054-10EC6494F192","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca20218efd60b9bdfe1c15b4397bf6e91b7136b7","datavalue":{"value":"NP-hard problems on graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116705$F1492985-FA27-4A11-86DC-4A51AC681171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e01cd63397d5a2053f9b0e3a01dc87e5a91c4a8","datavalue":{"value":"linear time algorithms for trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116705$DB86E8CD-BBC3-4F8E-B2C0-171391ED93C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c27024bc3112e6fbf1cca0a9a4aacb8e7e4a77e0","datavalue":{"value":"optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116705$4043BFF7-4284-4B6F-AD11-41B52192FE23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116705$86B32480-51AF-4F49-BA31-78E430149EAC","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":"Q1116705$C6C31FB6-372E-414B-B3D6-BE27FCEC8A8C","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e633e14c2fcf48d4c0202ab10e00bd4414ac3003","datavalue":{"value":"Q56141684","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116705$E7F94C67-2C38-4EB2-B68A-9BB734CAC8F2","rank":"normal"}],"P223":[{"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":"Q1116705$686BD840-22EF-4ECF-BEFD-6592CADABE71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"924e802243b4f51c1822e67211b88d08172a8079","datavalue":{"value":{"entity-type":"item","numeric-id":1062758,"id":"Q1062758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116705$16EABA59-C1A7-4181-8D96-E5F93B0D87F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98f763e865fb42b7a66d14c482658008165a710a","datavalue":{"value":{"entity-type":"item","numeric-id":3728922,"id":"Q3728922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116705$6015DFEE-1BDD-47DE-8AE1-0BDAB74CB7A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"770bb68de47752f527df3eb5fd0239815f0bd638","datavalue":{"value":{"entity-type":"item","numeric-id":3751595,"id":"Q3751595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116705$E28C5443-9EA0-42FB-B5A2-27F8F9E6B8CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d87478746e093073c1058b3d3f46e28a2e987337","datavalue":{"value":{"entity-type":"item","numeric-id":4728259,"id":"Q4728259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116705$DE4C28B8-CA2F-4AA8-A64E-1BFBC168BD46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdc25cbb648141cd33a4375961d870b7b0931a00","datavalue":{"value":{"entity-type":"item","numeric-id":2536444,"id":"Q2536444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116705$ACA195B3-12AB-40F1-9213-6DCF00AF2049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92112994480729c7855c79dcbbba9d177aba86ba","datavalue":{"value":{"entity-type":"item","numeric-id":3773922,"id":"Q3773922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116705$A1FACFDA-5276-4CAF-87E7-D4B57B7FCF4D","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":"Q1116705$841DBFD0-2D8E-4494-AF34-885453E1D54C","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":"Q1116705$04EF14FA-8EFC-44F3-8234-89DB3EF21B48","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":"Q1116705$BCC9AE30-FA55-49F6-B112-F71C83017BD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f3a345ac969991571213b2a34fe3bc06c137d18","datavalue":{"value":{"entity-type":"item","numeric-id":5896404,"id":"Q5896404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116705$E7042603-C070-4559-B71E-4AA4521FC6CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9bc3d2693967814a49d21c4474b191685c6ddae4","datavalue":{"value":{"entity-type":"item","numeric-id":3725545,"id":"Q3725545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116705$4CEFBC58-AF8B-4D9A-A9EC-13090E6D1975","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":"Q1116705$911D843F-EF03-4965-963D-410B167BF4C2","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":"Q1116705$6553E020-B1C1-400F-AD60-A64CC0C5F747","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":"Q1116705$748F5BE1-50B8-45D7-8D3E-275C1FBB4C04","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":"Q1116705$F82FB704-0F50-4CB1-BE7A-ED6D307E39AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff8466e8a6030720c56a95c18502dfb44c526f99","datavalue":{"value":{"entity-type":"item","numeric-id":3692864,"id":"Q3692864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116705$FDCA4271-1C63-4553-98DB-567BE180DF29","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":"Q1116705$045785A5-4098-420B-B332-E5BE431D52C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bd9653126c3310deaf3ad2b17670ad142db4d41","datavalue":{"value":{"entity-type":"item","numeric-id":3740231,"id":"Q3740231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116705$9ECFA184-FAB5-437C-9259-783699B7F27E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5282e2af6fb364e711b7a8fb3deb94d9bd219551","datavalue":{"value":{"entity-type":"item","numeric-id":3766846,"id":"Q3766846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"726a1ea94a771a0a072a1961c4a13fbff035b6d0","datavalue":{"value":{"amount":"+0.9265035390853882","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":"Q1116705$6B8D0072-F89B-4761-BF37-A69B04D89292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc048dc963a9290c84debec3ac0c13709f16e7b9","datavalue":{"value":{"entity-type":"item","numeric-id":3821601,"id":"Q3821601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00a7c77f316e02377d0875c9ebef98254ed9a470","datavalue":{"value":{"amount":"+0.8662247657775879","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":"Q1116705$26459C73-55B3-4979-B141-9E1B6A9AEEC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fbce7fcabf6ac497a07d9c1cddf2341168c5072","datavalue":{"value":{"entity-type":"item","numeric-id":3334090,"id":"Q3334090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa9e50eb2906c6964525e9d17a1e1597c288f17f","datavalue":{"value":{"amount":"+0.8642616868019104","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":"Q1116705$19437F4A-A601-4F29-869B-20944954261D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae8d8b1eccd8e9aae62568f1abb05c3edd598a5b","datavalue":{"value":{"entity-type":"item","numeric-id":5060153,"id":"Q5060153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79b94c0551dc35459a3f57f0704d7c01aeacf440","datavalue":{"value":{"amount":"+0.863405168056488","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":"Q1116705$E426E139-ACFC-4F37-B9B2-6F7289212239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a61042dba55e766d0f99d3bccdacdfe5b9371c56","datavalue":{"value":{"entity-type":"item","numeric-id":3751595,"id":"Q3751595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02c5a3d080eccaa3a1ae23b64fdb28e2ad8fe450","datavalue":{"value":{"amount":"+0.850196123123169","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":"Q1116705$C24736B1-E0E4-4D8D-BEC1-79F60FB7B3AC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1116705","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1116705"}}}}}