{"entities":{"Q2706178":{"pageid":2716917,"ns":120,"title":"Item:Q2706178","lastrevid":47587903,"modified":"2026-01-02T03:57:20Z","type":"item","id":"Q2706178","labels":{"en":{"language":"en","value":"Graph searching and interval completion"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1578812"}},"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":"Q2706178$244AB830-5159-400C-989B-A32633E1254E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1eb79760d870438763d7866e59216a401f51cba9","datavalue":{"value":"0972.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706178$E331B6CB-6612-42B1-A1F2-58412A18AC10","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4ddb5c98cb49c4ea64f30a7e8f1bd3f538772354","datavalue":{"value":"10.1137/S0895480199350477","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706178$BB264932-9C49-4F49-A473-A9161C3FD16F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a8874875f41e100f7dd0c90f8e9a202da131938","datavalue":{"value":{"entity-type":"item","numeric-id":259035,"id":"Q259035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2706178$413CB2B3-82DB-4154-AA91-FDED3B917C72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a4df628262abf79464ed4f15ac79f197844f8c4","datavalue":{"value":{"entity-type":"item","numeric-id":259036,"id":"Q259036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2706178$54349E14-A814-4C98-937D-0FFD83C4604A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"39a509948a5fd41054da3e7af81581f39adaebc1","datavalue":{"value":{"entity-type":"item","numeric-id":2706174,"id":"Q2706174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2706178$79148694-A3B2-4FA9-AEA3-BFCE493E8A1E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0da0ddb63369ee51f0c4f965ee150089663821f4","datavalue":{"value":{"time":"+2001-03-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2706178$C7497C63-2840-47E4-86C7-EF6506EF9699","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706178$3DCFD36E-D3F1-4864-87C3-B71DACCA3074","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706178$B6F510E5-9DC7-41D8-8049-37F3D0E228BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706178$953F1D0A-28E1-4858-9FDA-2388C5EFBD27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706178$7B0E444F-3104-4EFB-A6E5-C0A07BFEBD63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706178$75AE6E94-D5EC-4B4F-B7E8-4A1B183243E3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2e0f2aaac0d9e96e76d2c63520b3cc868ff8eb98","datavalue":{"value":"1578812","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706178$BCE7795E-C8C5-40F5-B192-6A7B13C50C63","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b322c03f72bfbe9e7516683225803e7e94a5704f","datavalue":{"value":"graph searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706178$568142C4-D248-4F94-8235-6AAED8271E5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f7cd7c63144bb16d90c8ca1a3d41cff03976c5a","datavalue":{"value":"search cost","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706178$C2974FE3-80CC-4967-B417-B6BF3F0A7532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d41eb88fcb4ea694844c1f905b54cccc1e6a9310","datavalue":{"value":"vertex separation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706178$CE876401-F323-45AB-B044-D9D3FB092100","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16cea5a673a3b0765ca8d950b55366509c2d8f38","datavalue":{"value":"interval graph completion","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706178$ACFB7450-0126-407C-A427-15D2B4A1A7D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e9b546562afba9bfeebc045b4015b20a62d228a","datavalue":{"value":"linear layout","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706178$7600F18F-8DA7-4815-A189-2DDD38B4BDF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31cf470b52797086e1b2eada1cd4da1924faa5a0","datavalue":{"value":"profile","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706178$3D41E0C9-4D2A-44E6-9B3C-E029BAB98DFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ae14706edea88a102ee43da4032c363bf1c64c9","datavalue":{"value":"cograph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706178$EE7AA1C3-22B3-4FD8-BA85-36A5C1BA13F9","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":"Q2706178$6C8796D8-94C4-4BC2-A707-2C774D2701A8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d8964027fecd3dc82be1ff657ca5b27e44e9affb","datavalue":{"value":{"text":"Graph searching and interval completion","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2706178$4F46F896-9388-4E50-A8E3-2744140BFB3F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b960ea512d573091a01bbe962f5be326154415a0","datavalue":{"value":"In the classical node-search version for a finite simple undirected graph, in a sequence of moves, at every move a searcher is placed at a vertex or is removed from a vertex. Initially all edges are contaminated (uncleared). A contaminated edge \\(xy\\) is cleared if on \\(x\\) and \\(y\\) searchers are placed. A cleared edge \\(e\\) is recontaminated if there is a path without searchers between \\(e\\) and a contaminated edge.NEWLINENEWLINENEWLINEThe classical search problem is to find a sequence of moves (a node-search program) such that the maximum number of searchers used at any move is minimal. In this paper, node-search programs with minimal sum of numbers of searchers are studied, where the sum is taken over all moves. This criterion is called search cost.NEWLINENEWLINENEWLINEThe paper shows monotonicity properties (with respect to recontamination) of search programs with smallest cost. The search cost of a graph \\(G\\) turns out to be the smallest edge number of an interval supergraph of \\(G\\) as well as the vertex separation sum and the profile of \\(G\\). Finally, the paper shows how to compute the search cost of the product of graphs and the search cost of a cograph. The corresponding search program can be determined in linear time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706178$2F247173-459B-4227-BD9A-92FADBBF48CC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5af1aa80224172db75f7ae535f0d2940793ea880","datavalue":{"value":{"entity-type":"item","numeric-id":170457,"id":"Q170457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2706178$6FDC425D-6DFE-472B-8521-03F900394B99","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c92054174b4cabe6334e4b82a53eed6753f7780c","datavalue":{"value":{"entity-type":"item","numeric-id":1059088,"id":"Q1059088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc96286bf421bca1c7925293adead43f1da119d9","datavalue":{"value":{"amount":"+0.833443820476532","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":"Q2706178$AAD33ECC-0150-4DF4-9EEB-A8236BFD93B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e93a2c90fbeba53f70f038c2b7c5a0ec1f5823ef","datavalue":{"value":{"entity-type":"item","numeric-id":4242800,"id":"Q4242800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8940e00ddb5267503397f54002463408e1ba6159","datavalue":{"value":{"amount":"+0.8219496607780457","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":"Q2706178$7D01C33A-AF44-4179-9F19-05810C964879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95d59cd2b2503704cdcdd1d680fc99002ed67a63","datavalue":{"value":{"entity-type":"item","numeric-id":391138,"id":"Q391138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2041fb6c484c847e9a1dbd04a4e4b51281667c49","datavalue":{"value":{"amount":"+0.8186582326889038","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":"Q2706178$22357588-5E4D-455D-ACA7-35D1775E53AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc2672874165f597a33d21e70cc15d5c575a3171","datavalue":{"value":{"entity-type":"item","numeric-id":5897983,"id":"Q5897983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32f10fb8e8312c775b352a6700f375f41339c2c9","datavalue":{"value":{"amount":"+0.8063885569572449","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":"Q2706178$977E9716-C106-487A-9F3A-5EB05738AB07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63f74846ec578280ca252f32b4d1b66c0988a257","datavalue":{"value":{"entity-type":"item","numeric-id":5902509,"id":"Q5902509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0d36b89b6f71ff88185e238d4ad7d639708d6ad","datavalue":{"value":{"amount":"+0.7913650870323181","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":"Q2706178$F1E8A5FF-0C3E-4D60-894C-A75E457A8537","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2706178","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2706178"}}}}}