{"entities":{"Q2111782":{"pageid":2122525,"ns":120,"title":"Item:Q2111782","lastrevid":57737106,"modified":"2026-04-01T04:31:48Z","type":"item","id":"Q2111782","labels":{"en":{"language":"en","value":"Min-cost-flow preserving bijection between subgraphs and orientations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7642887"}},"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":"Q2111782$EFA5E013-711A-488F-BDC2-30A8ABE2F711","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ae248bde4c7bfe04bb41b8a5e31a6977a9401a3f","datavalue":{"value":{"text":"Min-cost-flow preserving bijection between subgraphs and orientations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2111782$3F4F1453-D4ED-4FE1-8268-5BD456AD791A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cd1c5a3db86add21d48792b00403e95d3b532182","datavalue":{"value":"1506.05081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2111782$EB1137D1-2484-4FC5-B563-EC8ACE2091A1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1057cc97355135a5018b117aa5abe4aa392dd684","datavalue":{"value":"10.37236/10940","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2111782$2E4204B5-7D9A-4331-A29E-EDE38402D7FE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8d1c8f635a2820ec0fe2b37e668043db09056e77","datavalue":{"value":{"entity-type":"item","numeric-id":2111781,"id":"Q2111781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111782$1FB55605-4574-4468-A824-AE95A0F38B59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a4e68d27c2b7f74e6caa876203f2eade0f2f4435","datavalue":{"value":{"entity-type":"item","numeric-id":457826,"id":"Q457826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111782$C9ADBBF4-8DFC-4B67-963B-9F57B96127D8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111782$F9F39EB1-E270-4A6D-AA36-DFC67A39CCFD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"957af406b21c0dd147c281b56551aa32e3ad16a3","datavalue":{"value":{"time":"+2023-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2111782$F9D77FE4-FF0E-43C3-95B8-2ED3314CA076","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e835c410eb158ae6ac20fe071f7373af8bbd3916","datavalue":{"value":"https://arxiv.org/abs/2112.09250","type":"string"},"datatype":"url"},"type":"statement","id":"Q2111782$3BED56BF-A693-46E4-8C02-5620D23AAEC9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ab313744ed78183dc509d5bd97a2e4231220e292","datavalue":{"value":"Summary: Consider an undirected graph \\(G=(V, E)\\). A subgraph of \\(G\\) is a subset of its edges, while an orientation of \\(G\\) is an assignment of a direction to each of its edges. Provided with an integer circulation-demand \\(d:V\\to \\mathbb{Z}\\), we show an explicit and efficiently computable bijection between subgraphs of \\(G\\) on which a \\(d\\)-flow exists and orientations on which a \\(d\\)-flow exists. Moreover, given a cost function \\(w:E\\to (0,\\infty)\\) we can find such a bijection which preserves the \\(w\\)-min-cost-flow.  In [Electron. J. Comb. 20, No. 3, Research Paper P44, 18 p. (2013; Zbl 1298.05145)], \\textit{L. Kozma} and \\textit{S. Moran} showed, using dimensional methods, that the number of subgraphs \\(k\\)-edge-connecting a vertex \\(s\\) to a vertex \\(t\\) is the same as the number of orientations \\(k\\)-edge-connecting \\(s\\) to \\(t\\). An application of our result is an efficient, bijective proof of this fact.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2111782$D6BD4568-D42D-4145-87BD-56F565C407D7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6ffc362644ca7876fb8337c4e7378fca3f3c2090","datavalue":{"value":"05C21","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2111782$DAD498FF-956A-4D09-9F0B-6DBE52B38D10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2111782$0D9738EF-A6BF-40E4-9CCA-436B9F77423F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2111782$6175CFC1-C217-4BA9-BD8E-AC7A9B0F75BC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ce7a43c09b916886e33fdca863c1d73695a9f5f6","datavalue":{"value":"7642887","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2111782$9A91C0B8-CD7C-477D-9BC8-159F5595F4E6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b07fe4a26d03fdbe053565fb9c036f31df90a49","datavalue":{"value":"\\(k\\)-edge-connecting subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2111782$479C6E75-D73A-409D-B0CF-FFAE5213FDF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6fa12ae8a92385fa86abf9ca4f3b7d998b591510","datavalue":{"value":"\\(k\\)-edge-connecting orientations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2111782$3972B7F9-F38A-4C0F-9B55-BF7809FA14FA","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":"Q2111782$89B5ABBB-5FE5-4131-94FD-3716488968E1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f9456040111bd4994263f06d88419a561de3bff9","datavalue":{"value":"W4316038097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2111782$8F8A6395-1374-4123-9406-960CD042EFE7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7d3b9ea4191d0e8f38b85f31489e94d8e2e8043","datavalue":{"value":{"entity-type":"item","numeric-id":1010839,"id":"Q1010839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111782$71967251-EAE4-439F-A6B0-27F280A9C19E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4466e412628c87e0f897dd7fe15ffcda3043ccb","datavalue":{"value":{"entity-type":"item","numeric-id":1219300,"id":"Q1219300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111782$D12AF023-7695-43AB-8CFF-936C43CCBFF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111782$7B27DD7C-B1BF-4D90-A6AB-066BE2CC3F3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18fa18b88fbc2417a67b1552aa7c07c99fa5a03e","datavalue":{"value":{"entity-type":"item","numeric-id":2935519,"id":"Q2935519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111782$3C9E7398-B733-4111-9036-8B5192EFC05D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f64fe814393bceef05ecf53ea31d2243d2dae6bc","datavalue":{"value":{"entity-type":"item","numeric-id":396883,"id":"Q396883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111782$76D4E4D5-6FDC-4D71-92E9-5C042091F583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c99339ec96f53bc05e2deab0babe0eca87307031","datavalue":{"value":{"entity-type":"item","numeric-id":3275434,"id":"Q3275434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111782$CA575A61-A965-4786-A580-65543122EC67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7deea21eb23118fff2bb000dfee14764baccdef","datavalue":{"value":{"entity-type":"item","numeric-id":4454950,"id":"Q4454950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111782$E9113A45-490D-427B-BDB5-A2557BF42F5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa5f5448c92b03afe0ee9b9ec7d7ae88a567b335","datavalue":{"value":{"entity-type":"item","numeric-id":5774643,"id":"Q5774643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111782$A38382D3-26EE-48BF-AAF5-9B330DD10C1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa5d0cdb98837528d001d7d783c8350722956b36","datavalue":{"value":{"entity-type":"item","numeric-id":3330991,"id":"Q3330991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111782$217F7F71-EBA4-4B26-AF45-DAC21BCF2725","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"bc6c7a1d0cf0957e64ee60ed42ebe9b751c8f7f3","datavalue":{"value":"bafkreibreh7tlmu6zeeckrmq2cm5oqbzpkcpisol4mce5igotf4fh54pem","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2111782$FC5923CD-85B3-421B-AD50-93BCB3E586C0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8373b478201ffefaf1d238e0332a03f12a08939e","datavalue":{"value":{"entity-type":"item","numeric-id":6096813,"id":"Q6096813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d496f628c02fbaa58817d3118e565a229f2e1b4e","datavalue":{"value":{"amount":"+0.7370287775993347","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":"Q2111782$D9F99394-8B99-455B-BF90-D8DF48C527E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe058f24f27455753180ac12348843d3943e2edd","datavalue":{"value":{"entity-type":"item","numeric-id":4386300,"id":"Q4386300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f01a6f151ee9762f48e46c3931f6d6ba1ccd42a4","datavalue":{"value":{"amount":"+0.7338247895240784","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":"Q2111782$9438CF63-46A6-4027-A3DC-BAA74720B125","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ec811469f60b68e16372801a539d585920e0283","datavalue":{"value":{"entity-type":"item","numeric-id":5716201,"id":"Q5716201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f01a6f151ee9762f48e46c3931f6d6ba1ccd42a4","datavalue":{"value":{"amount":"+0.7338247895240784","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":"Q2111782$29AB9746-6F87-45FC-8219-FE113412D6D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de54645d9dae60528ddb256891b4af7751f10fdb","datavalue":{"value":{"entity-type":"item","numeric-id":5134324,"id":"Q5134324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5e4e0632750b6504cb4e453d8f8ac0e872d2b47","datavalue":{"value":{"amount":"+0.7253396511077881","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":"Q2111782$71CEFBDB-D827-4889-9ADB-F784C9423391","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70e9eaffbd8380662bff4ae92f3a5b65d7ca9970","datavalue":{"value":{"entity-type":"item","numeric-id":3697049,"id":"Q3697049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2430ec192c19a0cc47a85a666a1b5f0051f5965b","datavalue":{"value":{"amount":"+0.7198885083198547","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":"Q2111782$A46D4A46-CCF9-4EB5-88B8-CAFEC4142E8D","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111782$339707CA-7515-47E4-9E13-1E09FF81AD81","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2111782","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2111782"}}}}}