{"entities":{"Q1058995":{"pageid":1060843,"ns":120,"title":"Item:Q1058995","lastrevid":69534321,"modified":"2026-04-13T07:39:41Z","type":"item","id":"Q1058995","labels":{"en":{"language":"en","value":"On the complexity of recognizing a class of generalized networks"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3902427"}},"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":"Q1058995$C6DC2303-1B35-49EC-895F-9B7C79A2DAF0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2a160775258472d0bf28f8057ac8108efbe3a936","datavalue":{"value":{"text":"On the complexity of recognizing a class of generalized networks","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1058995$D9AC5E71-AF72-4E90-A8D4-E9028DEF632F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4d989f844c15bbac1dcb632bda4c70f52b44bc78","datavalue":{"value":"0565.90078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058995$4E134E7C-D227-4402-A0A9-00383778AF05","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"11dc79317c01d2a0d72778837f63e25d2236567b","datavalue":{"value":"10.1016/0167-6377(85)90036-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058995$6555D9F8-9855-461A-8478-F1C108164717","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"944eaafbd45c9ae73a50d6daf9410ee20734f178","datavalue":{"value":{"entity-type":"item","numeric-id":1058994,"id":"Q1058994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058995$136851D3-C60E-4851-B1DF-D14928B670A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c129f4888c20470ec7508e6617afd6aa87b5ce40","datavalue":{"value":{"entity-type":"item","numeric-id":751504,"id":"Q751504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058995$BA90F141-121E-4EA3-A774-C60EE81B4091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3dcab21441d0c16a4e960959e7900d7d14f24ae2","datavalue":{"value":{"entity-type":"item","numeric-id":170031,"id":"Q170031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058995$F2E34558-1F17-48BB-9C42-66BA07158880","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058995$065E6F21-AED6-43BB-9852-C34D19236D4F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1058995$15F442D5-006B-4B9C-B973-44AF95B6090A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1d2245f51fab26451b73282f561629384cc1822e","datavalue":{"value":"The problem of determining whether a given linear programming problem can be converted to a generalized network flow problem having no unit-weight cycles is shown to be NP-hard. The same argument also shows that the problem of determining whether a gain matroid is bicircular is NP-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058995$0073BCD7-5ED0-48ED-822E-446BF9FD3B40","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058995$99A99741-F19F-4567-BF78-C334262440ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058995$2D5F70A2-BADF-417B-A183-E959BD8C0F92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058995$02758079-C2A6-4DBE-BDDB-45C2DA203ED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058995$84A14EF8-CC39-4657-843B-BFEBF6A76E18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058995$2C2D6927-A80D-4F6E-A558-5B13B9CBC392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058995$634B537B-9C48-4197-9508-62D312786740","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3038de0773f18916a3e45d7b99fbdf1444363723","datavalue":{"value":"3902427","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058995$2231588C-D7AA-4ADF-ABB3-06F86C88E153","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"505dbb85aa01165c5edaebb690ddeb69548698f0","datavalue":{"value":"problem transformation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058995$C4F05D58-81FC-45A0-8DC8-831A359BA980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8276751dda601df177e9dc3270f8fe8af726d3b","datavalue":{"value":"problem equivalence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058995$FA1FE339-611E-4D0B-A841-4635A20C9404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058995$B4098117-3193-42BD-BB5A-04B08D52963A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79312ce0b9592d3ef20baf636f397d67d56f9b13","datavalue":{"value":"generalized network flow problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058995$216BF4AC-600C-4B90-8B1D-1D8DB87F54E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"baab42b8828767a96d0a3af43ade5f512a929e27","datavalue":{"value":"unit-weight cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058995$C194EEDF-1B64-4E49-AF38-2C0D5458C711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e172629663780e971698d7d841046893adba3be5","datavalue":{"value":"matroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058995$52B4D329-EE84-4AC0-B4CF-39D17B13D262","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":"Q1058995$29A647CC-DC66-48E4-A749-D9A36326AA1E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3b0008a3e00bdb7a05a0b4e1cd92fb1d3130e972","datavalue":{"value":"https://doi.org/10.1016/0167-6377(85)90036-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1058995$B7C454BD-769D-4322-B0D6-2AC43419586B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cc6ebddbc01c19a4e5fcee4a7963babde2019cf2","datavalue":{"value":"W2087699002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058995$DC06BFA3-9A42-4459-9941-11F947BE178D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea022308c2e9ea53b119c830963fd8056d7c2adb","datavalue":{"value":{"entity-type":"item","numeric-id":3885552,"id":"Q3885552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058995$E81ED3ED-7981-4E2A-BD53-2441C333F1C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21107a1715ab93a5c5e0aa5b524b63320bee928b","datavalue":{"value":{"entity-type":"item","numeric-id":579125,"id":"Q579125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058995$8DD2B6F4-3FF2-4058-A52B-02076AB75B15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058995$FC387D97-F1EF-471E-AB11-78810224541C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f12e6198b78831ce91556d24190a3c986ef0555c","datavalue":{"value":{"entity-type":"item","numeric-id":1142044,"id":"Q1142044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058995$74BFA87F-1AE0-4FA9-B711-644F3E1D0E21","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":"Q1058995$B4C67231-6B51-4D74-8A49-CB4CB722270F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d1492ebdc5b2ceb0ca4c85fc9ed7bee8f4792bd","datavalue":{"value":{"entity-type":"item","numeric-id":3968758,"id":"Q3968758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058995$CBA7E3CD-AC5D-4504-87CB-C0E4431CD057","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ef4a8da34066239ed7a122489499a2189cda29c","datavalue":{"value":{"entity-type":"item","numeric-id":4096689,"id":"Q4096689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058995$197D53FA-AC56-4048-BD79-0A56CD029404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ce2914c388114557b650a9ea05d85bde823197e","datavalue":{"value":{"entity-type":"item","numeric-id":1070236,"id":"Q1070236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058995$201A84F2-1401-464A-B5A2-299367667975","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ee6ba21410efd14ddd2a024a73c0ed4e5a2745","datavalue":{"value":{"entity-type":"item","numeric-id":4111952,"id":"Q4111952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058995$FB1D74B3-A4CB-476B-9945-6E43F73BDD97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5c00d6d3bb495d61503622c5425a16138667c44","datavalue":{"value":{"entity-type":"item","numeric-id":2936849,"id":"Q2936849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058995$E3B6B92B-4D5F-478F-A6F2-3C3530AFDB92","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86a272864571c1cd0a3cfa2ce35511f6f74d398a","datavalue":{"value":{"entity-type":"item","numeric-id":1208462,"id":"Q1208462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf3410d7f4cc7c5e479de86f653b3f328fc5f052","datavalue":{"value":{"amount":"+0.7980054020881653","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":"Q1058995$6E230BDB-671A-4DEC-9F60-42F2B260F2CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b77dfdea9785430c5e8f9351f53e4428698388ea","datavalue":{"value":{"entity-type":"item","numeric-id":3343725,"id":"Q3343725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1c6b25d120e1b8748b5ff875d2cfc470c921113","datavalue":{"value":{"amount":"+0.7953307628631592","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":"Q1058995$BD903B5C-32C1-468E-9742-FF5F1538FB26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1978c877f30018ae8cd00a2efd3d5d34f8963cd7","datavalue":{"value":{"entity-type":"item","numeric-id":3693261,"id":"Q3693261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a018254a30292a36ce3ee5a69bc2ba34b04437ac","datavalue":{"value":{"amount":"+0.7892638444900513","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":"Q1058995$9B16445A-FE4A-40B3-9CAF-24564332F72C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"813d100e71d0d8f5be288cab7b179a5c762f0226","datavalue":{"value":{"entity-type":"item","numeric-id":912110,"id":"Q912110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f11072a3d2c01c22f4ffe8314d1e5eceab9dba45","datavalue":{"value":{"amount":"+0.7877699136734009","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":"Q1058995$EE82071E-2456-42D8-B5C0-31EE8BC21C53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6b517366f06351308213e919e62463ce400ff87","datavalue":{"value":{"entity-type":"item","numeric-id":1308737,"id":"Q1308737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf196829111034eb22643aa4897c7b10bc62714b","datavalue":{"value":{"amount":"+0.7651636600494385","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":"Q1058995$E51B19F2-EABC-4DD0-847C-743332E8E322","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of recognizing a class of generalized networks","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_recognizing_a_class_of_generalized_networks"}}}}}