{"entities":{"Q1087546":{"pageid":1098298,"ns":120,"title":"Item:Q1087546","lastrevid":69610857,"modified":"2026-04-13T08:11:33Z","type":"item","id":"Q1087546","labels":{"en":{"language":"en","value":"Most and least uniform spanning trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3987292"}},"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":"Q1087546$F2EF9C03-63DE-428B-B9DB-C07EF99DD660","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3781f51df0b3996fdde0bc00ba5d00728e4fb0e3","datavalue":{"value":{"text":"Most and least uniform spanning trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1087546$2CE826E9-A517-4693-BFB4-66E0F55ACC58","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7540bd492261a0cea2f4494854e85769a19917a9","datavalue":{"value":"0611.05014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087546$44EABE55-0B20-47C3-A7C4-B29FABC0A1E7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8e67d783a7b77a3cf303cf6f4b5fa993e2308eda","datavalue":{"value":"10.1016/0166-218X(86)90041-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087546$05C7EEF9-62F1-4192-8184-E8FBD7F0D3EA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"65069cdb8b49018e0d5e0a3fa3b3949f039aec1a","datavalue":{"value":{"entity-type":"item","numeric-id":797495,"id":"Q797495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$E82303A4-054C-4370-A37E-57201939A744","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ca552b5a09a951163fe2671a2056a7d7d226e25","datavalue":{"value":{"entity-type":"item","numeric-id":496638,"id":"Q496638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$07D1D48D-B67C-4760-BC95-8ED083C0C2ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"03fd981d5df261cfa2446e7ed1d18dfa2af040b2","datavalue":{"value":{"entity-type":"item","numeric-id":193678,"id":"Q193678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$DE379561-17CB-496C-B94F-BAADA742F80F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4f4e50ab5ff3e3fa6e97103b12136833b436f53","datavalue":{"value":{"entity-type":"item","numeric-id":181212,"id":"Q181212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$F1EFF61C-4EC6-42C7-A69E-FA366D9F2F32","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$D1FE4C29-D3C2-48F6-B0A0-474A4E3EFAD3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1087546$1DF773A4-7F98-442F-BB37-CA091D2FC9E5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6aa8273f4b064714b5286a36e86410d7e465cf5e","datavalue":{"value":"In so-called ''bottleneck'' combinatorial optimization problems, a family of structures is considered and one looks for a structure minimizing the maximum weight (or maximizing the minimum weight) of any component of a certain kind. For instance, the min-max spannig tree problem calls for a spanning tree where the maximum weight of any arc is minimized. This work enlarges the class of bottleneck problems by considering the difference between the maximum and the minimum weight of any component as the objective function. Both the problem of minimizing and maximizing this difference is studied. The corresponding optimum structures are called most and least uniform, respectively. Components may be single arcs or paths, graphs may or may not be directed and the arc weights may or may not be restricted to positive values. Some matroid generalizations of the above problems are also considered. In each case an efficient algorithm to achieve the optimum is presented or it is proved that the problem is NP-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087546$F5077469-22E3-46ED-AAA0-AC703FEFD81C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087546$B8EA0828-6CE2-4506-8354-428DF3750B0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087546$0F54866D-1082-49B1-8D72-EE0A2702E898","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"24a0c858fea83962249df6b0aafe1e1efe75e19e","datavalue":{"value":"3987292","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087546$F38B388B-CDEA-4832-AD9E-4DEFA666E3BE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c19618875f7636c5c2465af013a961e239d68cb3","datavalue":{"value":"most uniform problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087546$A0FAB6CB-C3B7-4F6B-986C-A043DB68E2D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"524c7b22314eadf6f64b82e5879f703528760456","datavalue":{"value":"least uniform problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087546$67B3D97E-E7AE-43DD-B393-9BC5E68EF9C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b3980944371d2685366fcd3eec7137cf22b69b4","datavalue":{"value":"spannig tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087546$F265E719-F6A0-4395-85BF-0FEF3C10844E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"970f22a1cf7be79036759afd1a3f62d34918a36e","datavalue":{"value":"maximum weight","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087546$0DF5515C-B0D1-4F2A-ADA6-ED5652ACB8B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b106b1757aa4404c6a2568637934e8223dc8a13e","datavalue":{"value":"bottleneck problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087546$9940CA50-48FB-4F6F-9326-BA51813FADDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a7f31cec88f406d409fcee4bf41761e384a305c","datavalue":{"value":"minimum weight","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087546$B197844A-9C7B-4F4A-977A-E931E793A18E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7487a113f1fa2782ed8a9bb347fe987d03f9bf2","datavalue":{"value":"matroid generalizations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087546$993E7BAF-A34D-4298-9FEF-3E31A7BBD5D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087546$1E280635-86E4-473E-9887-AC3FACE5741F","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":"Q1087546$09AB659D-3E77-41CA-AB57-D47727486DFA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d9e735882f0114d9d1bd74d7bde93766d995370","datavalue":{"value":{"entity-type":"item","numeric-id":4065051,"id":"Q4065051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$7667A238-D35A-4392-9D80-6A1FCB616F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffe42ca938ed45695f535521b2107403cef25695","datavalue":{"value":{"entity-type":"item","numeric-id":1244239,"id":"Q1244239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$4C48E1F5-48F8-47AE-B953-445000AD2859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c69f643afc2588f00853aa488b66a93d14f5911","datavalue":{"value":{"entity-type":"item","numeric-id":3867580,"id":"Q3867580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$771C540E-33E9-411E-9D0D-C44FB10C4156","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d3e3cfcfc5dd09ceb46d46d8e815e084d66a72a","datavalue":{"value":{"entity-type":"item","numeric-id":3875356,"id":"Q3875356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$BE43A4AB-9069-4A56-8591-27F8BBD6AD7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1701c665407ff1a73129fefbb37e79f959ac915","datavalue":{"value":{"entity-type":"item","numeric-id":4750668,"id":"Q4750668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$826FDA03-8807-43D9-A4DB-B102B6ED56C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1429168f0b2d0f7dd5b4fd410296014223f9b108","datavalue":{"value":{"entity-type":"item","numeric-id":1145635,"id":"Q1145635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$3A3BB1DB-E615-4911-8C83-D4FA77F920F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9afeda4b01a785cd32db6912e9332ad4a06d3a58","datavalue":{"value":{"entity-type":"item","numeric-id":3328310,"id":"Q3328310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$D849EEFB-29BB-45D6-B569-64A5C6B996C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a1b3a23bef9ff22b898fb87db53c1229f631a7c","datavalue":{"value":{"entity-type":"item","numeric-id":5735194,"id":"Q5735194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$AD2C853F-3C95-47C1-8A2B-0FD33A2B4548","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":"Q1087546$339FEBEB-4040-4972-8355-5E4D8A2B876E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$09FE1C44-3505-4977-8E66-32ACF3DB61B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b41ba5dbbeebdc581ab76ad621e30e64cd67c78","datavalue":{"value":{"entity-type":"item","numeric-id":760338,"id":"Q760338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$71ECCD3D-B5BD-4C19-8834-46F692A3E3AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b99fccc5587221386654e1df50027cf58bfe9ff9","datavalue":{"value":{"entity-type":"item","numeric-id":3775351,"id":"Q3775351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$1B6AAB0A-08C1-43BB-8F4A-BF88FCEBFAC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d43174c7ab07afeaa3b31e225b5979b424c52447","datavalue":{"value":{"entity-type":"item","numeric-id":3795467,"id":"Q3795467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$F91E46AD-D18E-4104-8591-2748E945A1B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"932383d1ac997ed208ef47dcb574b592efaf75b3","datavalue":{"value":{"entity-type":"item","numeric-id":4065031,"id":"Q4065031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$E9B38E02-39EC-412D-A3B3-C61EE64DB804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7598deaa60e33f46db1320dc1b85a677389b314","datavalue":{"value":{"entity-type":"item","numeric-id":4158841,"id":"Q4158841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$1C67A091-84E8-4887-87A2-D46B5D437BE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8635a293f0260693024421bcdf9d97cffc1890ad","datavalue":{"value":{"entity-type":"item","numeric-id":4010349,"id":"Q4010349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087546$84B921B2-E220-4639-8732-0F7719CCBF6E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c7758d88ac55b01abcefdc80ceafbb40fd8b6f5","datavalue":{"value":{"entity-type":"item","numeric-id":1102979,"id":"Q1102979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e73e71812a6ac4714b53bdea5800226a28207847","datavalue":{"value":{"amount":"+0.8697426319122314","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":"Q1087546$32B247BB-03A0-4441-B062-F18859F5D1B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df9420c0e988bf2a3f5d74aab4488f2c422030af","datavalue":{"value":{"entity-type":"item","numeric-id":3347915,"id":"Q3347915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"575767c5ce41fc5e14a2f5804f712338b4a7cffc","datavalue":{"value":{"amount":"+0.804980456829071","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":"Q1087546$2D6F255C-EA4F-49A2-84F8-196AF69C1ECF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3459102d0227c5f8f5363db0adc0775f93cfe320","datavalue":{"value":{"entity-type":"item","numeric-id":3799842,"id":"Q3799842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2bb6aaa5a1dd4699090f04908c8755793082380","datavalue":{"value":{"amount":"+0.8009327054023743","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":"Q1087546$D21A81D3-93AB-460B-AC8C-2330AEEF654E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99c3b31ac1780f8e960f53865379a09578c4a23e","datavalue":{"value":{"entity-type":"item","numeric-id":3140426,"id":"Q3140426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fe8440670d2d96538eee1746f6fbc2585067332","datavalue":{"value":{"amount":"+0.7917768359184265","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":"Q1087546$13B2C851-476F-4837-8758-705C084A6DE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8288da02405d41ef59f1aa448becdf9773e1e2d1","datavalue":{"value":{"entity-type":"item","numeric-id":3745296,"id":"Q3745296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a930c4756453f51257cda2f7f78f966a0962baf9","datavalue":{"value":{"amount":"+0.7883996963500977","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":"Q1087546$86A450DA-5110-44AC-81DE-A40A4FA2F27E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Most and least uniform spanning trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Most_and_least_uniform_spanning_trees"}}}}}