{"entities":{"Q677988":{"pageid":679837,"ns":120,"title":"Item:Q677988","lastrevid":63653451,"modified":"2026-04-11T14:37:53Z","type":"item","id":"Q677988","labels":{"en":{"language":"en","value":"Undirected \\(s\\)--\\(t\\) connectivity in polynomial time and sublinear space"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1000110"}},"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":"Q677988$DD4056F2-6F21-4591-BE79-933AEDFACC93","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4bdd5bbbe04b427ae728ad50ec71c00c0263961e","datavalue":{"value":{"text":"Undirected \\(s\\)--\\(t\\) connectivity in polynomial time and sublinear space","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q677988$58719D60-F1CF-417E-8134-375FEC932253","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3df24f9d68471a3205f864a973308274749ca415","datavalue":{"value":"0872.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677988$A2C9F515-7144-40DF-98AA-580695990FF9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e9aa7cbc9c1415dcdde1eb107e00282ed297a91f","datavalue":{"value":"10.1007/BF01202039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677988$A7E1026D-E056-4608-B26E-D48A38419D08","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ceda081a81caa6460ae82582a860c0138cb6336f","datavalue":{"value":{"entity-type":"item","numeric-id":677987,"id":"Q677987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$20C94BC1-A23E-46FE-8CFD-3352282EBCC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"574a7757612bdc735a51e27abe74e9e45e1a1f3a","datavalue":{"value":{"entity-type":"item","numeric-id":675047,"id":"Q675047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$8543A3E2-1130-4CFA-A1EE-968748407F8E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$01ECBA23-3BD2-4837-9A92-B96D88C17B51","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7e9cebd28808effc23600f869e8c8d221fafc74a","datavalue":{"value":{"time":"+1997-05-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q677988$1521C827-ED22-4F89-9E9F-55BC064F6427","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c4be0f96b0e5c8190b02ac6c50a6ce78892bb9fa","datavalue":{"value":"The \\(s\\)-\\(t\\) connectivity problem for undirected graphs is to decide whether two designated vertices, \\(s\\) and \\(t\\), are in the same connected component. The authors present three new deterministic algorithms solving undirected \\(s\\)-\\(t\\) connectivity using sublinear space and polynomial time. The algorithms provide a nearly smooth time-space tradeoff between depth-first search and Savitch's algorithm. For \\(n\\) vertex, \\(m\\) edge graphs, the simplest of their algorithms uses space \\(O(s)\\), \\(n^{1/2}\\log_2 n\\leq s\\leq n\\log_2n\\), and time \\(O(((m+n)n^2 \\log^2n)/s)\\). They give a variant of this method that is faster at the higher end of the space spectrum. For example, with space \\(\\Theta(n\\log n)\\), its time bound is \\(O((m+n)\\log n)\\), close to the optimal time for the problem. Another generalization uses less space, but more time: space \\(O(\\lambda n^{1/\\lambda}\\log n)\\), for \\(2\\leq\\lambda\\leq \\log_2n\\), and time \\(N^{O(\\lambda)}\\). For constant \\(\\lambda\\) the time remains polynomial.","type":"string"},"datatype":"string"},"type":"statement","id":"Q677988$2BDD033F-8702-414B-8937-59B80DDD78DF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677988$B9F88D8F-B027-4E45-9585-087A072077F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677988$EDA30E8B-22E1-495F-8456-474643B1DFBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677988$C1771B00-5E46-4506-A23E-BAFC88815453","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677988$E1737631-0AE2-4277-95CE-72A34344AC0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677988$39435560-39E3-48F3-A098-FD21182CBA8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677988$BF6909F1-FF28-4F1B-BCFA-F9243469ABD6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8d7c574838c3c7f4dbcfd56467b65a92d2875017","datavalue":{"value":"1000110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677988$B8CFA697-445D-4EDB-B8DA-7268452751B8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q677988$7DCF9E49-BA0F-417A-ABB2-89521633792E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b3320975f0c9baf81f0934ae54829c031b1f8c3","datavalue":{"value":"sublinear space","type":"string"},"datatype":"string"},"type":"statement","id":"Q677988$4AB72206-120F-435F-BCCB-5780C85248B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q677988$0E9BB419-6F6B-4FA8-A0F4-7D2EBC6DD3AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e1e89c01692078d552e9dbfa43d9ed6cde94ace","datavalue":{"value":"time-space tradeoff","type":"string"},"datatype":"string"},"type":"statement","id":"Q677988$2FA42AA6-D740-4840-AF22-E3952613FAF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff7bf11626141f10491819543bc6e69eb57efdf3","datavalue":{"value":"depth-first search","type":"string"},"datatype":"string"},"type":"statement","id":"Q677988$094E3069-BBB2-4B12-8305-925AEEF4B13A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q677988$66A9C2CC-8EF6-4D3E-9610-561552E75800","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":"Q677988$49B59480-DE30-4B0C-9864-A6E4DA2B85F9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7be56282e6b70c8f0213b12e748645a1f3fe5209","datavalue":{"value":{"entity-type":"item","numeric-id":918989,"id":"Q918989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$8D060036-7877-464D-AB56-A2FE6E4B8434","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bbc8a63364718213bd1f348155f7d40d7b87df8","datavalue":{"value":{"entity-type":"item","numeric-id":1201152,"id":"Q1201152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$2784813A-2F62-4CB0-820E-F7FFC81C2076","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c086edff2920c7c16503c0a14ce4156a6830f33","datavalue":{"value":{"entity-type":"item","numeric-id":3472132,"id":"Q3472132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$DB1DC378-9AE1-4B2D-9840-52011ADE20DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c589262291363ca45e6a594c22c6cd417107033","datavalue":{"value":{"entity-type":"item","numeric-id":4875432,"id":"Q4875432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$BCA60C35-6353-48C8-BF1E-90C57062C917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"982934486b418444e6dbcee32d7e4af725ea6554","datavalue":{"value":{"entity-type":"item","numeric-id":675049,"id":"Q675049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$CB6144B3-B69D-4B5E-A70B-08DC8ABC7BE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23708f3ee0b536410829c31900335701f20e86cc","datavalue":{"value":{"entity-type":"item","numeric-id":3835019,"id":"Q3835019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$14B0FB37-5DFB-4FBC-8321-57CEEAF3E307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b68eb0ce267601da3cfc756b50abf8980d4d6bae","datavalue":{"value":{"entity-type":"item","numeric-id":1201151,"id":"Q1201151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$03F386C5-007E-45D8-94BF-64FF2297C3DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51d26082b5bd8cd875555480f84bc23029cbfcdf","datavalue":{"value":{"entity-type":"item","numeric-id":3782809,"id":"Q3782809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$0004188F-E8F9-452D-A74C-73596E48A69E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a8c61eee2c93c0da37878a1c86b63cade849745","datavalue":{"value":{"entity-type":"item","numeric-id":4291560,"id":"Q4291560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$1B439122-7AEA-4D8E-B803-6B166A7670E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d3b4cbd0eefd7c939851b7800abe7bcbb7802a6","datavalue":{"value":{"entity-type":"item","numeric-id":3890116,"id":"Q3890116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$D00B17F0-36CC-4237-92A1-CEB16BF4465C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c02bc119985d993e4e68ab85dce8ba5abd43c261","datavalue":{"value":{"entity-type":"item","numeric-id":5248543,"id":"Q5248543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$2FB26E0D-DEDE-47AF-815E-37DDA410C465","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"655386154c7a7e332c426e371ba90a3adcc2da5d","datavalue":{"value":{"entity-type":"item","numeric-id":1802060,"id":"Q1802060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$BC59B61D-715B-4BA1-BB94-D8FDD1B58B23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbc637d418c1199ceb82383cfd834401b7b93204","datavalue":{"value":{"entity-type":"item","numeric-id":1117703,"id":"Q1117703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$095802FD-3FB1-4564-990D-DD819D252152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$19082166-CDD5-4150-907A-3B400063C6E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1543a6d9030474a2d21021a96f6fd782e1dd1a4e","datavalue":{"value":{"entity-type":"item","numeric-id":1167537,"id":"Q1167537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$B5134298-0FD3-4489-9F01-FE7195049824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4203be64018c59961cbb6c7d765cd053aa8e75e3","datavalue":{"value":{"entity-type":"item","numeric-id":1327590,"id":"Q1327590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$1D932ACE-5DC3-4FF8-9ED8-0869E69660A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$D9D75760-4FD0-4342-A4A1-92689F32F6EC","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":"Q677988$D72458C3-A02A-408A-9148-AA86A62B5856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0460f5b4492f741d8a6681bf5cad208eb546f979","datavalue":{"value":{"entity-type":"item","numeric-id":4027857,"id":"Q4027857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677988$4EC2E355-3B25-47CB-AEB2-687ED4898DCB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d03b1d33eecaac5b080647c555352a6a6ffa459e","datavalue":{"value":{"entity-type":"item","numeric-id":5385338,"id":"Q5385338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35ba9cb2f1204fb042fe4fd052ca9691394327e2","datavalue":{"value":{"amount":"+0.9133020639419556","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":"Q677988$EE3E79B9-53E6-49EF-91FE-D200A82AEDF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98992fc219e66286c79945ce1a83bb06cd63abac","datavalue":{"value":{"entity-type":"item","numeric-id":4230323,"id":"Q4230323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0ca1abc689f9f27a208a2802fe4d17026c448a3","datavalue":{"value":{"amount":"+0.8936883211135864","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":"Q677988$38C94910-DE9E-4080-8772-D402476AB1C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe20b80cbf2dbd5e08c9e1af34aba302166e6c21","datavalue":{"value":{"entity-type":"item","numeric-id":3624373,"id":"Q3624373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9539f44a62052a070143807b118a86c47b8012d3","datavalue":{"value":{"amount":"+0.8918075561523438","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":"Q677988$A85502F3-7058-4B60-9443-DC162ED5A920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd38e5f406e3a325c9b73ea2052c75002cc84918","datavalue":{"value":{"entity-type":"item","numeric-id":1356886,"id":"Q1356886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9928bd0fd1a571baaecc61b7b52b765deea945f5","datavalue":{"value":{"amount":"+0.878329873085022","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":"Q677988$2BD1F979-3CD6-493D-BFE4-7EFE53F659EA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Undirected \\(s\\)--\\(t\\) connectivity in polynomial time and sublinear space","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Undirected_%5C(s%5C)--%5C(t%5C)_connectivity_in_polynomial_time_and_sublinear_space"}}}}}