{"entities":{"Q1209368":{"pageid":1220117,"ns":120,"title":"Item:Q1209368","lastrevid":69894243,"modified":"2026-04-13T11:03:16Z","type":"item","id":"Q1209368","labels":{"en":{"language":"en","value":"An optimal algorithm for the period of a strongly connected digraph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 167768"}},"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":"Q1209368$5BAC9EB5-3B58-4C58-98CF-56F0841D22BD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"558e9a9e978ba9dfefff2d68dc6cac2a6125f35a","datavalue":{"value":{"text":"An optimal algorithm for the period of a strongly connected digraph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1209368$4CED6B85-59D3-4E1E-87E1-67C01DFA169E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cac4c24ea6aa6e8ffbb250f59ef2f46b50782346","datavalue":{"value":"0768.68056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209368$754E9E1A-7D28-4642-8CCE-AE2D0A48C6FF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d7178f29e31bb6e2a3540f4319e7cbd8b586f76e","datavalue":{"value":"10.1016/0020-0190(92)90106-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209368$DEA28DBC-5B9B-41D8-AEDC-797069F2CD5E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e61dc6dab4fce0eb4dbedf2c296db33788c421a7","datavalue":{"value":{"entity-type":"item","numeric-id":595516,"id":"Q595516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$785D5672-FBE0-4724-B948-5202AC19CEAA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$5DA25FAF-58AC-4A71-AD7F-218E44A8282B","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":"Q1209368$869E9C75-C6E5-41E1-9525-4D73880ECDFB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2d8e7345be9829580a56bf34f6e3d27264b8b423","datavalue":{"value":"This paper presents a simple modification of the breadth-first search for the single-source shortest paths problem that allows the computation of the period in an optimal fashion: \\(O(| E|)\\) time and space. Moreover, the constants hidden by the \\(O(\\cdot)\\) notation are small, so the proposed algorithm turns out to be very efficient on strongly connected digraphs of any size. The interest in the period --- a seemingly strange quantity --- arises from the theory of non-negative irreducible matrices and its applications, e.g. spectral and structural properties of graphs, long-term behaviour of non-negative discrete time dynamical systems, Markov chains, etc.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209368$0882EF59-5C78-4E5C-8FA2-79B5236B29E3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209368$6FCD77C0-E59A-4834-912A-9C1EA5EB9AFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209368$272B858E-9DB5-4FA0-9A62-2087D8AC6848","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209368$A1CF94D3-7A50-432D-BAC7-17281AB4747C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0cb14977538002ae7f9b84cd09c92134fca34e85","datavalue":{"value":"167768","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209368$956C0C08-6B66-4EC7-935E-D0F6D5B4D3FA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfa71e439ec4028df02c3244a2a76dc52ffb0dae","datavalue":{"value":"breadth-first search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209368$22DB963A-8AC8-4200-87A6-C1E3D5351AED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"37b2763a57208c334f525d2a83bf6ecda0c1914d","datavalue":{"value":"single-source shortest paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209368$B507380C-62D2-401C-9967-A22621983EBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df2e397a86b8cc356bd87c7ff0b1a23a94a39170","datavalue":{"value":"period","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209368$674FEFA0-1CBD-4623-B719-D11F4A50EE4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3301f11b2e9732d6c77ee3947c1d62da041a3fa2","datavalue":{"value":"strongly connected digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209368$BF72E8D6-81B2-40EF-8E88-33D424BF0EEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9e4c4a0099f2a5ad09a1499a08fcdf50b5b0030","datavalue":{"value":"irreducible matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209368$49D92A8D-EFFD-45FC-8D3F-7DA872DDB65F","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":"Q1209368$1D582E97-D9FB-4946-8E69-00527EB589B1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"31ffbeb3b72142d175de150109c48686bfcfbae5","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90106-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1209368$A327944A-B5C3-4FB2-87A6-BC372221EAC8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"990f8ef4dd2b4cd6ac47d28d79aed1de6dc90870","datavalue":{"value":"W2059629137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209368$DB98BBEC-8479-4D5A-8044-4AD3C2BCE879","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"af897edd69650b0fb523f1e28b3483b5592bf862","datavalue":{"value":{"entity-type":"item","numeric-id":3474275,"id":"Q3474275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$FA8A8DF2-0399-4C0D-96AA-DEA9BB6FA1EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f65538fd9946d6df0cd6c1f809a144da41b8a003","datavalue":{"value":{"entity-type":"item","numeric-id":3943082,"id":"Q3943082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$8C7E5595-A7AA-4A2D-9C72-580C14DB988E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e5392f340010db75b20c324cc837f13e6bb04b2","datavalue":{"value":{"entity-type":"item","numeric-id":5524074,"id":"Q5524074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$3304AFBC-3895-4D3E-AD1A-2755189C096E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d82216c069c0d4e92b398f0b1f2381174e692ded","datavalue":{"value":{"entity-type":"item","numeric-id":4109064,"id":"Q4109064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$C0D72D27-CF4F-44ED-ABCD-3A4D0035C990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11eefd7e7dc86c1755a8db4c6825e6e9fdeb6d39","datavalue":{"value":{"entity-type":"item","numeric-id":3619797,"id":"Q3619797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$5302CA29-9D47-4F6A-9858-1D472FF3969C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1312a34b6a8327be1e35714f2f181547c026a788","datavalue":{"value":{"entity-type":"item","numeric-id":3907599,"id":"Q3907599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$C3A0839A-E66E-47E1-973C-3FBF77A3907B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5dfd9e4996ea3da2d0e02a61f9b6de58e2593e33","datavalue":{"value":{"entity-type":"item","numeric-id":4040797,"id":"Q4040797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$3157426D-D18B-43D5-8EB4-28BD24A89158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9651942f409c9d659c98c05303ddf9e9e3f71535","datavalue":{"value":{"entity-type":"item","numeric-id":1095465,"id":"Q1095465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$4F7811F3-9A51-460B-9D76-E19D9072EF29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10dd82ad424eb2de871c674798f71495dc3861ab","datavalue":{"value":{"entity-type":"item","numeric-id":5514145,"id":"Q5514145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$750B0F69-42A0-4DA4-9B5A-01487AFB763B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8d2a4faa50410d408d52d2fdbd09e9080c4b7f4","datavalue":{"value":{"entity-type":"item","numeric-id":5566869,"id":"Q5566869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$0524FC3D-96C8-456F-A0BC-37ED45257DAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2721c702dd018b6c82dceadd8f3e8916a3a56b42","datavalue":{"value":{"entity-type":"item","numeric-id":1157624,"id":"Q1157624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$4DED459C-CA26-49CC-83AD-471311176F4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"932383d1ac997ed208ef47dcb574b592efaf75b3","datavalue":{"value":{"entity-type":"item","numeric-id":4065031,"id":"Q4065031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$0406BEC0-2E03-41CF-A318-42D147924043","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6e689ca9104617943bd76b284824e0c9ceb6bd","datavalue":{"value":{"entity-type":"item","numeric-id":3707420,"id":"Q3707420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209368$B5658015-1A68-4AA9-AE9F-C11565CCFFE0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12842a70afc0337065e48035fbde1e5a341a6fca","datavalue":{"value":{"entity-type":"item","numeric-id":1363762,"id":"Q1363762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bb6d816817b6eb37911595101c3020473d82999","datavalue":{"value":{"amount":"+0.7944228649139404","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":"Q1209368$2BCFCD1A-90C1-4363-ADA0-D223C071ED14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"947965f089033f7f3fdb08efd32c40f06df79b03","datavalue":{"value":{"entity-type":"item","numeric-id":1570834,"id":"Q1570834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26366137697c473cd2691f055a9b0a4ab0b3e627","datavalue":{"value":{"amount":"+0.7566332221031189","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":"Q1209368$F01C4BA3-E013-403E-88C9-1FEBF45AF011","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a40ad003c07c3fdc0a39e70678f5f2981ad91dd","datavalue":{"value":{"entity-type":"item","numeric-id":1920444,"id":"Q1920444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07027b1fb2ffe213ac9ec19a71c660e0f2aa3808","datavalue":{"value":{"amount":"+0.7452020645141602","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":"Q1209368$E2E542AF-2E06-4389-91C3-7315A235EF81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66d0c5d01e8498b78ef08020f6ccf9141729ecc5","datavalue":{"value":{"entity-type":"item","numeric-id":4823306,"id":"Q4823306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"350d6f2b4b4bbc01265f7036494b0a59ecfeb9e3","datavalue":{"value":{"amount":"+0.7417179346084595","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":"Q1209368$DBB8E812-AAFB-41DC-B519-FB2A02B6B5D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd4bc30b6220cac463dfb50f5e30b84ff49bcc60","datavalue":{"value":{"entity-type":"item","numeric-id":3647995,"id":"Q3647995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4dd58829849352c5495d549d3eaa5402549b8c63","datavalue":{"value":{"amount":"+0.7356979250907898","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":"Q1209368$43203D43-9511-492C-B481-A026113473F9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An optimal algorithm for the period of a strongly connected digraph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_optimal_algorithm_for_the_period_of_a_strongly_connected_digraph"}}}}}