{"entities":{"Q1821118":{"pageid":1831860,"ns":120,"title":"Item:Q1821118","lastrevid":69038463,"modified":"2026-04-13T03:56:25Z","type":"item","id":"Q1821118","labels":{"en":{"language":"en","value":"An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3997839"}},"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":"Q1821118$3246309F-3064-403B-A7EE-11045694E446","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"870396babd319631e37f625398ccc733359fe815","datavalue":{"value":{"text":"An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1821118$A942D526-E4C4-4EDC-AAF0-5D248ECDB131","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3ba21aae30b590e729dfa9a0cd0aa4c1a67a4a7e","datavalue":{"value":"0616.05045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821118$E0C50684-7E55-459C-BA52-0A6D433D7A34","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"948fbda49720a93e02f4a176e1462861690ce9d2","datavalue":{"value":"10.1016/0166-218X(87)90007-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821118$9B1D4158-E8E4-42A5-A50C-DF200DC1A60F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b118d0eb140454f59ce6c876e7843371e3db6b4f","datavalue":{"value":{"entity-type":"item","numeric-id":442275,"id":"Q442275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821118$E3572D35-C363-4874-9D8B-2BD7B1D3C069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2eaa9e71fc79b2141544f205cf9e90aea8be73ea","datavalue":{"value":{"entity-type":"item","numeric-id":1821117,"id":"Q1821117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821118$277CCCA6-EFB7-4217-908C-2A7F1AF6AAE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"761f99324563a442d8fe16e998f4a3ddaa74167b","datavalue":{"value":{"entity-type":"item","numeric-id":1151053,"id":"Q1151053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821118$800596AA-0A4C-4781-8CAE-2B3A657306AB","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":"Q1821118$67175982-59AC-4F17-AFDE-AF05A44C49FE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1821118$861EFD38-169B-4CA1-9606-69D7AEABF9FC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5364427aba1c46d8ef8aef19c9bc0c02ab572e75","datavalue":{"value":"Given a digraph G(V,E) the problem under study, called k-vertex- connectivity unweighted augmentation problem, is to find the smallest possible set E'\\(\\subset V\\times V\\) such that G'(V,E\\(\\cup E')\\) is k- vertex-connected. The paper presents a survey of the known results concerning an algorithmical complexity of the problem for different types of graphs and different k. Then, the attention is focused on solving the problem for rooted directed trees. For this special case an algorithm is presented enabling to solve the problem in O(k\\(| V|)\\) time. Moreover, it is shown that the algorithm is optimal except for a constant factor.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1821118$020D7322-3459-4E19-8D04-7DE58816BD3C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821118$E9C92FA1-3306-44CF-B155-B856A7E028B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821118$131FA769-61DE-4CAB-BF32-7E7764E1E7E1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c7b2b2f73a7aac26183f9541a586dae14c7a8eb7","datavalue":{"value":"3997839","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821118$F86A94A2-5537-4342-A5C1-3F10C6238D22","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa1aad7939edcfd4b5e484df0d142dec37c824fb","datavalue":{"value":"rooted trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1821118$57A9A267-4D9D-4391-9934-D2F76C9E52E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39e982031e9bd6bfa9a6657473f99ab9778d4306","datavalue":{"value":"k-vertex-connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1821118$5209C6D0-0C92-4B1A-82CD-9454EB21F359","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af04e24410df1f46e57d1e9a33757b3785655244","datavalue":{"value":"augmentation problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1821118$D17F3180-E254-4C1F-B8C3-CE830EF62AF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7f879d8469ef3e35cba53e27c60974bacdf9b77","datavalue":{"value":"rooted directed trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1821118$5DE1ED42-3DFB-4EB1-BB95-4ED8876564C3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"56a1ca2701a8ace98397887a83075850e16781d0","datavalue":{"value":{"entity-type":"item","numeric-id":274436,"id":"Q274436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821118$CA312B9B-86DC-4445-95F8-69D5A5508C08","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":"Q1821118$3A83AAA8-A7E6-4A76-ADC9-E814E6590EFB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d9e735882f0114d9d1bd74d7bde93766d995370","datavalue":{"value":{"entity-type":"item","numeric-id":4065051,"id":"Q4065051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821118$4FDF1517-E701-4D02-BB72-CA59D29AE203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821118$731D9060-D83E-4215-AD46-71A6E7D31278","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f984a76d33b502ce8030a3d08c9fecc669033c57","datavalue":{"value":{"entity-type":"item","numeric-id":4115167,"id":"Q4115167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821118$8D4209D4-A324-43CF-BDB7-557FEA92B96E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb6d330b0ba17ea9706ff485bd2cc7e5caf6771","datavalue":{"value":{"entity-type":"item","numeric-id":3883524,"id":"Q3883524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821118$F3619E44-D95D-43A3-AB1A-F91284D97223","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"123daef8044687c6b82b228d6d82b12d7d70e566","datavalue":{"value":{"entity-type":"item","numeric-id":3910552,"id":"Q3910552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821118$E9AF71C8-ECAF-4A14-AFBC-49AA693DF1D9","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":"Q1821118$221D9E2A-FC6E-4CE8-9918-FFD2B64CDB60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ca3b0ed8dcdfc896e34507d7f18558a2c9249e4","datavalue":{"value":{"entity-type":"item","numeric-id":1821118,"id":"Q1821118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821118$B7047D3B-C10A-4B02-9A09-C1EA92D3EFEB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f7fac05bebaa0264de8f7f23864c8896f870ae60","datavalue":{"value":"https://doi.org/10.1016/0166-218x(87)90007-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1821118$7FE1688C-F620-4E2D-87E9-0CF3829DA7F3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"15f968fed6285fcd3002b72fe017b21bd7a23902","datavalue":{"value":"W1991573073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821118$590E5D3F-FA34-4FAB-AB0E-B4B41747EF4C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb5dc99a2b3a00da55328022fa9e2f7b8bdf697d","datavalue":{"value":{"entity-type":"item","numeric-id":1300059,"id":"Q1300059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de5190586c28bc065e5c83408dfca450db24a8d7","datavalue":{"value":{"amount":"+0.8692691922187805","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":"Q1821118$C1AEBDCF-2242-4C19-BA8E-7F37DD115644","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d68703cd044bbd46713c2b7d2191c219a5161859","datavalue":{"value":{"entity-type":"item","numeric-id":1407835,"id":"Q1407835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1a2fbbfac9986c2b944a955672332b2d810a870","datavalue":{"value":{"amount":"+0.8416314125061035","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":"Q1821118$02E9CE30-667F-4880-BFD9-E9E4508F37BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb03f5ed120c61ae366bfd44f69e9399f2afe0ae","datavalue":{"value":{"entity-type":"item","numeric-id":1386437,"id":"Q1386437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1a993242f794063dcfa69240c92786af12122d2","datavalue":{"value":{"amount":"+0.8158706426620483","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":"Q1821118$9972D408-FAB4-4376-9ED2-83E503B05DE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a578bc37667422fcc2737c4b7234dfbf913a918","datavalue":{"value":{"entity-type":"item","numeric-id":1775893,"id":"Q1775893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1a993242f794063dcfa69240c92786af12122d2","datavalue":{"value":{"amount":"+0.8158706426620483","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":"Q1821118$A4927F87-2818-4642-8E5A-00E0ED69E9A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"227e54671b4cf7c3ef74156e7660ad3e46e44a24","datavalue":{"value":{"entity-type":"item","numeric-id":2816106,"id":"Q2816106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8de772ccbb98e8833b133a72d675c271e533bf00","datavalue":{"value":{"amount":"+0.8126882910728455","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":"Q1821118$63CE5839-4A7F-4F37-A1F1-0915BF848105","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_optimal_time_algorithm_for_the_k-vertex-connectivity_unweighted_augmentation_problem_for_rooted_directed_trees"}}}}}