{"entities":{"Q1811121":{"pageid":1821863,"ns":120,"title":"Item:Q1811121","lastrevid":43340378,"modified":"2025-07-24T22:00:24Z","type":"item","id":"Q1811121","labels":{"en":{"language":"en","value":"Characterizing the flow equivalent trees of a network"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1925295"}},"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":"Q1811121$16AAC4B6-DBEC-48EF-8D15-7EA74AA6ED02","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5d9e079fc6bc946eb83c445335fbedebea5bb6b0","datavalue":{"value":{"text":"Characterizing the flow equivalent trees of a network","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1811121$3E3885F5-2CCB-4638-8092-2F4523B66C4C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6483d427027e092d5ac2e8ec4ced2036147912bb","datavalue":{"value":"1021.05024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811121$C0E39C5D-0ACF-4071-AC5F-3E08A64B1DB5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"097cd77c2a8ed897e17159703babdfc033d3c464","datavalue":{"value":"10.1016/S0166-218X(02)00501-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811121$0B00E745-A76A-4E8F-961A-19059E9DFE98","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":"Q1811121$464891B2-D503-4D6C-94EA-4DBDDB1864A7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ae38298a411e50615364cd6c80d7e0f949b3a896","datavalue":{"value":{"time":"+2003-06-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1811121$1BD51D01-43E0-4A50-96F3-C66AE2CF2F3D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"869613739494059b08666dcc3c90301f63f3fa11","datavalue":{"value":"Let \\(E_1,\\dots,E_p\\) be a partition of the edge set \\(E^c\\) of a complete graph \\(H = (V,E^c)\\). A cover of \\(E_1,\\dots,E_p\\) is a subset of \\(E^c\\) containing precisely one member of each \\(E_i\\), \\(i=1,\\dots,p\\). If each cover of \\(E_1,\\dots,E_p\\) is the edge set of a spanning tree of \\(H\\), then the partition \\(E_1,\\dots,E_p\\) is called a tree-partition, and the collection of all such trees is a tree-partition collection on \\(V\\).    Let \\(G\\) be a connected weighted graph with positive perturbed edge weights (that is, the weights of the subsets of edges of \\(G\\) are different). \\textit{R. E. Gomory} and \\textit{T. C. Hu} [J. Soc. Ind. Appl. Math. 9, 551-570 (1961; Zbl 0112.12405)] showed that there always exists a positively weighted tree \\(T\\) on the same node set as \\(G\\) such that the max flow value between any pair of nodes in \\(G\\) is the same as the one between the corresponding pair of nodes in \\(T\\); such a tree is called a flow equivalent tree for \\(G\\). In the paper under review, the author presents the ``compact'' (i.e. polynomial size) characterization of the collection of all flow equivalent trees for \\(G\\) in terms of tree-partition collections. Also, a polynomial algorithm that recognizes a tree-partition is presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811121$7EBB9D70-4E3F-451B-9DA0-6E2DB5882AFA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf552a6496a70699f2802e7f7eff6309238b43f4","datavalue":{"value":{"entity-type":"item","numeric-id":383766,"id":"Q383766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811121$70F8C75E-4853-4192-AE6C-86FD552B5383","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811121$CC2FDFE2-ADBA-4E89-8303-114922F679DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811121$8C2B8DB2-C50E-4A0E-887C-DE4B9A2B6829","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"163311a88640ad8a17f3c62f088f184d403e534a","datavalue":{"value":"1925295","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811121$E2544E5B-03FA-481A-B708-77110FB4CB28","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c328775408cb30d4646a12ed6718371917e6effa","datavalue":{"value":"max flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811121$F7D8DDE6-806A-4536-BAED-C045B7DE4318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811121$55BAFA45-EE44-4149-B8F5-CFE04F817199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1436851979751de4c37fd1f52ce66eb3fc964a64","datavalue":{"value":"flow equivalent tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811121$09114960-3E87-4FA7-91FD-7C42893CC569","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ff1ef44ac9a32152a02c08533e57178afe095060","datavalue":{"value":{"entity-type":"item","numeric-id":1103513,"id":"Q1103513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811121$FB13DADF-D3A8-4459-B69D-183BB1433C11","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":"Q1811121$06B1B239-1540-4904-8375-2D2092D1989C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"beafd09c79dfa9f43f527c7e484481f6934843d2","datavalue":{"value":{"entity-type":"item","numeric-id":3056948,"id":"Q3056948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811121$282BA492-D09A-408D-AA29-53CF9D389EA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e1fc2c6a2b2bacabb2cd2ad60440b182f5903d6","datavalue":{"value":{"entity-type":"item","numeric-id":3840854,"id":"Q3840854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811121$EF5AD952-31A5-4782-B1C4-5FBDE03F5913","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8396d8d81694d9207e42463cf8d371948e36190","datavalue":{"value":{"entity-type":"item","numeric-id":4073398,"id":"Q4073398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811121$1509F755-A55B-44E5-AD4C-B3BC18F3A575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c3f07a6a99cf5ac0cfbc187d64d34273b5155ca","datavalue":{"value":{"entity-type":"item","numeric-id":4371290,"id":"Q4371290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811121$6D98DDD7-602A-4180-ADC5-BD45C00E6FE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d49b17aa815d5cd4b57e7e054d4fb374b1472a1","datavalue":{"value":{"entity-type":"item","numeric-id":4939605,"id":"Q4939605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811121$D17FC823-C236-481C-95FE-096961672F1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1744afac4c45f065c4a9c50861775137377ee1b0","datavalue":{"value":{"entity-type":"item","numeric-id":3849459,"id":"Q3849459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811121$0ED64C89-0EBF-4C72-8257-CB9C811BA400","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82a9c8cc4cdcade87b9ccc515a00403d48d4459b","datavalue":{"value":{"entity-type":"item","numeric-id":5636776,"id":"Q5636776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811121$F43719C0-4ED9-426E-A87A-98FA92B0E6AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f879f118d39e858978a1451bfc36c1747e956157","datavalue":{"value":{"entity-type":"item","numeric-id":4742310,"id":"Q4742310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811121$117BC07B-52F0-48C1-96DA-08FAC2060D81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb8c15014e2ce921e9154dc859703b736262b19b","datavalue":{"value":{"entity-type":"item","numeric-id":3032277,"id":"Q3032277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811121$E8466194-B3C9-4037-8844-7290425B195C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc7527e7eb5e5b7912f06aa4114988da27cb61de","datavalue":{"value":{"entity-type":"item","numeric-id":1343494,"id":"Q1343494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811121$D9F54B3C-D35A-473B-873F-F39E4843F9E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1860b0031e2cbb9105661e4b1058c275782a39cf","datavalue":{"value":{"entity-type":"item","numeric-id":3135082,"id":"Q3135082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811121$43B2F7C9-25C0-4095-B8DC-DDDA66911294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9bb36bfa8ff9b999fd22009eb922d04862e30fb","datavalue":{"value":{"entity-type":"item","numeric-id":3967567,"id":"Q3967567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811121$4B3DC0C7-8721-413E-83B9-88D88723BBD0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5576522572a93c872f1133117ee68aad411c3f44","datavalue":{"value":{"entity-type":"item","numeric-id":6065288,"id":"Q6065288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01f01068d72b071134a4d204db1707a59d2c8d37","datavalue":{"value":{"amount":"+0.7614015","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811121$1C9F7590-8067-4148-8BE5-A68B8CA6E6C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10da9822b3a6183370f92d957835cee486455e7a","datavalue":{"value":{"entity-type":"item","numeric-id":3611470,"id":"Q3611470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76be132fb5679fe7c0e356067c2bf55e4d336f55","datavalue":{"value":{"amount":"+0.74086475","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811121$901A85D9-E7AA-46A6-A403-7AAE23B5BBAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d50dd544b92dcae35e7f41571c4aa71333dacf4","datavalue":{"value":{"entity-type":"item","numeric-id":325404,"id":"Q325404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0909c78c48e8df209d23f9d6a5a8b9b25657895","datavalue":{"value":{"amount":"+0.7408434","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811121$B92878B4-513C-4B7A-BC9C-766C8B61D494","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"593c4e34944fbe93f7757390cd240b346f134066","datavalue":{"value":{"entity-type":"item","numeric-id":4361177,"id":"Q4361177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"220c3925a6b4e36ccb4a6172503cf0c582a2b85b","datavalue":{"value":{"amount":"+0.7359193","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811121$FE51FD54-8075-4B11-B2A0-B48AA635E1C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6892cc283d6911a3b9daa1ab27a2af961373c746","datavalue":{"value":{"entity-type":"item","numeric-id":4368403,"id":"Q4368403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a966a60421c948b16df46aa7440c07beccb3fb58","datavalue":{"value":{"amount":"+0.73323727","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811121$1BC5F8C1-EE1A-4079-ABD1-F547A149F6C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38abe9df106a2bc88365f247e7b1cc7a48298d4c","datavalue":{"value":{"entity-type":"item","numeric-id":1413914,"id":"Q1413914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6a11d3b4141bf3b9351a31dfefc8162e2dbadb6","datavalue":{"value":{"amount":"+0.73304135","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811121$F48292D0-86BA-4649-90B6-DAD8C0156961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ddb90affb197ed25ccd14408bba3ca529366772c","datavalue":{"value":{"entity-type":"item","numeric-id":1200792,"id":"Q1200792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc240c7da21d2c4f4eff29ea3312e98e188840c2","datavalue":{"value":{"amount":"+0.7326651","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811121$63F0BE2E-FC79-4835-8C6E-7B1B7FF17668","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2dee932262b887b0917e6004641c888ce2ff7873","datavalue":{"value":{"entity-type":"item","numeric-id":845841,"id":"Q845841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22e7e125260e36f0e8d1bae8f724aab19b8d3a23","datavalue":{"value":{"amount":"+0.7311848","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811121$4A75DB0F-4051-46D4-9EA9-9453BE2B9557","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c89bdd39abf4bb48fa6bc12851496a4a6df7b31","datavalue":{"value":{"entity-type":"item","numeric-id":3511413,"id":"Q3511413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a361d8340d06ce6b0371536d5400aa5e6ae3543d","datavalue":{"value":{"amount":"+0.72985506","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811121$306CFF02-FA99-40F0-BB50-8392B9E78034","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1811121","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1811121"}}}}}