{"entities":{"Q875941":{"pageid":877789,"ns":120,"title":"Item:Q875941","lastrevid":65019582,"modified":"2026-04-11T23:46:47Z","type":"item","id":"Q875941","labels":{"en":{"language":"en","value":"Testing branch-width"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5143577"}},"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":"Q875941$4DBBB35F-8E2D-4D0E-B432-658DE7DACB88","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"45bc1013cf1a3092d91fad1b3d9c21f4d25cabf6","datavalue":{"value":{"text":"Testing branch-width","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q875941$E7D955DE-BECD-43AF-89ED-7BD5DC483783","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6c36c42111071cb9191ea566d8e9a02ee2ee8d51","datavalue":{"value":"1138.05070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q875941$9152C0F8-5721-4EF4-BA37-EAD6BCAD602A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6c9c8d991cb59f8bfb573d1c78b1770eda9953fc","datavalue":{"value":{"entity-type":"item","numeric-id":256976,"id":"Q256976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q875941$5DBC9B54-F32B-4D03-9FB9-AA2CC87EE265","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b7666b1aea36d852e5d73efdf8f9faa64e3f54f","datavalue":{"value":{"entity-type":"item","numeric-id":705887,"id":"Q705887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q875941$CDAFE313-8C42-4BB1-B728-E983FEEEA112","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q875941$1B8F61AE-E185-407D-90C5-539132A50BC1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d952bbb2d53d4bd5a9de3b9e090440b84b7e8929","datavalue":{"value":{"time":"+2007-04-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q875941$6D00A253-01D3-4FD8-B8B5-5B4C5EBEF865","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6eda131283aa2587ae47efb5ade2bedb8c41dd8f","datavalue":{"value":"A connectivity system is a pair \\((Z,f)\\) consisting of a finite set \\(Z\\) and a function \\(f\\) that maps subsets of \\(Z\\) to integers such that \\(f(X) + f(Y) \\geq f(X \\cap Y) + f(X \\cup Y)\\) for all \\(X,Y \\subseteq Z\\), \\(f(X) = f(Z \\setminus X)\\) for all \\(X \\subseteq Z\\) and \\(f(\\emptyset) = 0\\). Let \\(Z\\) be the set of leaves of a tree \\(T\\). Then every edge of \\(T\\) defines a partition \\((X,Y)\\) of \\(Z\\). Let \\(f(X)\\) be the width of this edge, and let the width of \\(T\\) be the maximum width of an edge of \\(T\\). Then the branch-width of the connectivity system \\((Z,f)\\) is the minimum width of a tree of maximum degree \\(3\\), whose leaves form the set \\(Z\\). Especially, the branch-width of a graph \\(G=(V,E)\\) is the branch-width of \\((E,f)\\) with \\(f(X) = \\left| \\bigcup X \\cap \\bigcup (E \\setminus X) \\right|\\), the rank-width of \\(G\\) is the branch-width of \\((V,f)\\) where \\(f(X)\\) is the rank of the submatrix of the adjacency matrix of \\(G\\) defined by columns in \\(X\\) and rows in \\(V \\setminus X\\), and the carving-width of \\(G\\) is the branch-width of \\((V,f)\\) with \\(f(X) = | E \\setminus (E(G[X]) \\cup E(G[V \\setminus X]))| \\). In time \\(O(\\gamma n^{8k+6} \\log n)\\) one can decide whether a connectivity system \\((Z,f)\\) has branch-width at most \\(k\\), where \\(\\gamma\\) is the maximum time to compute \\(f(X)\\) for an \\(X \\subseteq Z\\) and \\(n = | Z| \\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q875941$40E9F837-E03A-4810-9708-C17B5AF516A9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q875941$9FB4C9B4-99BE-49C6-AD2D-E8BBF7CC4A46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q875941$16788CE9-FEC0-4CA9-8A3D-6214D903FDE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q875941$88E29FDD-414C-4EDF-B228-AF22205503A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q875941$C9306F07-359A-4A83-9D5A-D25B8FC69217","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b607c45f37e249217fec9a632676b269266bb50e","datavalue":{"value":"5143577","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q875941$8D3D2981-E221-4449-8077-BC5A3D1C1355","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"125f848e824041bf43e11dfb5f43ae5c6f8f7ef9","datavalue":{"value":"branch-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q875941$0F97DBB9-B602-451E-9156-8D24B8CC4F9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d0f2378a494b1ff6e7d6d150deee08cac896b10","datavalue":{"value":"tangle","type":"string"},"datatype":"string"},"type":"statement","id":"Q875941$2D026926-F220-4038-A875-CC59903A6085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2601fad10ac141119be22fab139b3166ed4bb949","datavalue":{"value":"connectivity function","type":"string"},"datatype":"string"},"type":"statement","id":"Q875941$6404ACDA-03B5-4F34-9C8F-79656F0218A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"027947d7989dafa81df5c714724aa6886cd81996","datavalue":{"value":"symmetric submodular function","type":"string"},"datatype":"string"},"type":"statement","id":"Q875941$495103C0-038D-47F5-A374-B609CB862D22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f9e67e88bd2345300d0633b669f5623f033e3f99","datavalue":{"value":"rank-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q875941$B4E8FBCB-A765-427A-875F-7BF7F9C5A1F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8eaee2d943c7a918bd8d83c0e8e6e761cc8ea7e","datavalue":{"value":"carving-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q875941$4F942C4B-4DD6-4C19-8DB1-5F4F0C670329","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":"Q875941$AD997B17-6168-4B0B-BBBF-CB79DC1F5C1F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e6820e31b287a00a3ae416e39b692749a0ff9b4e","datavalue":{"value":"https://doi.org/10.1016/j.jctb.2006.06.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q875941$DEEE7F68-B67A-4DDE-8035-84E88AB856AD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3cb4d0223410ba3cbafeca8e110608c95300f227","datavalue":{"value":"W1993704152","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q875941$ED671A16-D5B2-4CDD-8B4F-AC9984214827","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d29c3edb437fe49bdce404fe379c64b6ca2adddd","datavalue":{"value":{"entity-type":"item","numeric-id":4571992,"id":"Q4571992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q875941$461F20D7-6411-4169-8CB8-9E95BDE5A0D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b669700049f587204adf7419534c5a3e94070f47","datavalue":{"value":{"entity-type":"item","numeric-id":5470690,"id":"Q5470690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q875941$0F1643EB-0039-4563-B3DA-42ECB3176AAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"295927bf2e5aa67e372bd1d56d8365ab655589ff","datavalue":{"value":{"entity-type":"item","numeric-id":5897543,"id":"Q5897543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q875941$36E3D9FF-FE6E-4A18-A957-99D55FA053D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e62926166610e171255ba7600cdacbb982331e7","datavalue":{"value":{"entity-type":"item","numeric-id":1179473,"id":"Q1179473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q875941$92491287-168B-45EE-953B-17349B69CA58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b42f01619235047e4cf6362bf5725564c6284fe","datavalue":{"value":{"entity-type":"item","numeric-id":1850505,"id":"Q1850505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q875941$2E9D36BC-FF95-4DFF-BCFE-47DB6E094127","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c14d9a61220e12304cae4b0bc137c861085cc53","datavalue":{"value":{"entity-type":"item","numeric-id":4472491,"id":"Q4472491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q875941$C9452512-ECCE-40DA-93FB-1F00B756A8D8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"137c6483cad965cfb51a3695b1a43552d0e19a63","datavalue":{"value":"10.1016/J.JCTB.2006.06.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q875941$82C1478C-7E23-4B2B-AED5-89E90EF4D0E9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07f8c693a78f2d4f207ab4d9f3e17d9c9e12729e","datavalue":{"value":{"entity-type":"item","numeric-id":2496203,"id":"Q2496203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"954832a79f4b884d515417d6f2031d321b69e844","datavalue":{"value":{"amount":"+0.7983500957489014","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":"Q875941$F56BC9F3-DF96-4988-A244-3EAC0FBB5554","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8d7b47070c99a607724aa6037054d6a356410b7","datavalue":{"value":{"entity-type":"item","numeric-id":4251049,"id":"Q4251049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfe4dbe6fac9757b884c94f2ba1b42db7faeb117","datavalue":{"value":{"amount":"+0.7802828550338745","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":"Q875941$49F8089E-B94A-4247-86D4-25FF375D6CED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42480abe2ce6a93293d80f0568dccde1cb6492bf","datavalue":{"value":{"entity-type":"item","numeric-id":6133165,"id":"Q6133165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f7d9e1b5dcf31c65bd2726d7c8f2876f9581535","datavalue":{"value":{"amount":"+0.7761879563331604","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":"Q875941$149E664C-D383-414A-A922-36A9DB064F95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d7a063cd3e4c6e1a167fa71cd9a6650e945a39a","datavalue":{"value":{"entity-type":"item","numeric-id":5470690,"id":"Q5470690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f247aa9e75e5141e5464bb7246d0263463851a8","datavalue":{"value":{"amount":"+0.7723938226699829","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":"Q875941$2DC9E009-C5F7-4768-9B4C-661BB89564D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02eeca17b62a02684c0e6294beeffba8674ea507","datavalue":{"value":{"entity-type":"item","numeric-id":4571992,"id":"Q4571992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06fe27fc2d7d3e6ad83969b3a761b70689dc5731","datavalue":{"value":{"amount":"+0.7721487879753113","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":"Q875941$038EE453-5BD2-4414-9557-0D990CC1EBC8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Testing branch-width","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Testing_branch-width"}}}}}