{"entities":{"Q6548028":{"pageid":14159182,"ns":120,"title":"Item:Q6548028","lastrevid":55673182,"modified":"2026-02-17T20:47:07Z","type":"item","id":"Q6548028","labels":{"en":{"language":"en","value":"Bounded-diameter tree-decompositions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7857947"}},"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":"Q6548028$89C3620B-C364-4A84-816D-45382BBCF065","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e07fbd876200332cb55be470c9129f81e97065db","datavalue":{"value":{"text":"Bounded-diameter tree-decompositions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6548028$E024D0DF-99FD-4C36-97A0-5CCA3C0E52FD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"84a8555b67c6b23fa0b4b81d144fd117edd2c5b2","datavalue":{"value":{"entity-type":"item","numeric-id":186190,"id":"Q186190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$ECFCD49F-495B-4BCE-AE41-C034ED08AA92","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":"Q6548028$EDBE659A-416E-4820-9595-B0F3F51F83E5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$C6542241-C4C4-415E-B03F-B6B7D1AFBAD4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"45e832027665a154275313064030e55fe57162e5","datavalue":{"value":{"time":"+2024-05-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6548028$AA50A690-EC07-4F0D-AC23-C25CEA32A1E9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a05d1863bcee68006dd43cc74abc612ff458ccae","datavalue":{"value":"This article addresses tree decompositions and five graph invariants. A ``tree decomposition'' of a graph \\(G\\) is a covering \\((B_t : t \\in V(T))\\) of \\(V(G)\\) where \\(T\\) is a tree such that for every edge \\(uv \\in E(G)\\), there exists \\(t \\in V(T)\\) with \\(u, v \\in B_t\\), and such that for every path \\(p\\) in \\(T\\) with initial endpoints \\(s, t \\in V(T)\\), if \\(u\\) is a vertex of \\(p\\) then \\(B_s \\cap B_t \\subseteq B_u\\). These sets \\(B_t\\) are called ``bags'', and the authors ask how small the diameter of these bags can be, as induced graphs (``inner diameter width'' or idw) or using the edge distances from \\(G\\)'s edge relation \\(E(G)\\) (``outer diameter width'' or odw).\\par Meanwhile, for a graph \\(G\\), a tree \\(T\\) and a map \\(\\phi : V(G) \\to V(T)\\), the ``additive distortion'' (ad) of \\(\\phi\\) is \\(\\max_{u,v} \\vert d_G(u, v) - d_T(\\phi(u), \\phi(v))\\vert \\), where \\(d_G\\) and \\(d_T\\) are the edge-distance metrics on \\(G\\) and \\(T\\), respectively. And the ``McCarty-width'' (mcw) of a graph \\(G\\) is the least \\(k\\) such that for any vertices \\(u, v, w \\in V(G)\\), there exists vertex \\(x\\) such that if the ball of radius \\(k\\) around \\(x\\) is removed from \\(G\\), no two of \\(u\\), \\(v\\), \\(w\\) are in the same component (if not themselves removed). Finally, for a cycle \\(C\\) in a graph \\(G\\) and a ``load'' \\(F \\subseteq E(C)\\), say that \\((C, F)\\) is ``geodesic'' if, for every \\(u, v \\in V(C)\\), \\(d_G(u, v)\\) is greater or equal to the minimal number of edges in \\(F\\) in either path from \\(u\\) to \\(v\\) in \\(C\\); let the ``geodesic loaded cycle'' number (glc) be the maximum of all cardinalities of loads of geodesic pairs \\((C, F)\\), \\(C\\) a cycle in \\(G\\).\\par It turns out that for any of two of these invariants, idw, odw, glc, ad, and mcw, if we called our two chosen invariants inv1 and inv2, there exist positive constants \\(A\\) and \\(B\\) such that for all graphs \\(G\\), inv1\\((G)/A - B \\leq\\) inv2\\((G) \\leq A\\)inv2\\((G) + B\\). In particular, for any family of graphs with a fixed bound on glc, that family will have a fixed bound on odw.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6548028$F59FAE90-2FEE-4D93-904F-154BA935AAB8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f4c2e453a383fe1e064f27e4ca3ff49f8a1646b9","datavalue":{"value":{"entity-type":"item","numeric-id":587174,"id":"Q587174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$F05E1588-9D7F-4E71-879D-6CC96432105D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6548028$EB3576D4-8AFB-441D-AB34-39EF37526BFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6548028$48F091CC-0FF3-435B-BEC1-9E72A9439690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6548028$6332929D-A1CF-4AF6-8553-E452D0A8AF39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6548028$7337F3F6-EFA8-44C6-82E8-934B1133EFB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6548028$4077E187-2630-488C-96C8-CEEEB5AEE747","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6dcb9e116ad2bc8b72e60f94e61fafc801518816","datavalue":{"value":"7857947","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6548028$6CEC2769-7A00-4A20-A779-620170EE6C84","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c44525982597a122b66318044ccd3dd49b468cab","datavalue":{"value":"additive distortion","type":"string"},"datatype":"string"},"type":"statement","id":"Q6548028$A9783CD5-A586-44CB-B145-0E6D691AD23B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc53a56e0199c21dfc56fdd1064d265ed4bc798e","datavalue":{"value":"diameter-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q6548028$89164BCD-2268-455C-8C8D-52C3F0B057E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1e9f5ed614d471bcb3cbede6b2352ac23cdb8a7","datavalue":{"value":"geodesic","type":"string"},"datatype":"string"},"type":"statement","id":"Q6548028$92E12DBF-31E0-4C32-AEB5-6A107A4769A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c48369a13f5a36d8f23b6b86aae50dfc447d79f","datavalue":{"value":"quasi-isometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q6548028$0AE7B9CD-1194-4AC7-A44C-F5E4B2F2B51C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a0073252dacd10c817f83ebbc24da5c2405f50f","datavalue":{"value":"tree-decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q6548028$18AC8488-A51B-4ABF-98B3-CC988D9F092E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0cb25f9a1c0424b8c453f78c2f5215d25d32a0b8","datavalue":{"value":"tree-length","type":"string"},"datatype":"string"},"type":"statement","id":"Q6548028$C2DF4DD4-03A3-4E07-8ECA-1640DF68BB80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b81b0e661ffd7a2b0cf4d74a6388abe874250e20","datavalue":{"value":"tree-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q6548028$94A8A82A-688C-4DF7-A338-A86E1CF74077","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":"Q6548028$1A22CD52-BFB0-4920-89B3-35D839B41E11","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2481164833747fead3de47abe9a03db3712ebec2","datavalue":{"value":{"entity-type":"item","numeric-id":2398916,"id":"Q2398916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$68915397-3B55-497D-BAEE-BE41F739DED3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28e9f141033e2da735477252dc7e99158fa858e1","datavalue":{"value":{"entity-type":"item","numeric-id":897004,"id":"Q897004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$1FFDACD9-872F-4613-8648-B70D68EF42F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"330c08d2e34632b34d8507a78c6591b2ab97cea0","datavalue":{"value":{"entity-type":"item","numeric-id":3177816,"id":"Q3177816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$251BB08D-5E62-484D-8D1A-ADB65B8F47DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d003e729c82f8198e1fd911612f801f918bf3e58","datavalue":{"value":{"entity-type":"item","numeric-id":664543,"id":"Q664543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$95A4B8B8-4C41-41F5-95A6-B6B2FBC02ECA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04a8d1405246635877333623ad8f4842cb823013","datavalue":{"value":{"entity-type":"item","numeric-id":2221926,"id":"Q2221926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$82918E60-A1F5-4B62-B035-8DE7C3C8BC54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfe9f7b632a5c8caaa02ec174ae8e6381abe2470","datavalue":{"value":{"entity-type":"item","numeric-id":722321,"id":"Q722321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$8C0EF8B0-F57F-45D2-B01F-4CF3B44522CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54ad3482b893f8e02ae5d587400cc8c64958b661","datavalue":{"value":{"entity-type":"item","numeric-id":2370441,"id":"Q2370441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$A0EAF450-85A9-4566-BA04-A6206FCACF4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9403e815bb9cfa5855234e76c11afdd57d1e9682","datavalue":{"value":{"entity-type":"item","numeric-id":6062661,"id":"Q6062661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$E04C4484-520C-498C-9EF8-A1DD46D2D8C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae0fcbe188a8e249a7f8c7ab5b74b16b1ee3aab4","datavalue":{"value":{"entity-type":"item","numeric-id":4443141,"id":"Q4443141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$4BCFE9AB-283B-4EFA-8873-6E6461E4FEDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fa76cb3067fa61059807a01637759d924a2f552","datavalue":{"value":{"entity-type":"item","numeric-id":2388865,"id":"Q2388865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$275BF5E8-D677-4747-B57D-9AE5B242141C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c0f6dd793166a567719b2fb5d958eb883aea03d","datavalue":{"value":{"entity-type":"item","numeric-id":1079583,"id":"Q1079583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$CDD16D1A-79DF-4292-AD1E-0D9CD6B490C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b458b2be72b5c58e48ba58f932b399980fcd81d4","datavalue":{"value":{"entity-type":"item","numeric-id":896001,"id":"Q896001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6548028$A33BAC4E-168C-499A-A8B6-2EC5588DE68C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a97d9e3f60b9ff88ce53ffe15a6d5bb01e0fe766","datavalue":{"value":"10.1007/S00493-024-00088-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6548028$3DDCDDA6-CFEC-40C3-B05E-04FA9C483C47","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32914fc5d8d371b96a68e1d8b140b490b51cb912","datavalue":{"value":{"entity-type":"item","numeric-id":4218147,"id":"Q4218147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0173ac7b7860041f1d6b6fc0d070bc0c951afedb","datavalue":{"value":{"amount":"+0.7837678790092468","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":"Q6548028$5BDA56D9-3244-45A6-BDC8-56EE695AF0AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a5ac34d8aae0c3d694883cc731da7a56432a01c","datavalue":{"value":{"entity-type":"item","numeric-id":2370441,"id":"Q2370441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c49ddb24f4d6bba760697cd904ba262ce2b72cf","datavalue":{"value":{"amount":"+0.7739026546478271","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":"Q6548028$A84EBF90-8C67-49D1-A884-847D1FE529FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8378d7f27f9bb08ab21ff9f3455ae272f24c83ae","datavalue":{"value":{"entity-type":"item","numeric-id":5741084,"id":"Q5741084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55c5aede8b8ed1f2a24d56ce2437dd104905d8f8","datavalue":{"value":{"amount":"+0.7482830286026001","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":"Q6548028$AD739D1A-E444-4D75-A26D-CD5D8EEEF4C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e669b11503ba8d972061fdb33f6060c47c90eba","datavalue":{"value":{"entity-type":"item","numeric-id":722321,"id":"Q722321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02c6c98a12c2be44924f4722274268d0b8b42093","datavalue":{"value":{"amount":"+0.7308573126792908","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":"Q6548028$AD59E6E7-318E-4024-ACD7-DAABD8B95EB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90fe4755c5242a4adc2b4f2ea2336aff2208dcdb","datavalue":{"value":{"entity-type":"item","numeric-id":2851524,"id":"Q2851524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b087254143525b9b7d61282afacb90b465ea5d54","datavalue":{"value":{"amount":"+0.7303334474563599","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":"Q6548028$2B749350-079B-445D-9E35-F925EDFA9685","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6548028","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6548028"}}}}}