{"entities":{"Q975761":{"pageid":977609,"ns":120,"title":"Item:Q975761","lastrevid":51008876,"modified":"2026-01-16T04:53:38Z","type":"item","id":"Q975761","labels":{"en":{"language":"en","value":"Galaxy cutsets in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5719880"}},"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":"Q975761$CE850B25-BB7C-474E-AAE2-BBB66FD61AE5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"85635b584d3c3643ddd0dbda6e88096c54e3b61e","datavalue":{"value":{"text":"Galaxy cutsets in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q975761$6276C625-9D5F-4610-B6F4-E2CC55A2665D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"846e60bc5b4050e979696f072e505703e23da0fa","datavalue":{"value":"1208.05065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q975761$A3CBB2C9-9708-47E0-8483-BC4FC15F3325","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"779a379499a738dd87db247844b94582c96d28c7","datavalue":{"value":{"entity-type":"item","numeric-id":975760,"id":"Q975760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q975761$F5EDB930-217B-4B56-B98B-65E7E1A225E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b98dfd69e695d361ad845eeb3c42cf13105fa89d","datavalue":{"value":{"entity-type":"item","numeric-id":487015,"id":"Q487015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q975761$323EE34A-DF71-4E21-BCFA-250CC15A240E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dcf8815e3b257674fa147da7a4e7c92c91c0b3e3","datavalue":{"value":{"entity-type":"item","numeric-id":185429,"id":"Q185429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q975761$F5ED1762-818C-4587-A4AF-907BFE620477","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8330f0162b04ee97697b5c3b59dea76e14d14e04","datavalue":{"value":{"time":"+2010-06-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q975761$B2AD1588-0809-435F-BAD4-38F757C32D40","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"31cdb8d90e5fd5ae89a5049bc369d9e3e421a13c","datavalue":{"value":"Given a network \\(G=(V(G),E(G))\\), a subset of vertices \\(S\\) of \\(V(G)\\) that is spanned by a tree of depth at most\\( \\)r is called to have radius \\(r\\). The authors discus graphs \\(G\\) where \\(G\\) has a cutset that can be written as the union of \\(k\\) sets of radius \\(r\\). A cutset which is the union of \\(k\\) stars is called a galaxy The main result of this paper is the following: It is NP-hard to determine whether a given network contains a galaxy cutset of order \\(k\\), if k is part of the input.","type":"string"},"datatype":"string"},"type":"statement","id":"Q975761$5FE1CA5C-68F0-4B5A-99AB-18F2CC6D7681","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5bf98c249556a3cbdf1ccaf58ec85cdce76ec514","datavalue":{"value":{"entity-type":"item","numeric-id":593214,"id":"Q593214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q975761$8E5545B9-D424-4A9D-B61E-EB41BF9C2E9F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q975761$C75150F4-90B1-4630-8E1B-C712E8638D7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q975761$149CAE75-F946-440C-A6EE-D407BBAF7E22","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"118d33f05d8b59855b6eb16ebae563acf40af007","datavalue":{"value":"5719880","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q975761$99787837-F1D8-4F12-8B42-9BBEDF207640","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1cbbec3018eb60e4a984891b43aa085b422863c7","datavalue":{"value":"network connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q975761$DDC884B5-556F-46D2-A5C6-06B55338C913","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63f88f8c41a8d8412c18444827d7670b7506a03a","datavalue":{"value":"galaxy cutsets","type":"string"},"datatype":"string"},"type":"statement","id":"Q975761$8E29F757-0D59-4984-A691-71DC135578D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e59ab4cef7cd7bd1deaf8f4d65a8a3536906120","datavalue":{"value":"denial of service attacks","type":"string"},"datatype":"string"},"type":"statement","id":"Q975761$B0204D0B-132A-4D18-9BAC-11E7FAD71C16","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":"Q975761$00058E86-86C0-4CD5-921C-89F209246EBF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ea3196392574ec107f440e2a0882e31bbddc4a4b","datavalue":{"value":"https://doi.org/10.1007/s10878-009-9258-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q975761$8E07C1A1-8174-46D7-AA57-21FCAB00FBC8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e06e808375c8a36969d0467ba0e5899d36d19e30","datavalue":{"value":"W2000364035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q975761$8DDF87AA-1DFD-417F-8794-9EA2B352FB04","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1234570f11caddb900135131d2fd06479f5792ac","datavalue":{"value":{"entity-type":"item","numeric-id":1772458,"id":"Q1772458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q975761$F015D6D1-EBE2-443E-AAE9-720331023AD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"377fc7d6f0f87cd999526d782ba240d822d49abd","datavalue":{"value":{"entity-type":"item","numeric-id":1121289,"id":"Q1121289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q975761$E9DEDE3D-EB92-4CCC-A9FC-B53F03E77019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6b4a9ae60aca210a1cbb562981e1a5d018a9220","datavalue":{"value":{"entity-type":"item","numeric-id":3589871,"id":"Q3589871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q975761$F81E037F-E28C-43AA-85AF-972C606826AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c028844c09fc58ee4ae2ae9e9ef7a8fd66f0aee","datavalue":{"value":{"entity-type":"item","numeric-id":2370449,"id":"Q2370449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q975761$2A75CB7A-B4FE-4F77-8740-8B1754577A55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"858d860865dcbd1a4805d33046728c208c106355","datavalue":{"value":{"entity-type":"item","numeric-id":1074600,"id":"Q1074600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q975761$F82424B3-4BEC-48C2-9E51-18003C46912F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be5f1aa9294846cde8376d837af26608b9f41054","datavalue":{"value":{"entity-type":"item","numeric-id":2941641,"id":"Q2941641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q975761$F47FD66D-EA06-4B2A-86F2-A5AB36DD4CD7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4b4d13ce6ad6a99d59b2b9f4476f25675c447fce","datavalue":{"value":"10.1007/S10878-009-9258-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q975761$B00AC200-05A9-4883-87AE-62BD0D186638","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ef9042a00df80de044a987db8bcec8846d776da","datavalue":{"value":{"entity-type":"item","numeric-id":2851448,"id":"Q2851448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc9e15425506ec859614c9fa9173fe59b4f2dd2c","datavalue":{"value":{"amount":"+0.705649197101593","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":"Q975761$025C9E08-76E3-4F3D-A0E0-137CB806C896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"597971f83374b2868144fbb5b41a66bae9e14bb8","datavalue":{"value":{"entity-type":"item","numeric-id":2419357,"id":"Q2419357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9813c3e29c2dd60dd034b07d5aaa922a33f70d14","datavalue":{"value":{"amount":"+0.7026011347770691","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":"Q975761$0EEF608D-B2E6-4209-9526-F85205A32926","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fabca1b85e0456762c129b157d02c93f327bbdf","datavalue":{"value":{"entity-type":"item","numeric-id":415275,"id":"Q415275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70aa959a6488ebc943e7193ad14bbef946bae175","datavalue":{"value":{"amount":"+0.701083242893219","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":"Q975761$6D1CF5FB-8C31-4B59-8257-8D0B029DD769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7471a5203c09b066f93344ea81c30103b3fbd7d4","datavalue":{"value":{"entity-type":"item","numeric-id":1582067,"id":"Q1582067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb496daa63f9988b694e8735de487e4143a70e5e","datavalue":{"value":{"amount":"+0.7003121972084045","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":"Q975761$714C152D-198C-4CA2-AE90-7A9121C10164","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"132f72f339f118f918a5f12114294466a80093ab","datavalue":{"value":{"entity-type":"item","numeric-id":2277496,"id":"Q2277496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3e1fa34d6d2453768d73117547862a2c593d5aa","datavalue":{"value":{"amount":"+0.6997237205505371","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":"Q975761$FC88FFED-1CCE-4A28-BBF4-5ECC703DB052","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:975761","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:975761"}}}}}