{"entities":{"Q1960293":{"pageid":1971035,"ns":120,"title":"Item:Q1960293","lastrevid":51103022,"modified":"2026-01-16T16:43:38Z","type":"item","id":"Q1960293","labels":{"en":{"language":"en","value":"Complexity aspects of the Helly property: graphs and hypergraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5799464"}},"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":"Q1960293$D2A9382C-29AE-4F8D-B8CE-4385CE17E816","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3ed96368079b58b8ecc3e92f5421318e0454594a","datavalue":{"value":{"text":"Complexity aspects of the Helly property: graphs and hypergraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1960293$BE4A3E1E-5DF3-4F16-B3C6-937EB796DED5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"09cb466597f7264af20a942b492589290759e9eb","datavalue":{"value":"1206.05002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960293$D6D82F28-4228-4F5A-A9F7-B3274E1773E0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebc47ace17f1b2870aca70eb88a88e134b28d3a8","datavalue":{"value":{"entity-type":"item","numeric-id":277611,"id":"Q277611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960293$FC404C74-F8ED-4B56-BE28-D7867D2338A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d373f1f7d11dc13fa2018808ffc1e6b0723722cd","datavalue":{"value":{"entity-type":"item","numeric-id":247856,"id":"Q247856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960293$83E09E06-4D04-4AC0-BD60-6D443069AD51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fd683c02639d43389eac3b26f5a1a60d6fdb0bf1","datavalue":{"value":{"entity-type":"item","numeric-id":712274,"id":"Q712274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960293$65DF1465-B59F-4303-9458-A5C5495F664D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960293$435E470E-DB2F-49A3-85E3-1B697F025C64","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5bc825493bb220acb505797bc531e77eaaee5ef2","datavalue":{"value":{"time":"+2010-10-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1960293$4BD240DF-D163-4466-916F-4D002EB605DA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9e98c8b0af0c117067a3a376cedac3fb9ac358fe","datavalue":{"value":"https://eudml.org/doc/222810","type":"string"},"datatype":"url"},"type":"statement","id":"Q1960293$464A0D30-3C50-4116-B5B6-11D7084A2863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"4524916fa6b507266dbf639f985ccf2975f6bd1c","datavalue":{"value":"http://www.emis.de/journals/EJC/Surveys/index.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1960293$EE70DBA1-4652-4F3A-BE08-72E00C182B6F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8e88f813ebb8ee6d971b0cbb6b232262050ec4a0","datavalue":{"value":"A family of sets has the \\(k\\)-Helly property iff each finite subfamily, of which every \\(k\\) members have nonempty intersection, has a common element. This originates in Helly's theorem of 1923 asserting that the family of convex sets in \\(\\mathbb{R}^n\\) has the \\((n+1)\\)-Helly property.    This survey, based upon 106 references, summarizes results on the \\(k\\)-Helly property and on variants of it concerning graphs and hypergraphs. It focusses especially on recognition algorithms and their complexity for families of graphs and of hypergraphs having some special Helly property. A table of 33 entries lists the complexity results of these algorithms, some being NP-hard and some NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960293$1E7DC8AA-76DE-4638-9A32-82DA10C9278F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5106252eb72617afc052c075699a4fbf786bbc66","datavalue":{"value":"05-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960293$668128E2-6D68-47C6-ADF3-031636D9EDAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960293$E94F8B07-F593-4DF9-B985-79BB5DCDDF85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960293$C2682DB0-4FDA-4102-BEC7-757E5B98FD71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e2385123772333afaee3f2a564b5a88a1933f934","datavalue":{"value":"52A35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960293$3E36A8FA-C770-497B-8953-41F98AC62CD3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"57adf8cd015892b31e1e4a9e4b2c6661cf6dd01e","datavalue":{"value":"5799464","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960293$B1CBB934-F1B3-4CA2-BB3D-BC62247C5080","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af787d1b4b14af1c021acee5efc3a18774584b59","datavalue":{"value":"Helly property","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960293$A205A282-64B8-47CE-BB56-C7A24CD73442","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7decde45aa28f7520212fb84cab816519940f4c9","datavalue":{"value":"recognition algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960293$2D066FBF-FB0F-46FA-A1AC-9FF07ED3B985","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960293$E07B0923-5363-4DCB-92C8-E18C89731B63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960293$592252C1-9787-4AD3-940C-F7365A8C16C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960293$95A70DE9-D1DA-44F6-BBB0-B7A95C27879F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"84719a152f3d80016cc596ed87fee134f8b91808","datavalue":{"value":{"entity-type":"item","numeric-id":703682,"id":"Q703682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960293$C1D0A6A5-6082-4462-A6F3-04DD576E9661","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":"Q1960293$D7296851-E35E-4EBF-87A3-84475D4D4F4D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc73379f285d7e80c27852ae021c31afe0b35e8c","datavalue":{"value":{"entity-type":"item","numeric-id":412268,"id":"Q412268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87b6a75f52d5f0970b3c1d022b05e9900fe4b8e8","datavalue":{"value":{"amount":"+0.8474035263061523","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":"Q1960293$78EACC7B-5515-4959-B475-7DC53EAECC11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56df3026eb9458c039e922d42af6e05b9e2129a3","datavalue":{"value":{"entity-type":"item","numeric-id":845662,"id":"Q845662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68a6e5b272bd308497f28a1eaf0e9f545c2812c0","datavalue":{"value":{"amount":"+0.836586058139801","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":"Q1960293$35C79B4C-8A89-45F6-8E6F-A074A984A493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb3afa9ac1c029c25bee9fffcc3e4df5da52a004","datavalue":{"value":{"entity-type":"item","numeric-id":2851534,"id":"Q2851534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2477abcf79f6a91f1e373fc059e93a540ead1f60","datavalue":{"value":{"amount":"+0.8333213329315186","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":"Q1960293$D104FFF2-9E94-4F71-8112-EE5BF3734F97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"342d0a7ba7583e7afd4f18d61f5f84ebc258da48","datavalue":{"value":{"entity-type":"item","numeric-id":4940014,"id":"Q4940014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a96ec613130fdf8be2bccf868f0142996fffc88","datavalue":{"value":{"amount":"+0.8275281190872192","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":"Q1960293$1677B58C-5C61-4D77-8BA8-7ED8F61ED63F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9723f6f23cbfbf5b1ff368a21fd7f12f7c8dff38","datavalue":{"value":{"entity-type":"item","numeric-id":2689646,"id":"Q2689646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffcfdeabf05a58e8067f68c2052099cf05c70d30","datavalue":{"value":{"amount":"+0.82631516456604","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":"Q1960293$75BBC62E-7225-4BFE-BDEF-89DAE3C047F9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1960293","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1960293"}}}}}