{"entities":{"Q1176719":{"pageid":1187468,"ns":120,"title":"Item:Q1176719","lastrevid":67039701,"modified":"2026-04-12T14:29:58Z","type":"item","id":"Q1176719","labels":{"en":{"language":"en","value":"A search problem on graphs which generalizes some group testing problems with two defectives"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 12436"}},"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":"Q1176719$DBFF23E5-6799-4BA7-AAD1-141D882D8B38","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7f7922c9e0ee368b4242bdb23a6cb8556a08a735","datavalue":{"value":{"text":"A search problem on graphs which generalizes some group testing problems with two defectives","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1176719$C46F46A0-EF89-48EE-8880-FEBD9224D67E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3c6863d2f4c551f55e5839262f44dae70edf3842","datavalue":{"value":"0747.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176719$87394071-7F14-415B-AA95-7F9361885711","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"31bf55e2f1acda6f4731169de3980d2ef7d83ff2","datavalue":{"value":"10.1016/0012-365X(91)90003-K","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176719$EB0F22C2-D054-4501-9660-F48F9BD81F2F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ea6c9e988b1a5ccaf11509582e9469b2e708609","datavalue":{"value":{"entity-type":"item","numeric-id":689954,"id":"Q689954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$8EC3ED53-D419-4F63-8F97-4AACC49A736D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$ACCA019F-B215-4F7C-905D-C1DB997594BA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1176719$FA044EB8-91D4-499F-9ABF-A9560471CC96","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d9f27699b7975941d555b3c85e503573a285983f","datavalue":{"value":"The author studies the problem of searching for an edge in a graph and tries to characterize classes of graphs with edges where \\([\\log_ 2 m]\\) tests suffice to find an arbitrary edge. Graphs having this property are called 2-optimal. Among other results it is shown that graphs are 2- optimal, if they are 2-orderable, i.e. their vertices can be arranged in a sequence \\(v_ 1,\\dots,v_ n\\) such that each \\(v_ i\\) has at most 2 direct neighbours among \\(v_ 1,\\dots,v_{i-1}\\). Furthermore, several upper bounds are given for the maximum number of tests in a search.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1176719$77C041A7-17FC-4009-AC46-2D1B67D2337C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176719$A865BA70-3A95-42BE-9076-0832422E1F92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176719$58F6AF71-D0C7-4F93-A759-0A0C231105FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176719$B07A8881-B580-4AB4-AC42-26EDDA7DC349","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"284b7bc3f3759535d2787178778b8e665ae82554","datavalue":{"value":"12436","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176719$0DA524AB-52D1-48C4-A6F8-F4AFD53CF70B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e0c7481e3c5c308fc47ea6e648bd33e7ea295f7","datavalue":{"value":"searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1176719$5B47E94F-221D-46AB-B021-E7F596273CCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b054bbd1ef16f604df0f61144322893e5b9a2a9","datavalue":{"value":"upper bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1176719$B9E232E0-27D3-42FC-80C4-360A241EA370","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"80e51cd7d7fb06dcf3d39ea7090bd669bdc6f79e","datavalue":{"value":{"entity-type":"item","numeric-id":789161,"id":"Q789161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$242E2F60-2810-4C46-92DD-6E1678A478BB","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":"Q1176719$92C5B950-D6FE-4D0C-914C-D72753140979","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1435c54d0e20d1dafd31cf861ac45c92c0347810","datavalue":{"value":{"entity-type":"item","numeric-id":3861131,"id":"Q3861131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$E9111AEF-E9AE-43DB-BF11-85E6244A10F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bf0286d6b735487227d24437e14202203ff14c8","datavalue":{"value":{"entity-type":"item","numeric-id":3050437,"id":"Q3050437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$94BA52AB-9A53-41A4-AF88-03E09507885A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea15ed0db24e5b282c459b65df0b30563ae6ddc8","datavalue":{"value":{"entity-type":"item","numeric-id":1082080,"id":"Q1082080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$48062759-B519-4363-9D1F-2D52324902DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bb05e105d0b783189108e5df4bac2153de9084e","datavalue":{"value":{"entity-type":"item","numeric-id":1118418,"id":"Q1118418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$0B10A3AB-A865-4579-BD13-E5800551941D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$8AA230D5-2CB2-4F7A-B4D0-2756EA3D9B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"029a9f29860baaa2d8f2be3c404465b07c99e374","datavalue":{"value":{"entity-type":"item","numeric-id":3964573,"id":"Q3964573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$0597A36F-7CBB-4405-975D-52CBA761E953","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e4380a0dd96952296b72164fdc8b7e12506dec7","datavalue":{"value":{"entity-type":"item","numeric-id":1164364,"id":"Q1164364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$D1F392CA-5520-4A11-8456-A020854749F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b5a77f691c73d3cc84a775a0deb455c68b0dbbc","datavalue":{"value":{"entity-type":"item","numeric-id":3241662,"id":"Q3241662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$4D9FDD3F-8468-4C1F-A2DF-B9D72D70B041","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df25916ae88cfd882e8cb6b5b5569c6957043ab0","datavalue":{"value":{"entity-type":"item","numeric-id":2394739,"id":"Q2394739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$D031CDA9-A1E0-4508-AFE7-CAE1B5E3FE82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"623aa0450604b7dbc9a31360325845e4adb61259","datavalue":{"value":{"entity-type":"item","numeric-id":5530478,"id":"Q5530478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$1ACD55AF-B465-4BF1-8A9B-0EBB89910C3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ff600c639285bb06593ca61942b0f485ac06878","datavalue":{"value":{"entity-type":"item","numeric-id":1202183,"id":"Q1202183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$3B781FF4-9901-4A3D-A134-52FB34734720","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef1e280ff313784cce95cf1dc6e1b139af0e3310","datavalue":{"value":{"entity-type":"item","numeric-id":5599569,"id":"Q5599569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$5F3C0046-CA29-49E9-9C8E-4ADDF1C80D80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"862a599e491eb36847da317e117b81da85af8a6f","datavalue":{"value":{"entity-type":"item","numeric-id":4097334,"id":"Q4097334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$D772E9C9-7F9C-424D-9574-559E77E0D051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20b852a7a28bbec3b861b12cebdf1e5b87806fca","datavalue":{"value":{"entity-type":"item","numeric-id":2645755,"id":"Q2645755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176719$44B6DCD4-B1A8-4280-A24D-1EFEBD39D0C7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c704bde1bd6e724ad45b5827daece5f26f3cb1f","datavalue":{"value":{"entity-type":"item","numeric-id":1024439,"id":"Q1024439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbf4793038b82367e0c3660d50e3692d1daae6b7","datavalue":{"value":{"amount":"+0.8741499185562134","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":"Q1176719$B29400AE-3620-4D6E-8035-CCBEACE2FF8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"094ccf0a34abdd88c8e441592f9682e466349b52","datavalue":{"value":{"entity-type":"item","numeric-id":1082080,"id":"Q1082080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de1ec0f6dd400ef4fc71bfc65ce1f9196a1e00e4","datavalue":{"value":{"amount":"+0.8667119741439819","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":"Q1176719$CD43F45A-83A9-424A-92D1-FD446FA1B2BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3d4251921992dc6252a30232eba36f46d01a49a","datavalue":{"value":{"entity-type":"item","numeric-id":1045083,"id":"Q1045083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e250e765a4e69db489151d82bd9b1f2aad17ed21","datavalue":{"value":{"amount":"+0.8647992014884949","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":"Q1176719$8E8E733F-8BA0-4A42-AB08-335E511B4146","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73f081c9e0ca1219c895756b6d1fba13742a0367","datavalue":{"value":{"entity-type":"item","numeric-id":411849,"id":"Q411849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2f18749a10126d9566de228dbced3bbb4465554","datavalue":{"value":{"amount":"+0.8483275771141052","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":"Q1176719$AC6A1442-55E6-4A40-A532-1B84BFF4B87A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e79fdc9e337743e14c46efa1886c9853eea6d274","datavalue":{"value":{"entity-type":"item","numeric-id":1315459,"id":"Q1315459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3f3b96369e18adabd65fd0c3ea123275b6424b8","datavalue":{"value":{"amount":"+0.831509530544281","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":"Q1176719$BD1E7E0B-5961-425E-B3F8-856C112D079A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A search problem on graphs which generalizes some group testing problems with two defectives","badges":[]}}}}}