{"entities":{"Q1811083":{"pageid":1821825,"ns":120,"title":"Item:Q1811083","lastrevid":48108904,"modified":"2026-01-03T16:27:37Z","type":"item","id":"Q1811083","labels":{"en":{"language":"en","value":"An \\(O(n^{2}\\)) algorithm for maximum cycle mean of Monge matrices in max-algebra."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1925265"}},"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":"Q1811083$33FC72EE-F107-4EC7-BCC5-41214979740C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e92de9bb80fbe733ee6bc91e313999a7574cdf35","datavalue":{"value":{"text":"An \\(O(n^{2}\\)) algorithm for maximum cycle mean of Monge matrices in max-algebra.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1811083$5477CF26-C793-45D9-A4FB-BC393642379F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"68e15d66eb823684525824a143fb60fbcaeeea30","datavalue":{"value":"1041.90045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811083$AD67FE82-C693-41CE-8273-A5EE50790644","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"684dcd9091f4c15f02dd20b094b863e950ff07c9","datavalue":{"value":"10.1016/S0166-218X(02)00395-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811083$EC36D475-DF24-4CBC-9414-A2A82947AA68","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"364ef6bad6d03d0437606ec147d4361592f89632","datavalue":{"value":{"entity-type":"item","numeric-id":400505,"id":"Q400505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811083$AC318593-7BDA-4899-AF14-A9811883CD6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5d38f62edf1d4ea0abec9914cd3ebde0b3334d6","datavalue":{"value":{"entity-type":"item","numeric-id":217088,"id":"Q217088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811083$19001488-2FE1-4E5E-8D07-B14FA51EE1BE","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":"Q1811083$8F7FBF9E-12E6-4EB2-B369-7757F867A217","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ae38298a411e50615364cd6c80d7e0f949b3a896","datavalue":{"value":{"time":"+2003-06-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1811083$B6F2FFAA-F93A-4BE3-B009-FF57918873F6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"addf12442878c753c8dd2bf2a5095ceba52e6b73","datavalue":{"value":"For a \\((n\\times n)\\) real matrix \\((a_{ij})\\), the known algorithm by \\textit{R. M. Karp} [Discrete Math. 23, No. 3, 309--311 (1978; Zbl 0386.05032)] exists to find the maximum cycle mean in \\(O(n^3)\\) time, i.e. to find \\(\\max (a_{i_1 i_2}+a_{i_2 i_3}+\\ldots +a_{i_p i_1})/p\\) over all cyclic permutations \\((i_1,\\ldots ,i_p)\\) of subsets of the set \\(\\{ 1,2,\\ldots,n\\}.\\)  The paper deals with the case when \\((a_{ij})\\) is a Monge or inverse Monge matrix, i.e. \\((a_{ij})\\) satisfies the so-called Monge property \\(a_{ij}+a_{kl}\\leq a_{il}+a_{kj}\\) or inverse Monge property \\(a_{ij}+a_{kl}\\geq a_{il}+a_{kj}\\) for all \\(1\\leq i< k\\leq n,\\) \\( 1\\leq j < l \\leq n.\\)  An algorithm of complexity \\(O(n^2)\\) is proposed to find the maximum cycle mean (eigenvalue).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811083$CF2B6AD5-37A5-4A61-828E-70365B316C3E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"937feade3061e9f7774221fad1a9d078a901d790","datavalue":{"value":{"entity-type":"item","numeric-id":336765,"id":"Q336765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811083$03082904-20C6-40B6-A150-46313CB0DDD9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811083$97D90E84-0638-4C84-AE70-494042481361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811083$8F9453B9-22ED-4D7F-BC8B-E02D684ABCAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811083$9F6FFA1B-3E20-455A-A52B-11756C150954","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0df8c3af3220b407b86e9f0296f96459ff5fb799","datavalue":{"value":"1925265","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811083$3A639A3C-7B93-4C4A-A21B-CE7C90CDD6FB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2621a7f114359c15599320f635eb9b30e969bde4","datavalue":{"value":"eigenvalue","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811083$33E16B20-33BD-45DA-A269-E21B40E6EBF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08dd28f219463d251a2bc2ea42f2e092b3223146","datavalue":{"value":"Monge matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811083$E7B3F525-DCD0-4EDB-8C6F-C7871249FA6D","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":"Q1811083$C03827AB-B0E1-48AD-916C-FA69619D85A1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b4998d2df09b116bf5e066fc438f67a68c7965a","datavalue":{"value":{"entity-type":"item","numeric-id":1923588,"id":"Q1923588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811083$6BC0CCA4-6DF3-4906-8544-00D50377E847","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6974afa4556fb58b10e698257842dea53674ee49","datavalue":{"value":{"entity-type":"item","numeric-id":1183336,"id":"Q1183336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811083$2CF5D1F7-793F-40AD-BD1D-426BAD114BE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86cdee82d5415e58dcb12c4969d50345b83953d2","datavalue":{"value":{"entity-type":"item","numeric-id":802638,"id":"Q802638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811083$9ED73368-6E95-4191-B971-FB26A65CAD8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a339108f845f381ae162edfeda7b58a976de693","datavalue":{"value":{"entity-type":"item","numeric-id":1254944,"id":"Q1254944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811083$98E4BFF3-3A40-4AA4-84FC-52BB18A318B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"117178b46bd4133cc1ac40b9e01f7800f42d50ab","datavalue":{"value":{"entity-type":"item","numeric-id":5583694,"id":"Q5583694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811083$3DF8AC11-0B15-45A2-A708-62B395A66639","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6ff40bf465825b8b8792a44d1b66e2e0447b71b","datavalue":{"value":{"entity-type":"item","numeric-id":3684177,"id":"Q3684177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811083$A2DC1BF5-1095-4843-B3AA-ECC8D470B45B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f970782cef7606d75b439e57c5964589154083b2","datavalue":{"value":{"entity-type":"item","numeric-id":1249587,"id":"Q1249587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811083$9651B9E7-8016-42E6-9E92-7077F7077C74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811083$5C07523B-6BEE-4F64-8131-BD8B4D90F416","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"febad564399d40b9634cf9cbba4a0f68304f3775","datavalue":{"value":{"entity-type":"item","numeric-id":4764873,"id":"Q4764873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811083$BC9AEE03-7E07-4FB1-BD9C-BC180CE76A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c00f7c1f68319c6e7fcca0e07f3cb303985fe5f","datavalue":{"value":{"entity-type":"item","numeric-id":1329798,"id":"Q1329798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811083$900809AC-9030-4CC1-83A9-C830A1C6F2CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f3d72d6f067eeebf02882fdf0a5f1edb3452f80","datavalue":{"value":{"entity-type":"item","numeric-id":1155513,"id":"Q1155513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811083$AC945142-4E8A-4286-A644-2B1A35DAEF2D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44c2c8d61c7ee8d1a978ee6956787eee5d90ca10","datavalue":{"value":{"entity-type":"item","numeric-id":2715511,"id":"Q2715511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1fd08dc103431ef17fd0a84ffe72618a33f3eeb","datavalue":{"value":{"amount":"+0.8892483115196228","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":"Q1811083$E320D39F-9CC0-40FA-9749-3C12CB1DAF82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bd46e3b671068bbcc0defc9d7f2db8eaa55ef01","datavalue":{"value":{"entity-type":"item","numeric-id":2476248,"id":"Q2476248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9028720c4f3a7953d3404d90552c04b7112abccd","datavalue":{"value":{"amount":"+0.847540557384491","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":"Q1811083$87AD3A2A-E9D3-4393-B088-324B9B697FA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7d6e1d04bd555a4d147ce862abd6d700322cfb5","datavalue":{"value":{"entity-type":"item","numeric-id":1183336,"id":"Q1183336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fcdeaa904461653caa980209e3e906577b0910c","datavalue":{"value":{"amount":"+0.8442391753196716","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":"Q1811083$979E2AC4-9926-40BA-80DA-5ED2F3B98460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"389a266136fd081847bd86bca42835f1413a9695","datavalue":{"value":{"entity-type":"item","numeric-id":2857726,"id":"Q2857726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7435cd935c5fab7169935731cecfc849244fe9d7","datavalue":{"value":{"amount":"+0.8408412337303162","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":"Q1811083$33CD78EE-614E-4A9A-BB41-99F482F1ABC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d65a885fb270aa11f11b8ba7feddd7a95bfd81ea","datavalue":{"value":{"entity-type":"item","numeric-id":1028473,"id":"Q1028473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88ff5d6ee268676927a5acb69293f0c31568830c","datavalue":{"value":{"amount":"+0.8169777989387512","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":"Q1811083$DCC026A8-3269-477E-936A-FFA8C4C8AD5D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1811083","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1811083"}}}}}