{"entities":{"Q1877665":{"pageid":1888407,"ns":120,"title":"Item:Q1877665","lastrevid":48330499,"modified":"2026-01-04T09:32:53Z","type":"item","id":"Q1877665","labels":{"en":{"language":"en","value":"Minimal congestion trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2092835"}},"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":"Q1877665$5283582B-464A-428E-800F-F5166CD7C1E6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d312b775dd0848de57c94c67c32f78dc9c477a87","datavalue":{"value":{"text":"Minimal congestion trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1877665$3A22FBBD-A653-444A-A33B-41E0923AA430","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ccb945c3842e3067ae8218fa7bab84b418d1f441","datavalue":{"value":"1051.05032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1877665$3CEB5669-081E-4597-A83E-871F839E272D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$1309CE87-138C-4FE5-A52F-70675B8E9626","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dad9e6929b84d2aa86589bcc6be2d26ada8b5576","datavalue":{"value":{"time":"+2004-08-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1877665$B5F91AF3-7AB5-43A2-A92B-98B441FA7565","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4e96fda3c10972356eadeee5385fe714af6837ac","datavalue":{"value":"For graphs \\(H\\) and \\(G\\), an \\(H\\)-layout \\(L\\) of \\(G\\) assigns to each edge in \\(G\\) a path in \\(H\\). The congestion of the layout is the maximum over all edges \\(e\\) in \\(H\\) of the number of paths that use \\(e\\). The {tree congestion} of a graph \\(G\\) is the minimum congestion over all \\(T\\)-layouts over all trees \\(T\\) with the same vertex set as \\(G\\); the {spanning tree congestion} is obtained when we additionally require \\(T\\) to be a spanning tree of \\(G\\).  This paper gives a number of estimates for the tree congestion and spanning tree congestion. It is shown that the tree and spanning tree congestion of \\(G=(V,E)\\) is at most \\(| E| -| V| +2\\). Lower bounds on the spanning tree congestions in terms of the {isoperimetric dimension} and the {Cheeger constant} are also given. A \\(k\\)-regular graph is shown to have tree congestion \\(k\\). Also, several bounds are derived on the maximum possible spanning tree congestion that can be attained on a graph with \\(n\\) vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1877665$DE03C1B6-40FD-41EE-AD42-F50DBA28AFE1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1877665$407EB347-9D08-4CB9-88C0-2BB40D366492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1877665$54D9A6A3-A89D-45AD-B231-9C3EBDAF8D21","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"88869a039fafd5d1d9ac172978c446f8290885b1","datavalue":{"value":"2092835","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1877665$43CAD336-DDB6-4DA2-90B2-961D166DBDDB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1212d9f1381595a9ae5da1f9b2f814aef617f74","datavalue":{"value":"minimal congestion spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1877665$F749EFE6-28E8-4DF1-95F0-826C93E238C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53b446798f755473eb568368fd059c8380a39503","datavalue":{"value":"Cheeger constant","type":"string"},"datatype":"string"},"type":"statement","id":"Q1877665$2817CF4D-F468-4B49-A846-00BC52B15656","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b389a47d15052b94b2e43a608889bd60cb44cc4e","datavalue":{"value":"isoperimetric dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1877665$76FA4BB3-9B74-4758-9355-489608A8109B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5e91bb2a184cf60b30eaaf9faa2cba87f387c995","datavalue":{"value":{"entity-type":"item","numeric-id":394136,"id":"Q394136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$331DF99B-CCC6-4DA7-B441-B40DF6539FA5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eea1ea35de576c62b8101835521aa928ecd629a1","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$4258FF81-6EFE-469E-A014-D678294CC84E","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":"Q1877665$495D22FB-4F72-4FE0-AD37-D112993876E9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"86dda2d1a9889703da659383c6515ca4f25b1299","datavalue":{"value":"https://doi.org/10.1016/j.disc.2004.02.009","type":"string"},"datatype":"url"},"type":"statement","id":"Q1877665$4C3A8A63-9779-45D9-9D11-A347840033E0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c84e8562d7a5099b75354d4fe1ae99081c96a68a","datavalue":{"value":"W1968079464","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1877665$120CC9BD-187F-44DB-B843-BF82B1427C2E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ddfeba75ace0f57cbf6e9428d3a2341565c57d7","datavalue":{"value":{"entity-type":"item","numeric-id":1970694,"id":"Q1970694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$3DF699D1-CBC7-49F3-A5DB-61183376FA21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e7755b59f502e424fcc6a89b92ce42bdb4bba82","datavalue":{"value":{"entity-type":"item","numeric-id":2386083,"id":"Q2386083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$12DFE860-BB26-495B-87C9-2C7DC57B923E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0467fcc2fdace998bb0e2a4ae19f551426b71af0","datavalue":{"value":{"entity-type":"item","numeric-id":1103631,"id":"Q1103631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$16ADC009-3D6A-4D3B-B616-07A8B23B92B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09d12695d4a3731e56edebe1f68edf8feccbdbd8","datavalue":{"value":{"entity-type":"item","numeric-id":4398864,"id":"Q4398864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$BDE1C520-AA73-4399-A783-0AE707A5F327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bc219f0be77e66e91ea1a8fcd25d7f98f5a88bc","datavalue":{"value":{"entity-type":"item","numeric-id":1270769,"id":"Q1270769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$A722332E-8D07-46DE-AF1B-606849EC6933","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5890cccaa2e42ff79b9f0f2ee8067b4e5c008f8c","datavalue":{"value":{"entity-type":"item","numeric-id":3679205,"id":"Q3679205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$AFB33C5C-F975-46FC-BB1D-F06BF0E97D57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4579c9ed2f80d8c550c917bdc7d7ab51a80583d","datavalue":{"value":{"entity-type":"item","numeric-id":4039999,"id":"Q4039999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$E236E384-CB0A-42EA-BFB8-8E6A6F8DF358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d4b8048f6210c471ad38d88b52197aa2bd692d2","datavalue":{"value":{"entity-type":"item","numeric-id":4337503,"id":"Q4337503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$DD0EF39F-15D6-40B3-A195-372277AFA3D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c10ef6534007b5c94aecfd01692c781446b4ed82","datavalue":{"value":{"entity-type":"item","numeric-id":1117949,"id":"Q1117949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$2B2D24AF-3B9A-4525-8467-3BD3A8A43CA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dad2f02dee3722959f439e39af4548de7a2e2b6a","datavalue":{"value":{"entity-type":"item","numeric-id":4844486,"id":"Q4844486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$2D3715C4-0A65-4E41-9143-6709E214EA7D","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":"Q1877665$62E5A0BD-17B3-4E7E-BCB9-9D98E6F768D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2c594e9705e780a6a4b2b01479e5d5553e79570","datavalue":{"value":{"entity-type":"item","numeric-id":5572939,"id":"Q5572939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$6E412F83-2543-4F01-8F57-84484989B842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d18461bd83654f4f08d5e686a898268b52a8f90","datavalue":{"value":{"entity-type":"item","numeric-id":5937915,"id":"Q5937915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$A176F7E7-3227-41AC-8115-A93145846810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84c35c3c18100f10a76a9ef0d730325b542a65e7","datavalue":{"value":{"entity-type":"item","numeric-id":115238,"id":"Q115238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$FB894CF2-5669-4988-A05D-4EFA2DE50ED9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd3455b1bb7e74268c4da08a3f8ef98dc3987eb8","datavalue":{"value":{"entity-type":"item","numeric-id":1332484,"id":"Q1332484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$D85EDEE6-CD3A-4ABB-B106-0BB8EF80BC45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10540fe260bc097dcd60a8b84744008e5dd472b2","datavalue":{"value":{"entity-type":"item","numeric-id":751660,"id":"Q751660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$7F62A7D7-1FDA-4E05-90C3-408886433B7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b2dd397e6a6cf4d03acac1069f23f8962b690f5","datavalue":{"value":{"entity-type":"item","numeric-id":5936015,"id":"Q5936015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$A961B72C-38E6-46C3-B05B-4666C0847F25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e52e84b58e5d9b443e1b932c8ad2bf1495726ad7","datavalue":{"value":{"entity-type":"item","numeric-id":1585975,"id":"Q1585975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$1B4E7DDB-B558-4CA1-AA0B-B96792FC4A95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23f8e74c10d091ee61ff0f27173554e03c87c7dc","datavalue":{"value":{"entity-type":"item","numeric-id":1870065,"id":"Q1870065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$7F368D19-5AE5-4CBB-9327-6B27DE6D2618","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fe2d4aaf4bc944d2a24950698b2f3f2b60f8b6a","datavalue":{"value":{"entity-type":"item","numeric-id":2748499,"id":"Q2748499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$B29976CB-773F-428F-9187-0F011A05F154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2479aa030f634bd795c8918a967327496f5092d5","datavalue":{"value":{"entity-type":"item","numeric-id":3771641,"id":"Q3771641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877665$D5FC6644-1C8A-4C24-8970-78BB98600B91","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ef306eba600bdf0595151376428c83a081117204","datavalue":{"value":"10.1016/J.DISC.2004.02.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1877665$9F4E8D77-4F94-4942-8B19-D84563D99543","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"316c15198a66997b49a595ffbb8ba329dbca48d3","datavalue":{"value":{"entity-type":"item","numeric-id":1043936,"id":"Q1043936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e2665052e8d52fdf324b522a3d459dce00baa40","datavalue":{"value":{"amount":"+0.8897147178649902","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":"Q1877665$D8EB7B3A-4D8F-4108-B28A-F4D6C6B1CF42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee1e0a364cab24139481603e9f9aa68ec815e2d2","datavalue":{"value":{"entity-type":"item","numeric-id":2906358,"id":"Q2906358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a677de850a7c4faedd362bedbbcf93a12d224fc6","datavalue":{"value":{"amount":"+0.8642644286155701","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":"Q1877665$7949ED62-9E33-4C4E-ACD1-1DF0FA24643D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b564edda7d16e4f62000f5d5b16811ef88b6bb7","datavalue":{"value":{"entity-type":"item","numeric-id":952638,"id":"Q952638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af7f4497a5593271e348cd2f8268b87f198df8f1","datavalue":{"value":{"amount":"+0.8633910417556763","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":"Q1877665$C9E99696-85C8-407E-A131-AB454744E3C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db205fc996574811676cb5ec083cadb38a24cc59","datavalue":{"value":{"entity-type":"item","numeric-id":1045206,"id":"Q1045206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1752ddfa30b9bb00e3addd87bc8eb1de84f1380a","datavalue":{"value":{"amount":"+0.8572249412536621","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":"Q1877665$8D4A6F24-5E39-48A4-B7F5-7B16FCBC3428","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b68d648c9d4fd430410bc04915368a7a42e67d1d","datavalue":{"value":{"entity-type":"item","numeric-id":394137,"id":"Q394137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21b9922a78426f63ee16c9c2733be77a3263308f","datavalue":{"value":{"amount":"+0.8514081835746765","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":"Q1877665$18DC44F4-287F-459B-942B-F9850F124FE4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1877665","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1877665"}}}}}