{"entities":{"Q1028845":{"pageid":1030693,"ns":120,"title":"Item:Q1028845","lastrevid":69641043,"modified":"2026-04-13T08:23:52Z","type":"item","id":"Q1028845","labels":{"en":{"language":"en","value":"Evaluating a weighted graph polynomial for graphs of bounded tree-width"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5576445"}},"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":"Q1028845$C7C73A85-ABE7-41CC-A5F4-62D1E32D2408","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"06749e36e9a719185b0a5343129656a9a3f45f06","datavalue":{"value":{"text":"Evaluating a weighted graph polynomial for graphs of bounded tree-width","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1028845$DB780AD0-5EBA-4AB4-B253-88B59382C52D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2ebdac19325b3c0bee4316a7b4583c8d2e20c441","datavalue":{"value":"1209.05249","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028845$D95F6F7D-440E-415D-AF87-E287D8F5E23F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028845$B7C445CC-09A7-48B9-902B-B767E9BF639C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4b7fce5b7b399ac4add92aeecf381b606c94d340","datavalue":{"value":{"time":"+2009-07-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1028845$971BBA46-5640-4754-80FB-529722FB7992","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"869c158e204f17189a9b749863b1b8473633302f","datavalue":{"value":"https://eudml.org/doc/117522","type":"string"},"datatype":"url"},"type":"statement","id":"Q1028845$C73B7DDB-D862-4CB3-B89D-2D2716A1AA94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"8dbfc053e47ab83cecc660ff7a35f91248aefe2d","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r64.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1028845$9D81EA7E-70D3-4B0A-BEF1-CAC9A1C3DBC6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6affc361caad05dee2e83e6832761d1ed4f63597","datavalue":{"value":"Summary: We show that for any \\(k\\) there is a polynomial time algorithm to evaluate the weighted graph polynomial \\(U\\) of any graph with tree-width at most \\(k\\) at any point. For a graph with \\(n\\) vertices, the algorithm requires \\(O(a_k n^{2k+3})\\) arithmetical operations, where \\(a_k\\) depends only on \\(k\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1028845$101EF334-B8DA-4156-91B6-7F11065C8C7D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028845$7B321507-733C-4C61-8B47-9017A6ECF221","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028845$E21570E2-9DB9-4F12-9C16-3F94D6843647","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028845$79444764-E7E9-4E03-8881-B42BB919D90E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"daf739b5d7c8c47bb81ad0fbe38261afe773a24a","datavalue":{"value":"5576445","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028845$26D23D94-7FB2-47D4-9474-A5A10C3CD8B6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bf5a0e86ee5fc1c6662191d40866b670f7742aee","datavalue":{"value":{"entity-type":"item","numeric-id":412351,"id":"Q412351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028845$66124C06-ACBB-46D5-8AAD-5176215A8F12","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":"Q1028845$21E59717-1882-474C-BE02-7CD3752EF11F","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"ac79df5d8911ddc9f1e95cacf7e2fcb0b95df144","datavalue":{"value":"bafkreibphbkl73pttdsmsimriao4xgb3wspn4u3ybehskk77ewtaajhgja","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028845$C3A15F15-4B79-4C1E-A7BD-B124955C7951","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4efc42ed87593f2828937127842355ce8719d3f6","datavalue":{"value":{"entity-type":"item","numeric-id":4228207,"id":"Q4228207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64d7db0bcb1627929f465e768d4b325a8fec9421","datavalue":{"value":{"amount":"+0.8762961030006409","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":"Q1028845$4D247C84-B039-437A-AD2A-DEFEBDEEDE0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6a0e7c488cfdd46305d30820b803b90595bc6db","datavalue":{"value":{"entity-type":"item","numeric-id":1584397,"id":"Q1584397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ddb4e3578523c885152b505ae37d789f676ea5f1","datavalue":{"value":{"amount":"+0.8393591642379761","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":"Q1028845$9E432C40-E0CC-4836-B91F-FE608E2E9267","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a1be3ed7b0dff4a9597cdd2a5717a04a730a3b6","datavalue":{"value":{"entity-type":"item","numeric-id":3557008,"id":"Q3557008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec1f3fe34959e1d803c772093a6c0a10f56ea6ed","datavalue":{"value":{"amount":"+0.8200641870498657","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":"Q1028845$A45B433D-3D52-47ED-B0D3-511750AA6823","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b7ee46dfcd855ad3c7724c970b564ba2c10a5c5","datavalue":{"value":{"entity-type":"item","numeric-id":3639277,"id":"Q3639277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d8c308e83b6180ccd59b1ba75d9249c2f70156f","datavalue":{"value":{"amount":"+0.8163226246833801","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":"Q1028845$1EB2D677-5D0D-4149-B2FC-724A58D25815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce1c6b44728aec2706ab695049df4b20366ccc01","datavalue":{"value":{"entity-type":"item","numeric-id":634679,"id":"Q634679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5e7e8d64864b80c1d43af93ff90fec57d78e7aa","datavalue":{"value":{"amount":"+0.8079980611801147","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":"Q1028845$5510940F-F5C7-4AE6-88EF-90ABC3492C75","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Evaluating a weighted graph polynomial for graphs of bounded tree-width","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Evaluating_a_weighted_graph_polynomial_for_graphs_of_bounded_tree-width"}}}}}