{"entities":{"Q4734768":{"pageid":6764345,"ns":120,"title":"Item:Q4734768","lastrevid":110814317,"modified":"2026-11-20T18:44:14Z","type":"item","id":"Q4734768","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4121438"}},"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":"Q4734768$286D32A8-C582-4BEC-92D2-D50342CC8AAF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bd1f46efbef2140699850be1b3e7c683275925cf","datavalue":{"value":"0684.68061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4734768$FD493906-2A1F-4D45-9DA8-D05D2668B69C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"670b2fcaa25bcf252136cb1718da6303f4912aab","datavalue":{"value":{"entity-type":"item","numeric-id":1363644,"id":"Q1363644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4734768$47EDE378-01CE-425C-8385-2B9A303EDD92","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":"Q4734768$170C8558-AEF8-4EC5-8404-A0716CF39175","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4734768$C6EC96CA-8FFC-421E-9AA0-31B58E33E25B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4734768$62727D0F-6F34-4F11-800E-C8F468204518","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f3d7f92439300dfc4449c38ea4edef55f1822194","datavalue":{"value":"4121438","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4734768$3F0A3C19-E1E1-4DD9-8E4D-CD040966E406","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b17e6e28d1a18f7a35b77cc1e7558e6f62021227","datavalue":{"value":"tree width","type":"string"},"datatype":"string"},"type":"statement","id":"Q4734768$3CEAC8F0-4026-4434-B7BE-A2AA50E3F452","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d05f1d908ad789449a8d56b6ccdc658c83adea34","datavalue":{"value":"path width","type":"string"},"datatype":"string"},"type":"statement","id":"Q4734768$8B980F1D-D13F-469D-9743-49CD96DB8496","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q4734768$BFD6B044-6648-49AE-A722-304361D54F23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q4734768$4D71B158-1CD4-4CC3-8316-59413D17F24C","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":"Q4734768$0024B7F7-3A01-490D-B845-5E0B988A86C1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5122387dbddefc2c48f38fba64573e5718c8d0d","datavalue":{"value":{"entity-type":"item","numeric-id":3735735,"id":"Q3735735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"647cc3bbd48794c3142135b6bf807e048e9e8be6","datavalue":{"value":{"amount":"+0.7843678593635559","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":"Q4734768$341BAB84-E56C-4AED-B89C-DD56F7D1EFF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8ff5e629e614bd4eeee1b64d73e50ad8cf963c5","datavalue":{"value":{"entity-type":"item","numeric-id":3358765,"id":"Q3358765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b428949cfdddf1412fb627d09465bb9ce1556f16","datavalue":{"value":{"amount":"+0.7785768508911133","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":"Q4734768$3EAC4168-ADC6-414D-B02E-76A6D01CC14E","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":"d33ddad895b846622402fe9fb23a7eb058ae43bf","datavalue":{"value":{"amount":"+0.775886595249176","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":"Q4734768$5029942A-2A0B-4A30-8AF8-DA0C14F175FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4988c8c3fcc8686751dd1179a13dcea06b4f1af6","datavalue":{"value":{"entity-type":"item","numeric-id":4864433,"id":"Q4864433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1b6e1433a339eeb1f782bc608e94ea957821e14","datavalue":{"value":{"amount":"+0.772805392742157","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":"Q4734768$70712655-4B1A-48CF-B97F-6F16F8DC6840","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":"dc4c708bd39c90170fb68c2cbf3a0b784c97cca5","datavalue":{"value":{"amount":"+0.7703559994697571","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":"Q4734768$D95AC332-CDA6-4F6B-B9CD-B6E4B35BC7A1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a3323d6752f3f90940f44200f7121ef546a80cb2","datavalue":{"value":"Eine Baumzerlegung f\u00fcr einen ungerichteten Graphen \\(G=(V,E)\\) ist ein Paar (T,\\(\\underset {=} X)\\) bestehend aus einem ungerichteten Baum \\(T=(VT,ET)\\) und einer Mengenfamilie \\(\\underset {=} X=\\{X_ t\\subseteq V:\\) \\(t\\in VT\\}\\) mit (1) \\(\\cup_{t\\in VT}X_ t=V,\\) (2) \\(\\forall \\{u,v\\}\\in E:\\) \\(\\exists t\\in VT:\\) \\(\\{\\) u,v\\(\\}\\) \\(\\subseteq X,\\) (3) liegt \\(t'\\) zwischen t und \\(t''\\) in T, so gilt \\(X_ t\\cap X_{t''}\\subseteq X_{t'}.\\) Die Weite der Zerlegung ist gleich \\(\\max_{t\\in VT}(| X_ t| - 1)\\). Die Baumweite eines Graphen ist die minimale Weite einer zugeh\u00f6rigen Zerlegung. Serienparallele Graphen, Halingraphen oder au\u00dfenplanare Graphen haben eine geringe Baumweite. Das Problem, ob ein Graph eine Baumweite von h\u00f6chstens w besitzt, ist (incl. die Bestimmung einer zugeh\u00f6rigen Zerlegung) mit \\(O(n^{w+2})\\) Zeit- und Spreicheraufwand l\u00f6sbar. Die Wegbreite von B\u00e4umen ist in O(n log n) Schritten bestimmbar. F\u00fcr ca. 50 bekannte NP-vollst\u00e4ndige Probleme wird aufgrund der Tatsache, da\u00df diese sich \u00fcber die Existenz von Teilen des Graphen definieren lassen, die eine Konjunktion lokal verifizierbarer (bzw. auf Cliquen verifizierbarer) Eigenschaften erf\u00fcllen lassen, gezeigt, da\u00df sie f\u00fcr Graphen beschr\u00e4nkter Baumweite in Linearzeit l\u00f6sbar sind. F\u00fcr die Entscheidung, ob es in G m dominierende Mengen gibt, und f\u00fcr die Bestimmung disjunkter Wege wird eine solche L\u00f6sung entwickelt. Verwandte Betrachtungen werden f\u00fcr die Wegbreite von Graphen angestellt.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4734768$3BDA058E-B9DF-4E29-A5FA-F9D0D3D8BD06","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4734768","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4734768"}}}}}