{"entities":{"Q653831":{"pageid":655680,"ns":120,"title":"Item:Q653831","lastrevid":63352362,"modified":"2026-04-11T12:17:51Z","type":"item","id":"Q653831","labels":{"en":{"language":"en","value":"Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5990603"}},"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":"Q653831$D3BE707B-6811-4B96-B4C8-642CD3AB1D73","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"39d56fba47fc03f30e9a7d12195da341b349ee70","datavalue":{"value":{"text":"Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q653831$0217DFB2-CADA-45A2-86BB-28728F31F25A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d7d77edd8cdc7b165323511beddd6bd803a8bd54","datavalue":{"value":"1240.68113","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653831$65522983-1973-411A-9E25-DE7074B146F3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce5c4e491743af757e6bac3568c5cf5e0b33a677","datavalue":{"value":{"entity-type":"item","numeric-id":653830,"id":"Q653830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$BF08D509-0C65-4586-8D30-3E019A59FDAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c036cc59d8136b1c1d330e12aacdea4899ce840","datavalue":{"value":{"entity-type":"item","numeric-id":293456,"id":"Q293456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$F6A8058A-E873-4D38-955D-541F29B76387","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1cd61dc54a904d4e6718a447d2843eceb30bc3aa","datavalue":{"value":{"entity-type":"item","numeric-id":178479,"id":"Q178479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$CA2FFE66-30B6-4470-800B-705BE8ABE057","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"85c6f6a91431ca12cca016abff9de72c021957d9","datavalue":{"value":{"entity-type":"item","numeric-id":627521,"id":"Q627521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$A6B173E5-DB43-4B06-B849-5212858DE0FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2eb6362a5c6cc16df5ef424b93e45118a98a956e","datavalue":{"value":{"entity-type":"item","numeric-id":187145,"id":"Q187145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$589760FF-7714-4277-9446-1E5D95FC3412","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e8bbffefd0dbcf64a3b305a130ac56fa48950b5","datavalue":{"value":{"entity-type":"item","numeric-id":2219707,"id":"Q2219707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$5FB37884-A56A-4A3C-AA82-00CDFFEADAFF","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":"Q653831$1C7CE19B-2CE1-43C7-A5A9-EEC06087892E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5e7c33876f49da64580f033b95b71f550b669c2d","datavalue":{"value":{"time":"+2011-12-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":"Q653831$588FFE15-3F8C-420B-B9CB-DA88FB5AC0B6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d9662abe7d372a49e983f8155a9ac17f399b6b93","datavalue":{"value":"In the edge-disjoint paths (EDPs) problem, a graph \\(G\\) and a set of pairs of vertices, called terminals, are given. The objective is to connect as many pairs as possible via edge-disjoint paths. Even highly restricted cases of EDPs correspond to well-studied important optimization problems. In this paper, undirected EDPs are studied, together with a natural generalization known as edge-disjoint paths with congestion (EDPwC), in which the goal is to route as many terminal pairs as possible subject to the constraint that at most \\(c\\) paths are routed through any edge. For \\(c = 1\\), the problem is simply the EDPs problem. In this paper, the hardness of EDPwC in undirected graphs is studied. The main result is that, for every \\(\\epsilon > 0\\), there exists an \\(\\alpha > 0\\) such that, for \\(1\\leq c \\leq \\alpha \\log \\log V/\\log \\log \\log V\\), it is hard to distinguish between instances where we can route all terminal pairs on edge-disjoint paths, and instances where we can route at most a fraction \\(1/(\\log V )^{(1-\\varepsilon)/(c+2)}\\) of the terminal pairs, even if we allow for a congestion \\(c\\). This implies a hardness of approximation of \\( (\\log V )^{(1-\\varepsilon)/(c+2)}\\) for EDPwC and a hardness of approximation of \\(\\Omega (\\log \\log V/\\log \\log \\log V )\\) for the undirected congestion minimization problem. Another related problem is the all-or-nothing (ANF) flow problem where each routed demand is allowed to be routed on fractional paths. ANF is a relaxation of EDPs. The last problem discussed in this paper is the congestion minimization problem in which the goal is to find the minimum value of the congestion \\(c\\) such that all terminal pairs can be routed. An \\(\\Omega ((\\log V)^{1/2-\\varepsilon} )\\) inapproximability result for EDPs, ANF, and node-disjoint paths on undirected graphs is shown for any constant \\(\\varepsilon>0\\). If a congestion \\(c\\), \\(1\\leq c \\leq O( \\log \\log V/\\log \\log \\log V)\\), is allowed in the routing, a hardness factor of \\( (\\log V)^{(1-\\varepsilon)/(c+1)} \\) is obtained (and a slightly weaker \\((\\log V)^{(1-\\varepsilon)/(c+2)} \\) factor with perfect completeness, i.e., when it is ensured that the instance has an edge-disjoint routing for all the source-destination pairs). Using standard reductions, these results are extended to the node disjoint versions of these problems as well as to the directed setting. A \\( (\\log V )^{(1-\\varepsilon)/(c+1)}\\) inapproximability ratio is proved for the all-or-nothing flow with congestion, a relaxation of EDPwC, in which the flow unit routed between the source-sink pairs does not have to follow a single path, and the resulting flow is not necessarily integral.","type":"string"},"datatype":"string"},"type":"statement","id":"Q653831$BA25E730-51F5-4DB3-B262-FB3E2CF57E46","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$974E19BE-A98A-4325-AD02-AB5CBB765648","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653831$DF3CFDF0-8EAC-45B9-809F-8B14AB3529E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653831$2AF0E581-3ECC-4C4B-9581-C0231FAF4FF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653831$D4A98C7C-8960-4AB0-A953-DDD89ABFE264","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6ffc362644ca7876fb8337c4e7378fca3f3c2090","datavalue":{"value":"05C21","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653831$FFC93B85-17E5-49C5-910E-B10C58838FD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653831$4331EC73-437E-47B4-ABC1-0C59AA62E8A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653831$842D7EAE-9535-441F-AE96-121FCF121F44","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a5cc24d6e93b71bb20f2090eb8ee2ba5e7e8d60c","datavalue":{"value":"5990603","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653831$D9791E62-2D3E-44B0-87D5-DDB81AF61FC3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c978d5080a26f9df914f2aed4c827713484cc3c0","datavalue":{"value":"disjoint paths problem with congestion","type":"string"},"datatype":"string"},"type":"statement","id":"Q653831$0ABE8BE8-6624-4AE2-8FA5-8D4FE4B33E2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be9847b5080561732e2df3fe2a5afade2166808c","datavalue":{"value":"routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q653831$400B81E3-6700-4637-BE3F-5A20E0262AEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84086ae2881b7933aab9262123a90fa3e99771a4","datavalue":{"value":"approximability ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q653831$EDFE93C2-01F0-4AD1-B30E-E1D13FF43FB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q653831$AAACE26F-C72E-4E80-B1C0-B6D6948AE450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88d4d94e4f7cb04320063f664166fa5ca067fe66","datavalue":{"value":"randomized rounding","type":"string"},"datatype":"string"},"type":"statement","id":"Q653831$9201D77D-8CE9-4F4F-A43E-92EAA154D718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcea8e5cc028b2546d1a82dc93619f7d910763e1","datavalue":{"value":"all-or-nothing flow problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q653831$F2078C43-AD56-4D88-80A5-C6088BA6F334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e294c35d02458ac0be96a20a1a82dc3005c85256","datavalue":{"value":"congestion minimization problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q653831$A0640D44-4CF9-4BE4-81E8-9233C082B1DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a348f9efcaabdd35d491583f05dde8d8e0eb673","datavalue":{"value":"constraint satisfaction problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q653831$D86C5F87-B579-4117-846D-7F122C2D34F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6b51c37a2365f3630442b4ed01a847c483b1237","datavalue":{"value":"multicommodity flow relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q653831$E3679E63-F907-4DC1-872D-2621E937FC90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ad22613fc54c36c8248580a6c672588e112aab2","datavalue":{"value":"random hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q653831$29FA7AB6-C46F-4175-B7B6-AE4ED9DF61AA","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":"Q653831$B08FE8F7-6D43-4CA7-ABED-34CB7D2A0682","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"24201bb15f5b91ea946e2f3c19b71c8c12f15dc7","datavalue":{"value":"https://doi.org/10.1007/s00493-010-2455-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q653831$DF8937AD-F6E6-4F1C-9068-39FC16C92635","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b862ff95b670b9eae15dfe336e658acf8c20a977","datavalue":{"value":"W2122997342","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653831$78DEA6E9-D7DE-4843-A904-54F92BEA4636","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"78df361f4f0565ce79a5d22c8249ba5b83be24ff","datavalue":{"value":{"entity-type":"item","numeric-id":3581428,"id":"Q3581428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$FA8B34A5-7339-4FAF-8964-EA0C6B26DA8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74b89bf88e5b182b62bd29103758c9762884caf0","datavalue":{"value":{"entity-type":"item","numeric-id":3581429,"id":"Q3581429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$1ACA760E-877D-4A10-B502-90F5EE05DA21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2a2d9ed6071dd0e2194907994000fc8d7c71fe8","datavalue":{"value":{"entity-type":"item","numeric-id":2931414,"id":"Q2931414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$446350E9-5D90-4017-872E-189CD76C81FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"066346d3f85d258fbd02e2c44432c52843acfdc6","datavalue":{"value":{"entity-type":"item","numeric-id":4388872,"id":"Q4388872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$50125C8B-A9A6-43AB-84AE-FA13FFA866CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86726a092e1c3dcd24fc6b8240970e860c671858","datavalue":{"value":{"entity-type":"item","numeric-id":4537731,"id":"Q4537731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$870F6421-78C9-46A2-BCB5-8D19DB75AA12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c670a268dc70af3c858595ce2a1b0511596e64a","datavalue":{"value":{"entity-type":"item","numeric-id":2757635,"id":"Q2757635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$50E43F85-88CF-4A8E-B589-CAAF9E33D19A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a389c27f5cc8ec7e168b365e02dd38608b3dd118","datavalue":{"value":{"entity-type":"item","numeric-id":3580965,"id":"Q3580965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$28B7E4D6-4B61-4C6D-A6B1-5720AC6E2134","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b10f51dd9991e8381aebd70b95cfd4a3da9438b5","datavalue":{"value":{"entity-type":"item","numeric-id":2931436,"id":"Q2931436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$E1C22259-ADAF-4507-8693-779B340D3994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d01bdd0dfc8813b08206b721e0c2ea36ed382e47","datavalue":{"value":{"entity-type":"item","numeric-id":3581391,"id":"Q3581391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$11F33729-6ADC-4882-B119-1720739C511D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d605d1694f0d3bcc9b52b0bf70655ff8acc72ec","datavalue":{"value":{"entity-type":"item","numeric-id":3002769,"id":"Q3002769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$2BF084CA-6E2E-4430-8012-51FAF9EFC752","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"937ae116b7fdbe072adfd8234134fcc94577207f","datavalue":{"value":{"entity-type":"item","numeric-id":4471352,"id":"Q4471352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$D04CBD3C-CBAB-4833-A664-677D7E1EAE80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dd02be46be2f85ee5a1cf3be08f09f801897f0b","datavalue":{"value":{"entity-type":"item","numeric-id":3580938,"id":"Q3580938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$866E49CA-8BC3-4F23-98CA-32698BF1495F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f860c822d150849de58cb13021a4c67632e4c4b0","datavalue":{"value":{"entity-type":"item","numeric-id":3549611,"id":"Q3549611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$38E1F8BC-3722-45AC-AC54-5ABAF47D4B98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2944680d9be1bbf82be438feb52f904d24769775","datavalue":{"value":{"entity-type":"item","numeric-id":4652625,"id":"Q4652625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$BBB0EF06-041B-43AD-AE3A-75990F2F140F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ce1b86400443e0ae20d58e94201235ac6cd7626","datavalue":{"value":{"entity-type":"item","numeric-id":5725269,"id":"Q5725269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$5698D18F-9D24-4378-B6CF-BDCE1A4AC5B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f162310378466468e1e5a21c200f8a44fd9da35d","datavalue":{"value":{"entity-type":"item","numeric-id":1069956,"id":"Q1069956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$3233596F-3344-42A9-B5DD-CCD9DF7C878A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c2045a7ec56e01f15e3eae4db248ef2b73a81db","datavalue":{"value":{"entity-type":"item","numeric-id":1132111,"id":"Q1132111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$CB22FE6E-DFAE-4943-9541-FB1A05ED70E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a95519225f29f990ef0bc75750edda1f58384478","datavalue":{"value":{"entity-type":"item","numeric-id":5387766,"id":"Q5387766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$8DFC0BB3-5FD9-4A70-B9D8-E15FD627178C","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":"Q653831$CBEB9ABD-3A67-4C2C-BE32-9DD4EAF324E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ef25dcaca47a5224dc8bf68ba789427e2dbeca8","datavalue":{"value":{"entity-type":"item","numeric-id":679443,"id":"Q679443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$275E8354-5717-4CF4-AAD1-F1DA78A98E7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be9eaff081fa0346426907bace79e10f38eeeccf","datavalue":{"value":{"entity-type":"item","numeric-id":5917535,"id":"Q5917535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$A40CD788-A072-4AD4-98CB-EFD89EFB97DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d294477451b4e4cf6da04717af8db29433f60eb1","datavalue":{"value":{"entity-type":"item","numeric-id":3002760,"id":"Q3002760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$B54D8ABE-B66F-44B0-BDDC-B3CD92A54D2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afda2e6fa57564a6ed691366eb6a9b9b66e0dd60","datavalue":{"value":{"entity-type":"item","numeric-id":4800393,"id":"Q4800393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$2B00A05E-5EB4-4888-8FCE-00854173C1FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31c938f3d673080655fa42607e9b0f1f90c6c848","datavalue":{"value":{"entity-type":"item","numeric-id":1273862,"id":"Q1273862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$0AD1100D-B6D8-460D-B183-79EFEE52F1F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9607381471dc0f116433ab85a72bcd324dfda9a7","datavalue":{"value":{"entity-type":"item","numeric-id":4231910,"id":"Q4231910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$DAA6A14E-E61E-472A-8E51-00B94251E3C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ab86b7398d637e303d156f59e322bc5f9b8edbe","datavalue":{"value":{"entity-type":"item","numeric-id":1354427,"id":"Q1354427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$D02866B0-2DFD-4FEE-BB6E-D0FDDAF009A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8fb3b6e080f74269765d5a8259f6d97eeca91ea","datavalue":{"value":{"entity-type":"item","numeric-id":3840354,"id":"Q3840354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$033C7BEE-652D-435F-B35F-42EF26B33803","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ab78561d0c2ea3f07476e2f06785c9df4d719fb","datavalue":{"value":{"entity-type":"item","numeric-id":2921712,"id":"Q2921712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$779749E0-0F71-4C48-A59F-2DB788782531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0611c8fede42ac100885c81ef1a90e51ba7e3b3","datavalue":{"value":{"entity-type":"item","numeric-id":1106724,"id":"Q1106724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$D524BC41-A7B4-4F9B-B07C-506841BD4511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc7c1b8cc24016a7c6b464cd2135f72b919e9781","datavalue":{"value":{"entity-type":"item","numeric-id":4388898,"id":"Q4388898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$0E6E655D-7F0C-4EAE-AA94-482C39C44277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6938dba8ab074bb35a73751ce72717af16278b0d","datavalue":{"value":{"entity-type":"item","numeric-id":3972953,"id":"Q3972953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$D4FD84B2-9D02-49A2-B197-8D9877857B3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c838b9c29403a30009bc371ef6955e3141c412f","datavalue":{"value":{"entity-type":"item","numeric-id":3191985,"id":"Q3191985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$40B47CF4-D739-4B4C-B01B-14457C666875","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f612a5df390348ef79d62d9d7ca747009a06f745","datavalue":{"value":{"entity-type":"item","numeric-id":5501283,"id":"Q5501283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653831$F9AF074D-D542-4DCE-B2A0-48B8E0B5F9FA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"216e40e1efcd4ade3df4d69205c0b85bd4774dd9","datavalue":{"value":"10.1007/S00493-010-2455-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653831$5B3D1EE1-26BF-4BAD-A28B-B2D3281D7D21","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9193ee8d05a8bd15e45497e055c7942be53b1b11","datavalue":{"value":{"entity-type":"item","numeric-id":5917535,"id":"Q5917535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8dda84bcc7f504ac18a046f374033e09f4b1b59","datavalue":{"value":{"amount":"+0.909221649169922","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":"Q653831$36079C1A-7271-454B-9FD9-9DEBF0E6ACA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e23a7092b23a2b280707b27d8cc8e88a060b687f","datavalue":{"value":{"entity-type":"item","numeric-id":3177821,"id":"Q3177821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"154d79be5ca1f2dfab7733ed7fce687dad6f2ac3","datavalue":{"value":{"amount":"+0.8813654780387878","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":"Q653831$419717F1-32AC-428E-85A8-E1FA6AB4AA1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf0b85af01c30bbd46e0c25ab2683af1e9bd47e2","datavalue":{"value":{"entity-type":"item","numeric-id":4962686,"id":"Q4962686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f01a128465c550e7272ba4620c1d8008ec78023","datavalue":{"value":{"amount":"+0.8697782158851624","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":"Q653831$5350F921-C5F0-4552-BA18-B70084510EAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9de5b5fa83c084bb2b5f751c5a60890065dcea5","datavalue":{"value":{"entity-type":"item","numeric-id":5890864,"id":"Q5890864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a09d960558ba5f771ea9f6d3ebbb92776318e81c","datavalue":{"value":{"amount":"+0.8691664338111877","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":"Q653831$FEB8779C-A6DC-4E94-85BA-FFCE4A7E2C82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0dd42f7aa52e4f81a72169dbf1ae755327048cc6","datavalue":{"value":{"entity-type":"item","numeric-id":3455215,"id":"Q3455215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a3e44c36b9a3fc9f043ef97063ef9ddfcc251b2","datavalue":{"value":{"amount":"+0.8681315183639526","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":"Q653831$83E079E5-F555-4FFD-90BD-A477ACD87B4A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Inapproximability_of_edge-disjoint_paths_and_low_congestion_routing_on_undirected_graphs"}}}}}