{"entities":{"Q2462389":{"pageid":2473132,"ns":120,"title":"Item:Q2462389","lastrevid":50225762,"modified":"2026-01-13T14:06:37Z","type":"item","id":"Q2462389","labels":{"en":{"language":"en","value":"The source location problem with local 3-vertex-connectivity requirements"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5216560"}},"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":"Q2462389$A46A9D40-DFD6-4541-8615-9D11B9047226","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dfcee718d443d21c172c5b074fad9dad6f650d72","datavalue":{"value":{"text":"The source location problem with local 3-vertex-connectivity requirements","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2462389$C1633D08-C152-4CE3-B057-209456C2F31B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"72180bf684a6e09d6a6c0822c6afd92d7ed18ddc","datavalue":{"value":"1127.90009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2462389$A6098F2C-29D5-4E49-971D-043E3C87EABE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd50cafeb7b40aba5852fdface8d2050ee59a85b","datavalue":{"value":{"entity-type":"item","numeric-id":290103,"id":"Q290103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462389$3299F1AD-FACF-434D-BBD6-1898B604D477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f658de36e953bbcf40c9e76b279d589c6c71f4eb","datavalue":{"value":{"entity-type":"item","numeric-id":870841,"id":"Q870841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462389$A71278F3-3C8C-48C2-B8BE-09066E0C4F60","rank":"normal"},{"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":"Q2462389$A9141C73-9605-4640-9FDA-9E9DE20B8E2E","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":"Q2462389$9543120B-129B-4FBC-B5C6-59C7C539C517","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"010c4d093ca2609306a3c907c440788c4ad84899","datavalue":{"value":{"time":"+2007-11-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2462389$D5B4AF9D-3DDE-4282-ADCB-52F79073B40F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"88170ed1c0288afbf25a556672c1839dc54a1820","datavalue":{"value":"https://barrel.repo.nii.ac.jp/?action=repository_action_common_download&item_id=872&item_no=1&attribute_id=19&file_no=1","type":"string"},"datatype":"url"},"type":"statement","id":"Q2462389$459E541D-2EF6-49C1-9700-7344F894131F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"38797ab869c022137faf75771daca04367f4be23","datavalue":{"value":"Given an undirected graph \\((V,E)\\) and an integer \\(d(v)\\geq 0\\) for each vertex \\(v\\in V\\) the source location problem with vertex-connectivity asks for a subset \\(S\\subset V\\) of minimal cardinality such that for each \\(v\\in V\\setminus S\\) at least \\(d(v)\\) vertex-disjoint paths exist from \\(S\\) to \\(v\\). The paper develops a linear time algorithm to solve this problem when \\(d(v)\\leq 3\\) for all \\(v\\in V\\) and proves NP-hardness when \\(d\\) is surjective \\(V\\rightarrow \\{0,3,4\\}\\), by reduction from a special type of vertex cover problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2462389$EF3DA295-32C4-407D-A1BA-8DD4075C1EF1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5e09f3da1a7483864918926ab5885138a8f45aaa","datavalue":{"value":{"entity-type":"item","numeric-id":166210,"id":"Q166210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462389$682B8489-1585-4F79-A6C7-630C2989DA07","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2462389$CBE4FE9E-36F5-4233-887F-856E1E235FBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2462389$31AD7952-54A6-4351-AF4D-F0907BA89497","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2462389$64F66380-77AA-435D-8CC9-FC158399A0B7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d51865320487d095e9cd1a03a9e98ce0078a7efc","datavalue":{"value":"5216560","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2462389$8136B72D-7561-4EFD-BAFE-E8D92EDDAB88","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e84ee48586814a40f00ca811bc22a55bf16a558","datavalue":{"value":"undirected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2462389$B4F280C4-F091-4D25-919D-602A13F62B07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcdb8c3e68a951c3a2c3e1c25ce8878406ad877a","datavalue":{"value":"source location problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2462389$2134394A-CAC7-475A-B44B-16DAFDA69E74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f132160ab7f111e0b365c0c32500976b2f15ddb","datavalue":{"value":"local vertex-connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2462389$E5AD0138-4678-46BA-AAAE-C48A433BA522","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q2462389$A23C34CD-A37F-4C9D-839B-9DE376F10CFC","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":"Q2462389$AE3DE1AC-C684-4477-B7C9-18BA74BDFF5F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"744ed64c2cecbe7967e65be603cf716edb177c10","datavalue":{"value":"W2148786002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2462389$5E7DFD23-9EBC-430F-A7BB-872000439C1A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"44f44a76b5719daa58c59d178eeffb178e71bb9e","datavalue":{"value":{"entity-type":"item","numeric-id":1566710,"id":"Q1566710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462389$B16CB055-8268-4F5B-ABBE-38A1E08303F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70416dc717dd0e2d0dbb49d7e831c25f9c22076f","datavalue":{"value":{"entity-type":"item","numeric-id":2777606,"id":"Q2777606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462389$0F80981F-36C3-416D-8534-C2E6E03826BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89a031afe32dfcbf4f8fba11966dba55c1408ae","datavalue":{"value":{"entity-type":"item","numeric-id":4179026,"id":"Q4179026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462389$479C3ED5-836E-4CA6-89E4-6BEB09B9D14A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e93fcc5f5e8911813f16fcd1e3e08e519d9e013","datavalue":{"value":{"entity-type":"item","numeric-id":4767335,"id":"Q4767335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462389$656D02C7-D799-4569-95D3-FDC87DB9B7F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755930f281d822c3dc49c8f730b726804f075bb4","datavalue":{"value":{"entity-type":"item","numeric-id":2843925,"id":"Q2843925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462389$BC88BCCB-F16B-4FE3-8EB2-771D832458ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eef11a2c1a563cf0a54618428c2d4fac93779880","datavalue":{"value":{"entity-type":"item","numeric-id":5431336,"id":"Q5431336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462389$6C69CFC0-847A-47B9-9EA1-DBCBF1FD68F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"beb2cb1e9d0e8c05bcb21866e6bafe1b44b6d41f","datavalue":{"value":{"entity-type":"item","numeric-id":4472509,"id":"Q4472509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462389$EF94D080-6E2E-4E8F-8468-597DFAB1AE05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ae02aa5e940aec926794a90179a0a928b044901","datavalue":{"value":{"entity-type":"item","numeric-id":4540043,"id":"Q4540043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462389$F3F22717-30AC-45B1-BD32-CC4456B7F87D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"377de45750c43b344ccb26bc903a8246bab12b20","datavalue":{"value":{"entity-type":"item","numeric-id":5687198,"id":"Q5687198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462389$D07ABE3E-5C16-4638-B40B-C742F98CEBD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f29fb4a42580a90bad5a386d83e8984d9dfa4645","datavalue":{"value":{"entity-type":"item","numeric-id":1607133,"id":"Q1607133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462389$762D7FE4-AB65-4D2A-9E77-17CA1D8494CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a791e6b13200f21127f48f475b5988c15175f95b","datavalue":{"value":{"entity-type":"item","numeric-id":5663889,"id":"Q5663889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462389$B57A57CA-CF1B-48B6-9D3D-A87A863CA0A9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"53fcaef7ffda8b7c59c30d46fee6c05cf1fb0b29","datavalue":{"value":"10.1016/J.DAM.2007.06.022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2462389$264314CF-458B-4759-89B3-1A655AF019E9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de4e12c4cf2f65f0fec438ed60607b8efc5b8059","datavalue":{"value":{"entity-type":"item","numeric-id":870842,"id":"Q870842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae7c8e7c222cf632a3a8c4cb9f3d1764304e738b","datavalue":{"value":{"amount":"+0.929449200630188","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":"Q2462389$89A44DF9-4B26-4598-984E-AB58A10D5AA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c8299340ff7da47998401e5b612f49d8b088253","datavalue":{"value":{"entity-type":"item","numeric-id":4785221,"id":"Q4785221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2851f8dad50e62d220af5c7ccdbd205d75aba793","datavalue":{"value":{"amount":"+0.8733330368995667","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":"Q2462389$BD99BB65-1730-4748-A1B5-9CAC46A7151A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9db18a133b3b1623f474acd4e435d81b2ea29423","datavalue":{"value":{"entity-type":"item","numeric-id":2434929,"id":"Q2434929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b871f846d51e72fd07a5742aae8483d0580a5b7","datavalue":{"value":{"amount":"+0.8609089255332947","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":"Q2462389$8CDCDB01-BFAB-4E6D-926A-DF46F4B6A453","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df59a9d76f30074335aadb263e8cfc70f84081de","datavalue":{"value":{"entity-type":"item","numeric-id":3010423,"id":"Q3010423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0432b661d80320389333cde22920ef1709528f00","datavalue":{"value":{"amount":"+0.8606155514717102","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":"Q2462389$258AB334-0859-4859-9E71-877B14078B4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a61bf9cb8a9f3d50bd25e60dc8036445a05b39b","datavalue":{"value":{"entity-type":"item","numeric-id":2482728,"id":"Q2482728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7500e74e1d4f57f750c598bfc494d1e6f616ada","datavalue":{"value":{"amount":"+0.8471762537956238","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":"Q2462389$A7483797-60C5-424C-9E4E-52572900D2B2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2462389","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2462389"}}}}}