{"entities":{"Q1923587":{"pageid":1934329,"ns":120,"title":"Item:Q1923587","lastrevid":46394478,"modified":"2025-12-24T17:02:22Z","type":"item","id":"Q1923587","labels":{"en":{"language":"en","value":"On strongly connected digraphs with bounded cycle length"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 933102"}},"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":"Q1923587$CB862A9B-C510-4C9D-9BCF-AC5A29B9CDE6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"17cd9343cae19372f3a216cf954dc8519b1aa7c1","datavalue":{"value":{"text":"On strongly connected digraphs with bounded cycle length","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1923587$6343FEBC-5BD8-40CB-9EE1-433F8B59C887","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"737c927b77a791b675610a6431271cc18270c414","datavalue":{"value":"0859.05057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923587$C3F947DB-0A16-438F-AABE-306A1B338AF6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1ce8be51c74e5c37cc42eca4bc99b344df99f072","datavalue":{"value":"10.1016/0166-218X(95)00105-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923587$6E0DDB90-7B5C-4F79-8649-3AB981EE05BE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f496316b317a1071c5b5dfba5a175583d61d254d","datavalue":{"value":{"entity-type":"item","numeric-id":194031,"id":"Q194031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923587$ABB6A889-ADB4-4C81-88EA-34F0689391E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8dfa84db11a180db135dbd3dcd59aa7a291f852","datavalue":{"value":{"entity-type":"item","numeric-id":1026236,"id":"Q1026236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923587$930016CE-FC58-4B7D-8EBA-C5F444829F4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2025d27ed226beca4e83850bfb90b5799a2e527d","datavalue":{"value":{"entity-type":"item","numeric-id":290247,"id":"Q290247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923587$4108E5C2-36D5-403A-8324-9D8A5B4F8975","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":"Q1923587$A0BF37C0-5A55-4408-B1D4-608D29BC5883","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"987a2f2e82526aa2085dc97bf2e88574c6b234f8","datavalue":{"value":{"time":"+1997-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1923587$B7D2E65F-8F9D-4677-87F0-61D3731D914A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q1923587$9B570D28-4DF8-4DCF-BF4B-6646EC64C172","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6806dd3a8b9771fbf6b18c9bbf7157f65a468b41","datavalue":{"value":"Let \\(G\\) be a strongly connected digraph with cycles of length 3 or less. We wish to find a strongly connected spanning subgraph of \\(G\\) with the least number of edges. The authors show that this problem is equivalent to the minimum bipartite edge cover problem. This equivalence allows the authors to improve the performance of the best approximation algorithm to the general problem with no cycle bounds.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923587$8E2F7944-1893-4AC8-918E-61BD89211F2E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf8837edd6f8e1022b15c3d0748921656854f53e","datavalue":{"value":{"entity-type":"item","numeric-id":1811077,"id":"Q1811077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923587$DFDD43B7-C884-43D6-9964-3131A903ADE6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923587$98DFE4BD-2307-42DB-8B07-155CBA898D4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923587$80E09D40-1AE9-4B19-93CF-28E76614FE0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923587$B1138E4C-4807-447C-9F59-48A1F4CEFDFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923587$0DBF678D-DFBC-498A-8D50-806634C11064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923587$E16394E9-4D48-4DB5-828B-FF3D49204FE6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e77289f777a891dc9d6d5bab0bbd190cc4beac92","datavalue":{"value":"933102","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923587$E4192A90-EA6E-4DC5-A9A0-1B0ABB86AA4A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3842779000597abe3dc3cef2451250276bc01d5","datavalue":{"value":"maximum matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923587$F4F84C7F-C7A2-4805-9C1D-1E6ABC0D736D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e006f56fa7ddece386990be346ad42f4a8e6b62f","datavalue":{"value":"strongly connected digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923587$572F3B5E-9325-4D89-A011-C815ECC304AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a239cae0219351c76c4a6acdeee7ae40dfcc085f","datavalue":{"value":"minimum bipartite edge cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923587$891451B5-5B08-4611-8FF5-3651CFBE45E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923587$75D7C77A-C8A2-4C5F-9B70-0557689B7680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ae6cc52b35d03b83d5162d854c61cf5b039329e","datavalue":{"value":"cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923587$84E3A6CC-60C3-46F9-884E-4C2A655EE7D2","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":"Q1923587$930C7FB1-93A1-4171-B085-B6C5A1986AC5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"52b37db1f75b1fe2bd91d3915bec89ade0194420","datavalue":{"value":{"entity-type":"item","numeric-id":5659571,"id":"Q5659571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923587$E5AA00B4-C943-4132-8525-5EA7203A8674","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be17e3e16f8de4b41a5e87255873ed44ec5fd55e","datavalue":{"value":{"entity-type":"item","numeric-id":3361904,"id":"Q3361904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923587$53C81A21-FEB9-41F3-B52E-59A02F7D75B8","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":"Q1923587$89877E00-A61C-4D0B-B418-9A14B9202E40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923587$506665A2-7AD1-4CD3-A3B5-74CAB2C6A35A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"340facedbea30c7fe358ffb2ba0c5abdea3ed5aa","datavalue":{"value":{"entity-type":"item","numeric-id":4075493,"id":"Q4075493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923587$C59288DA-F6B5-4BC5-9C2C-5E8B20F38FEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3919974a0da75982842c318887f6990491692f99","datavalue":{"value":{"entity-type":"item","numeric-id":4852628,"id":"Q4852628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923587$4DF0E019-763A-42AC-B13B-0588F3F2BEDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923587$D557D1D5-5CDA-4B59-A773-671572990D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5978258c83db65a9aa51624f6ab2bceffec8534","datavalue":{"value":{"entity-type":"item","numeric-id":5576821,"id":"Q5576821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923587$2B8BC3DC-C401-443B-836C-0CB1598F8A00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b29076f31dc73c454fb9de1110bcc531f7c39fb6","datavalue":{"value":{"entity-type":"item","numeric-id":3271425,"id":"Q3271425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923587$278DC915-B1FB-4642-AE4C-2818584440C8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8a6210b0af8c6340b077105497e7b849b9e5fae6","datavalue":{"value":"W3100826043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923587$CE5C1957-EB01-4B30-BFDD-F0FA31BA10D0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d100389878e620e8a1e055a790ad8f3470c2439","datavalue":{"value":{"entity-type":"item","numeric-id":1923478,"id":"Q1923478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aff28bca20d80f6960b4a0dd6a073bee5c813013","datavalue":{"value":{"amount":"+0.7907469868659973","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":"Q1923587$E60B6F92-C2FD-43FC-8E5D-EBC5DA69C8E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13cf996bb10ff50a5930e444d577196de37d01f6","datavalue":{"value":{"entity-type":"item","numeric-id":2768327,"id":"Q2768327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a95548ef55678641d28cf62918228c7e332287fa","datavalue":{"value":{"amount":"+0.7792577147483826","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":"Q1923587$18742F09-B66C-472A-BF25-593B76EB6EA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f691856250bf7c020e151d80debf92f2cda7a4ee","datavalue":{"value":{"entity-type":"item","numeric-id":1007574,"id":"Q1007574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ff40c231e136ad21844c61f5860547c1a23e1a6","datavalue":{"value":{"amount":"+0.7656602263450623","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":"Q1923587$BFA4EA21-812F-4D0E-88B0-29C67D2DB9B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfb49b241e6baec59eedac0e46a1fc48d8089e4d","datavalue":{"value":{"entity-type":"item","numeric-id":4443090,"id":"Q4443090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29a4abaa1e24fdf28910ed04a357afef6c1ed4fc","datavalue":{"value":{"amount":"+0.7652105689048767","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":"Q1923587$108ED2B3-1214-4AC1-9DEC-0E573D3C71A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1a1c77aa30bc399f63f8461f08f38f3e35c9ce7","datavalue":{"value":{"entity-type":"item","numeric-id":1613363,"id":"Q1613363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac9af5852c341a3d853862401e1ea603b28d2c1c","datavalue":{"value":{"amount":"+0.7622580528259277","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":"Q1923587$3C32C0A6-0972-4076-B9EC-007F96B49824","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1923587","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1923587"}}}}}