{"entities":{"Q1082080":{"pageid":1092832,"ns":120,"title":"Item:Q1082080","lastrevid":70576389,"modified":"2026-04-13T15:33:30Z","type":"item","id":"Q1082080","labels":{"en":{"language":"en","value":"Search problems on graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3972203"}},"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":"Q1082080$87ADF8E0-9B83-4472-8F5D-DA459392E91A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e7533f1748ee55a02517855dbf847439b35af53b","datavalue":{"value":{"text":"Search problems on graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1082080$B0A60202-0D99-42D5-BA22-9A66213B5A5A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e314a0e354bbfa4839845cb763e5dc0cb2156915","datavalue":{"value":"0602.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082080$11CEBFC7-410B-480E-A410-A082F070BCB5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"663cef3ca9dd4617723a4dd97e0c9124d4b1fb68","datavalue":{"value":"10.1016/0166-218X(86)90026-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082080$0E98CB31-946F-4914-A008-74AC31800079","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"289d49a761dfac02c62be4b7f68381ebc5e52ce3","datavalue":{"value":{"entity-type":"item","numeric-id":495333,"id":"Q495333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082080$21B32522-CCE1-4669-A248-B773BC0B9A13","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":"Q1082080$060AEA6F-4049-4ACB-9136-552C2299327F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1082080$75749F2F-8E01-4AB6-AED6-E91620883B56","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"86f0a6f82300bc94b2ae47e16cd4522b8599e826","datavalue":{"value":"The following search problem on graphs is studied: given a graph \\(G=(V,E)\\) and an unknown edge \\(e\\in E\\), we can test whether a subset \\(A\\leq V\\) contains both ends of e, one end, or neither. The edge e is to be located with the minimum number of tests. When G is a complete graph, this is a classical problem of finding ''defectives'' in a population when at most two defectives are present. Lower and upper bounds for the minimum number of tests are derived for complete graphs and for complete bipartite graphs. These give the exact values for \\(K_{m,n}\\), \\(1\\leq m\\leq 4\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082080$AA8EF1E9-A104-4724-952C-286CD1EF7E7D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082080$044AB61E-1334-4592-BEFE-FF19C8A51852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082080$A8513C24-DAB0-4283-ACCE-B22D95445831","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6e61601cd41094c3d60d1b910c2d5f769c83f2cc","datavalue":{"value":"3972203","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082080$DA8F80B9-1D26-487F-A7CD-357EC9B80BF0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff57e61308315e7d839f45f98149a35fa3e4051d","datavalue":{"value":"search theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082080$9B402941-55F0-43DD-9EE9-3953B4298BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4e3931263c27b7a132d5d87cf7000f397c70495","datavalue":{"value":"group tests","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082080$985B9D7A-A165-451D-9178-016DAF47A86E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"012bdf1b14ad4ae91d5373002705261caea64c8b","datavalue":{"value":"complete graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082080$5728AECC-0B3E-4C2D-A74F-2EB668FB4CC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eecb173004633ca38efc326bcd073800d8b745c9","datavalue":{"value":"bipartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082080$ADDB59F1-5669-45E6-89E3-7A40C4889E3C","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":"Q1082080$AEF111DE-12E7-4BC3-BC56-934056FD9CC8","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":"Q1082080$28E17020-29A5-4691-98B4-F5FBB32F209A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7a6965487e66d7808fff55ef747487b9d8ee5a8","datavalue":{"value":{"entity-type":"item","numeric-id":5599181,"id":"Q5599181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082080$EC60F170-B66E-4C72-98D8-456ED316741B","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":"Q1082080$ACE4323E-D85F-4562-AFB3-B57265961FB5","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":"Q1082080$2B849E12-24CA-424A-A306-A3F9132437A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082080$91BE256D-9149-48CA-8425-524B037F7CA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"290a874e6b5defe246b06a0d481a3b05c781aa50","datavalue":{"value":{"entity-type":"item","numeric-id":5183260,"id":"Q5183260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082080$09DCF3B1-F1EB-4294-AE80-58D0872BE387","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74709a847cf2d3232582dba6a69cf2a7f5aec1e6","datavalue":{"value":{"entity-type":"item","numeric-id":5556461,"id":"Q5556461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082080$3CDD4D57-D74D-46D3-940C-4B17A69519CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98a49f4e67f5c571eb85fbd92a89f69c59b8cfb1","datavalue":{"value":{"entity-type":"item","numeric-id":2551781,"id":"Q2551781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082080$DE28D6F5-AC0D-48B6-9B1E-869DDF41D7B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21b9b607a619b214a7e2202022426e07ac7abf86","datavalue":{"value":{"entity-type":"item","numeric-id":4109144,"id":"Q4109144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082080$56FC27B7-FE92-47CD-92A1-CB4BF26B2681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d1c9edc710ee8436a565b3f4b9f414032bf9c94","datavalue":{"value":{"entity-type":"item","numeric-id":5550257,"id":"Q5550257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082080$5C6B61A0-5511-4297-94BE-0B35B0DE3E65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db8db57a920e535ad0bbb2a17e5279dbcf3f7817","datavalue":{"value":{"entity-type":"item","numeric-id":3244437,"id":"Q3244437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082080$012BF990-1CB0-48A7-9500-6267F03657B0","rank":"normal"}],"P1643":[{"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":"6cb03581bc129a8307ffa4e1dffe8d0ed82d187e","datavalue":{"value":{"amount":"+0.8872283697128296","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":"Q1082080$07AB6C9E-3528-425E-8A8E-3F78ED48A8DE","rank":"normal"},{"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":"5af2aef00d0a875ba58f113cfdc50ab33d216cf6","datavalue":{"value":{"amount":"+0.8699758648872375","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":"Q1082080$6BA6B038-50F6-4963-960C-8A1AFE89A29B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c738112e54abbae483a5af1dc833007c88b9e32d","datavalue":{"value":{"entity-type":"item","numeric-id":1176719,"id":"Q1176719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f29ab8874b7d2f6922727ba6d5f9042e976a8c8","datavalue":{"value":{"amount":"+0.8686266541481018","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":"Q1082080$29910D18-B9DA-4785-BE7A-3414B1471B0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2d127300d1224ce165d5fe2afe3d17323614c99","datavalue":{"value":{"entity-type":"item","numeric-id":1118418,"id":"Q1118418"},"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":"Q1082080$D9D0EB93-99A1-483D-98E2-64BB89DA5095","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c71a502bf95d8032d5bf5dca09578f43fe86a2b4","datavalue":{"value":{"entity-type":"item","numeric-id":1186168,"id":"Q1186168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ebb369d11fb294e1343510a010e80fd21929d1e","datavalue":{"value":{"amount":"+0.863362729549408","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":"Q1082080$E756B448-AC23-4842-9443-9C4117301F2E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Search problems on graphs","badges":[]}}}}}