{"entities":{"Q1186788":{"pageid":1197537,"ns":120,"title":"Item:Q1186788","lastrevid":69848136,"modified":"2026-04-13T10:45:00Z","type":"item","id":"Q1186788","labels":{"en":{"language":"en","value":"A linear-time algorithm for finding a sparse \\(k\\)-connected spanning subgraph of a \\(k\\)-connected graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 37163"}},"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":"Q1186788$95F44154-2809-4846-BB9A-EA9845962F7F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3cd1e102346783aecc0aad15d38b8ac61adb7944","datavalue":{"value":{"text":"A linear-time algorithm for finding a sparse \\(k\\)-connected spanning subgraph of a \\(k\\)-connected graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1186788$505387B8-D125-470F-9748-663D79FC4B67","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1048ac61019fc65d0cbfe25aef52da9990d1fb64","datavalue":{"value":"0763.05065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186788$56261D0C-629A-424E-B50A-F2F1AB915A7E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aed4717fd20e582f729b6abe190183d26499d1b9","datavalue":{"value":"10.1007/BF01758778","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186788$B5997F85-4500-427C-92E8-9CDB2752D092","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"60eb2392c3cbb67419a7505eb4d7770437782b61","datavalue":{"value":{"entity-type":"item","numeric-id":187130,"id":"Q187130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186788$FA682DF1-7733-4DBB-A2B9-6D8F79FEF310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"746535ddb96ae77c4a55cf2874e59b3bf4f00d57","datavalue":{"value":{"entity-type":"item","numeric-id":171928,"id":"Q171928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186788$04A5F349-C67C-42AB-BB81-C117D59904AC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186788$ACEA629F-BE4D-4387-A0B4-238D05B145C7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1186788$6FC80C1A-15C2-42C4-8162-ECB52708A065","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fd6222f70b452f27cdf049c43d532e37e9d620bf","datavalue":{"value":"The authors present a linear-time algorithm for finding a sparse \\(k\\)- connected spanning subgraph for a given \\(k\\)-connected undirected graph. This is used to improve the time complexities of other graph connectivity problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186788$1A40FCA8-702E-4DE2-A625-03DADA0F9A1C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186788$C1841D24-0A84-4AC6-92AD-BE30D8D3A311","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186788$9C3EB7DB-25A8-4357-A29A-ECB37B78A922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186788$83702B15-6A83-4D5F-A02D-EA7E98FEC7B6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f80409a4c97acaeb02c5d543d868f9cce02b6701","datavalue":{"value":"37163","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186788$9C790D37-5EEA-45AC-ABFA-EEABBE371C6C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea851233c5e4599b2a4b08f7ea4fcd7bafb8b013","datavalue":{"value":"\\(k\\)-connected spanning subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186788$713B1897-F399-4D9F-B9CD-2F95DA457B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5186fd99999e6921db65766363ee98e6a615dadc","datavalue":{"value":"linear-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186788$4F5B4C06-6099-4D7E-B700-4FA7B5FA0716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89474c1417aef4801613bbb13330810b920695a1","datavalue":{"value":"time complexities","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186788$5854343C-7E8D-43EE-A39B-2FE126BDF610","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f6f7c7615658aa0a6fcce2e63c3a90143d33589","datavalue":{"value":"graph connectivity problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186788$490B2F38-4AD5-41E6-9B59-E69493BAED3E","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":"Q1186788$C6937982-3284-4076-91C8-E270C79F8935","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8938235e226586e0d42dc09ecbb90514ca80ee6","datavalue":{"value":{"entity-type":"item","numeric-id":4094634,"id":"Q4094634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186788$2004B860-AA13-4772-BD49-EB28F1858C1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"227c7382c822325f79332c05b795d49129bd542c","datavalue":{"value":{"entity-type":"item","numeric-id":3891779,"id":"Q3891779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186788$298FFAFC-326E-4E38-B2AD-30B7F31D337E","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":"Q1186788$8897DBC2-A7E5-43E2-9915-1DDC63F99CC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d575657fa68b8ef0feca63f02ca1b0b6990f89b9","datavalue":{"value":{"entity-type":"item","numeric-id":3989010,"id":"Q3989010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186788$AC9CE8C5-416B-4628-B76C-B454BC0C9FC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc3daf7de14aeb01da885b4ed98fe4e8dcc1494e","datavalue":{"value":{"entity-type":"item","numeric-id":3987534,"id":"Q3987534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186788$2704F6F9-6102-4E4C-A9CC-618FE3A68E78","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"030eace40ae37d337c350ddf46bbb78c582a8cf9","datavalue":{"value":"https://doi.org/10.1007/bf01758778","type":"string"},"datatype":"url"},"type":"statement","id":"Q1186788$F8CDB90D-C84A-4B75-9CCD-10D5A6C3FCD2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c11de316393fd4250efe61440e0dced828b510ae","datavalue":{"value":"W1996575062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186788$87A7B707-EC11-4F1B-B152-413C56626C5D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19d593ce9c2c35b26a58fe612495be0a37a4c835","datavalue":{"value":{"entity-type":"item","numeric-id":1847357,"id":"Q1847357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a3a8481a838aa44ebb6a15d166f8c55ee2120f0","datavalue":{"value":{"amount":"+0.8400145769119263","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":"Q1186788$DC4F92A5-23EC-4F5A-908E-2FA9ECDCA671","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6142cb5fefdd9f5b31bf4a47ffea4ea507073322","datavalue":{"value":{"entity-type":"item","numeric-id":2929622,"id":"Q2929622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5951d139ab02d4782e3520ff604e13703146eb3a","datavalue":{"value":{"amount":"+0.8079208731651306","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":"Q1186788$933BC1D1-13AE-41AB-960E-5F0045E53E13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6e1fa347993ec3d648cae88cc4d8a0d53afe4b8","datavalue":{"value":{"entity-type":"item","numeric-id":4763401,"id":"Q4763401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf8f228d5ff430efb3cf9b1d98f670f88ec89aa8","datavalue":{"value":{"amount":"+0.7999048829078674","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":"Q1186788$33C552D3-D582-4D60-B853-3DF052DF4869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35b0326f014de26510c9cf5b3a7d478e140970da","datavalue":{"value":{"entity-type":"item","numeric-id":4507363,"id":"Q4507363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5338e9070152397aed01d08b00d211a7ab877140","datavalue":{"value":{"amount":"+0.7979782819747925","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":"Q1186788$CF0AAAED-5C50-4D77-BB8B-C5478D957F80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df2a69f40c1a667e03c0000f6a309a9c53f5c211","datavalue":{"value":{"entity-type":"item","numeric-id":1199755,"id":"Q1199755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51868d9fe9fc1c9fba26db7a8d00460da57ff8ed","datavalue":{"value":{"amount":"+0.7970812916755676","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":"Q1186788$BE1C33E5-174F-4ABC-8CD6-BFF4494D50C0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A linear-time algorithm for finding a sparse \\(k\\)-connected spanning subgraph of a \\(k\\)-connected graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_linear-time_algorithm_for_finding_a_sparse_%5C(k%5C)-connected_spanning_subgraph_of_a_%5C(k%5C)-connected_graph"}}}}}