{"entities":{"Q1208460":{"pageid":1219209,"ns":120,"title":"Item:Q1208460","lastrevid":77960552,"modified":"2026-05-06T10:27:27Z","type":"item","id":"Q1208460","labels":{"en":{"language":"en","value":"Search and sweep numbers of finite directed acyclic graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 166461"}},"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":"Q1208460$DD71CB61-E398-4017-85E0-C51507EF009C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"14d983e10b402e1f198a228bc23e7b250e6d532d","datavalue":{"value":{"text":"Search and sweep numbers of finite directed acyclic graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1208460$408F0032-0913-4500-9A18-269FF8BC946E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"760b3665e8d5f86a30e601247f7c4595e6027179","datavalue":{"value":"0777.05062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208460$6D19E621-F3FE-4838-9D9F-5D5B4EF8C04F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d81503a3a824e5876e89318ff81509d81c866a85","datavalue":{"value":"10.1016/0166-218X(93)90242-G","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208460$58B2DFB6-C46B-4890-A740-113254013339","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":"Q1208460$F491EB0A-D97A-418E-BF78-9DAB54CA9587","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1208460$35B934E4-D03C-418A-83F2-9574B2BAF1B6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"74be03b5023e18dead965a9278d1a8267d97c0e5","datavalue":{"value":"Let a graph be taken as representing a set of rooms (vertices) and corridors (edges). The searchers who move with fixed speed, have to find an infinitely fast intruder. The search number \\(s(G)\\) of a graph \\(G\\) is the least number of searchers required to find any intruder. The sweep number \\(sw(G)\\) is the least number of searchers required if the searchers and intruder are constrained to the vertices (e.g. the edges may represent doors between rooms). In the paper finite directed acyclic graphs are considered. A searcher may slide along an edge only in the indicated direction. It is shown that the search number for such graphs can be found in polynomial time. Tight bounds are given for the sweep number and it is determined exactly for two classes of graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208460$74ADE638-27CB-4DAA-9678-D76487C5523B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208460$4D3EA248-5DA9-47C4-9639-A4B1DBAE3377","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"30d6d0de101c6ff200d712a6d7e331bcba20c783","datavalue":{"value":"90B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208460$4CD20BEC-7F35-40FB-B556-EF54A39CE4E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208460$6424C388-A617-472C-9320-8F835728D078","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8dede62f7bd3834f56c19ba3c37551c0ad824cb5","datavalue":{"value":"166461","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208460$0A4A8596-241E-4784-94E4-C45328C2F4E8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99fb8c69c202cd08d29b22488e32432b5a73c333","datavalue":{"value":"search number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208460$43713AF0-2B5D-42A3-868B-21997FFC7339","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"688d3c4c27cd602bcf5807f66663da34ba9dc312","datavalue":{"value":"sweep number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208460$0B3CAD17-1FBF-4B89-8491-CFF5139F325B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c2155b1f0f1b7934ea2f00e74be522bfbe52774","datavalue":{"value":"directed acyclic graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208460$95B9BB69-1080-4CF0-9DEC-C4980DCD3281","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5676fa5282611dbd0fab8edb7a4f82cf8ae7a025","datavalue":{"value":{"entity-type":"item","numeric-id":215016,"id":"Q215016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208460$2FA8103B-E2EB-411B-BCA4-29918AF4AFB7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8e5e75dedf8ab0bb7287ae40896accfbf134619f","datavalue":{"value":{"entity-type":"item","numeric-id":1770495,"id":"Q1770495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208460$BC03FA12-13AB-45F7-A631-E4BEE9977A2E","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":"Q1208460$F8650C62-D6B9-4710-B6DA-DEFCCA2DE9E8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f2df30c2d101f5dbca247effe5da6704181adb3","datavalue":{"value":{"entity-type":"item","numeric-id":2565249,"id":"Q2565249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208460$18928410-F2B0-405D-B819-5B754607012B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c10880db3512cb44b0c7a9adcd35842c8fcabb1c","datavalue":{"value":{"entity-type":"item","numeric-id":793755,"id":"Q793755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208460$C78B8ED4-70AE-4CFD-B165-FC85D0DE0CF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab7bf23ef18fe656ee82acb4586c7d9adb3e4719","datavalue":{"value":{"entity-type":"item","numeric-id":3217243,"id":"Q3217243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208460$50916919-0318-442B-ACA3-390C73F3397C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb35434071b02cad61f63c7cadd55ff55ed5a42d","datavalue":{"value":{"entity-type":"item","numeric-id":3740255,"id":"Q3740255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208460$CD3EF307-EDA9-42D9-86E7-B4A21F9F5768","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"007c64cb1e51e420a82b1528582743678952b922","datavalue":{"value":{"entity-type":"item","numeric-id":2648578,"id":"Q2648578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208460$F9DE3436-5182-481B-B427-8E19C0CCBA50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"256376258f0dacc6c84417f2d334937ae797b5c7","datavalue":{"value":{"entity-type":"item","numeric-id":1821562,"id":"Q1821562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208460$FCE945DD-DB70-4121-B8A7-DDB1B5514AA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6873e217fa14d8d61b078525075498902f69fdce","datavalue":{"value":{"entity-type":"item","numeric-id":3777477,"id":"Q3777477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208460$3D5B3E8B-7727-44B5-A30C-350C57BD2ED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcd7542caac5915c8f63a224b76605abf20c2235","datavalue":{"value":{"entity-type":"item","numeric-id":1837707,"id":"Q1837707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208460$7157370F-BAE6-4B69-8A6B-C7387FE719F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208460$AE7CF568-764E-48E4-86DE-1A2092842008","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1aec7a5195d839105a9eaed2e0df2aa8b7b1aebe","datavalue":{"value":{"entity-type":"item","numeric-id":4159394,"id":"Q4159394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208460$BAE848F4-9CFE-484A-AD68-38846B78E946","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e235b1e856f674628ea45299d84fda7e204eaef1","datavalue":{"value":{"entity-type":"item","numeric-id":3208679,"id":"Q3208679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208460$DDC76AD4-874B-4D32-98E7-03FA8BD20719","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a9d5296f40ff82792829067ac9320202d663622","datavalue":{"value":{"entity-type":"item","numeric-id":762182,"id":"Q762182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208460$AD920A80-5BCC-4FAF-ACA4-12DDE55C4E7B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11f270944d5c5bc486f8131dc09dfcd9dd085474","datavalue":{"value":{"entity-type":"item","numeric-id":3418339,"id":"Q3418339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b540094631d3c5a17e16dfa580ae9afcdd7bf041","datavalue":{"value":{"amount":"+0.8278083801269531","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":"Q1208460$E6C56131-270C-473C-A46D-B815C2EDF641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bff329ce37a0ece146a7f16ddaf9a760bd25d24","datavalue":{"value":{"entity-type":"item","numeric-id":1029267,"id":"Q1029267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46297b460492093546b5235679b897731987a302","datavalue":{"value":{"amount":"+0.8215075731277466","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":"Q1208460$9EDA961A-2940-4A9B-9087-14A996E8824E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7250d87628500fd8999cb5dbb3f70a60f79bbc14","datavalue":{"value":{"entity-type":"item","numeric-id":3777477,"id":"Q3777477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2097db85db16bb6e491b7c5bbd2f0a0fc9a2525b","datavalue":{"value":{"amount":"+0.8200774788856506","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":"Q1208460$66318097-EB78-479A-88BF-3E1A21002262","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b79a73cb841b0f0a5a8b8f2b9d922ae39b2bc82","datavalue":{"value":{"entity-type":"item","numeric-id":1821562,"id":"Q1821562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa50649bc1c505f3d708d25c00330aecbb874e93","datavalue":{"value":{"amount":"+0.7992801070213318","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":"Q1208460$8AF5BDA4-A9B3-4F1F-A796-8B7B95C7FCDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ddea3fe9d3e6d90006ad254c7a0bc1f66068a152","datavalue":{"value":{"entity-type":"item","numeric-id":944735,"id":"Q944735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd8b7e86361c7ff275613db0a66011fe7e8ad299","datavalue":{"value":{"amount":"+0.7991162538528442","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":"Q1208460$2411E2C0-7278-4DE3-A087-E1607D4DADAF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Search and sweep numbers of finite directed acyclic graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Search_and_sweep_numbers_of_finite_directed_acyclic_graphs"}}}}}