{"entities":{"Q1208462":{"pageid":1219211,"ns":120,"title":"Item:Q1208462","lastrevid":47149147,"modified":"2025-12-31T20:24:05Z","type":"item","id":"Q1208462","labels":{"en":{"language":"en","value":"Recognizing hidden bicircular networks"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 166462"}},"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":"Q1208462$971B995F-7C54-4093-AFD6-EF4752CC6D27","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d13c67428767f6b7a80b528dda506878c486316b","datavalue":{"value":{"text":"Recognizing hidden bicircular networks","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1208462$8A791708-7A1B-4C24-8643-C1B176E19BED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9b168064f5afa2cfe615bb4532d1fc0630de4091","datavalue":{"value":"0781.90089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208462$EB09CED0-6A06-44BA-A560-45E9159DC32B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"955e1dd7ec8fb343f7dd57d2563e047aaac4d03b","datavalue":{"value":"10.1016/0166-218X(93)90243-H","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208462$8049C11C-57D2-4B77-BE80-C6595303782C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4304002f78783010c19d830db830788617be8be","datavalue":{"value":{"entity-type":"item","numeric-id":251907,"id":"Q251907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$2C80E46B-AB0B-4399-8414-41F3ADE823B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"21bb8288589ef2671e05e2e3385b12bfd959a91a","datavalue":{"value":{"entity-type":"item","numeric-id":251906,"id":"Q251906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$D08A3C14-B3EE-4537-9998-09CA563605FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"66a05d3cec73c611e907f1d401669479dd6ceb7b","datavalue":{"value":{"entity-type":"item","numeric-id":229627,"id":"Q229627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$E8507AE1-81E0-4097-9C54-927135D33502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d22515e60eb595c922ccb211ff64d963b3c69e77","datavalue":{"value":{"entity-type":"item","numeric-id":1208461,"id":"Q1208461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$D70F7DD4-0325-41AB-A1D4-38BFC076DA49","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":"Q1208462$0FD2D728-835E-4189-9110-8EF88BFBA181","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1208462$88D26E61-2CBD-48A9-A890-AFB491FC7911","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0a2f45674da8537168764de82f0ff01f492c866e","datavalue":{"value":"A generalized network flow problem is a linear program \\(\\min\\{cx\\mid Ax=b,\\;x\\geq 0\\}\\), where the matrix \\(A\\) has at most 2 nonzero entries in each column. The authors present a polynomial-time algorithm for transforming an \\(m\\times n\\) matrix \\(A\\) of full rank into the constraint matrix of a generalized network flow problem provided there exists an underlying bicircular generalized network \\(N\\) whose generalized incidence matrix can be obtained from \\(A\\) by elementary row operations and nonzero column scaling. A bicircular generalized network is a weighted digraph having no cycle in which the product of the weights of forward arcs equals the product of the weights of backward arcs. Such a transformation is useful because generalized network flow problems can be solved much faster than regular linear programs. In this paper, the underlying graph \\(G\\) of \\(N\\) is constructed using an algorithm with worst-case complexity \\(m^ 2 n^ 2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208462$74B12909-2909-4E33-9773-A64FFED55FB2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208462$1321DBB8-FABF-420C-B821-EF674B919809","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208462$5BACE47A-B11A-40BC-BCBC-0BF21B104291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208462$68D00DD3-D7E5-43D8-B612-379AA33988BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208462$D5011518-81DC-4FEB-9C63-386627F2D520","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"772466e23f65811e4792a58a12ff09d79c338e5f","datavalue":{"value":"05B20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208462$AD8E6A4A-CD48-450C-8C7F-F17D8B8C0978","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208462$6D57F527-7866-454A-B549-50156268E129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208462$DA85032C-FD84-4CEB-8B05-EC7CE2DE2DAB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"affc5d8dbd791d0c409567c088689cf17d1f13f1","datavalue":{"value":"166462","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208462$65A31CAA-2CD1-4030-97BC-341ACE7FC1CA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26c620aaf949f0d997a632028f59ce3a935e5232","datavalue":{"value":"generalized network flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208462$34452CF7-E9DC-4995-8C03-1C8C3DB17E99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208462$DFE93A21-1DD2-4CFC-B0EE-57C1E12F4B84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ab74c6cd144e2452e52efb90c1499997f995ee8","datavalue":{"value":"bicircular generalized network","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208462$EE92F753-B810-4E3C-BC45-D91CB413A821","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1036338e57ff468c07842b36de9d1ae094bc8bd2","datavalue":{"value":{"entity-type":"item","numeric-id":1110542,"id":"Q1110542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$B84C1C42-A0C3-4B7A-9AEF-9A89CFF5CAAB","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":"Q1208462$0132E6FE-6064-4127-8CC3-F325A2296C59","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"809456f9b83efc4613dc33314f84ade88c3b6f77","datavalue":{"value":"Q59592655","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208462$D3363E97-EA96-43EA-B413-7A1A7DE02A21","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbad8fe81e26073464f6b85132be23a270ba588f","datavalue":{"value":{"entity-type":"item","numeric-id":3760253,"id":"Q3760253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$237D75BD-9737-4D8A-898A-D7A2B787C1BB","rank":"normal"},{"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":"Q1208462$BE74F8AA-6718-4906-9269-B42F8432D15F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5689fa65385b2c188bfb367432ebbda01751a974","datavalue":{"value":{"entity-type":"item","numeric-id":3800056,"id":"Q3800056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$1D8A3557-D03C-49FE-9CBA-72D8444BD9DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06d48f21b86acc37cbf2a178cbf59e7536f03c3b","datavalue":{"value":{"entity-type":"item","numeric-id":3875975,"id":"Q3875975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$81490AC2-91A5-4DD1-AD95-4A9C6CBEE8F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1aa89ab59c6f0a2f6fdee4d97fc0ba60ba0d2534","datavalue":{"value":{"entity-type":"item","numeric-id":1179188,"id":"Q1179188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$8E2ADCE0-056A-4A5E-9421-9374E1242C7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b244cb0340bacce9fbda5d3c658e590f6171652d","datavalue":{"value":{"entity-type":"item","numeric-id":2367405,"id":"Q2367405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$8CE17738-C609-4F6D-A695-196BD6AB1517","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":"Q1208462$88349AA1-3D29-496A-B35D-5811B1A8B362","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"740b7d8ada28ddb4663c917efe6c3e5f76516d4b","datavalue":{"value":{"entity-type":"item","numeric-id":3734141,"id":"Q3734141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$71563CEC-93E2-492E-A071-1A7BEE11060D","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":"Q1208462$7F043D02-93C0-4F29-99C9-45C753F40BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f19c0fea124b1e4d241c86907dcd3f62cf1eab81","datavalue":{"value":{"entity-type":"item","numeric-id":4166768,"id":"Q4166768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$BE7CAB7F-0631-4773-9185-05CE7BA8F88B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c733c31882f7865f225c48f5b8bde558111550e4","datavalue":{"value":{"entity-type":"item","numeric-id":912110,"id":"Q912110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$5B508B09-C253-41D7-AF68-DE8D2EEB8333","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e910e00272b68c5fd3866a8ce71b045f283e907","datavalue":{"value":{"entity-type":"item","numeric-id":1208462,"id":"Q1208462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$D092F5F2-4040-4243-AD56-4224E4B92BE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"256716341fa2304097119a075fc5d388b3c532e2","datavalue":{"value":{"entity-type":"item","numeric-id":2548961,"id":"Q2548961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$7E7D60E3-5738-4D57-A717-2E779589D318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b29b0c856c4bd4e3790fe737a87e449c0425f434","datavalue":{"value":{"entity-type":"item","numeric-id":1217718,"id":"Q1217718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$ACA6928D-C37D-4781-9EF5-8D07398B8F0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aafca11f6108c1682bc43bba0be14da2da95b8ee","datavalue":{"value":{"entity-type":"item","numeric-id":2548968,"id":"Q2548968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$957F0CDF-7B46-4F13-BAF5-192347E96560","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":"Q1208462$0CD225A4-2ED4-4577-A026-345036F13B5B","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":"Q1208462$485C983F-79E9-4D64-9E10-C03FB380B7A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ccd6715b3f65ae04291a6db4d8b9a00187f4bc1","datavalue":{"value":{"entity-type":"item","numeric-id":3669431,"id":"Q3669431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$81FC8B4B-E2CA-443A-BCF0-40F5B5AFEB99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94d63c9c78c92e7451a854f7d460a73fd448775a","datavalue":{"value":{"entity-type":"item","numeric-id":1160198,"id":"Q1160198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208462$86CC5514-EDCD-430B-B684-B379A0130C27","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db17f77bf12abc5d768965a039ab9479b7ece9f5","datavalue":{"value":{"entity-type":"item","numeric-id":4390652,"id":"Q4390652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a00a860aff5f9fd12889c1019b99645eb9d7df48","datavalue":{"value":{"amount":"+0.8332162499427795","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":"Q1208462$DE7CAB64-7EC9-4F1E-A860-6A774E568A1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a3d1032ecf995219e689b1671388bb3761330f6","datavalue":{"value":{"entity-type":"item","numeric-id":2757524,"id":"Q2757524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a00a860aff5f9fd12889c1019b99645eb9d7df48","datavalue":{"value":{"amount":"+0.8332162499427795","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":"Q1208462$DDE1D28B-393D-472E-B3AB-97B3A39FFCA1","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":"ad640c76fc41ee0254843a922096adf44455966c","datavalue":{"value":{"amount":"+0.8278595209121704","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":"Q1208462$76E3ED37-93B8-4064-B0BD-DDEAE959C4EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ec5bfa19d30b9f53a7561ff5fc19635851374c2","datavalue":{"value":{"entity-type":"item","numeric-id":1058995,"id":"Q1058995"},"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":"Q1208462$3D8A87D8-6F84-4DD2-81F6-DE885CCDA3C1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1208462","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1208462"}}}}}