{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:47:17Z","timestamp":1764557237036,"version":"3.38.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,7,28]],"date-time":"2011-07-28T00:00:00Z","timestamp":1311811200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,1]]},"DOI":"10.1007\/s00224-011-9341-8","type":"journal-article","created":{"date-parts":[[2011,7,27]],"date-time":"2011-07-27T11:22:31Z","timestamp":1311765751000},"page":"158-184","source":"Crossref","is-referenced-by-count":27,"title":["Searching for Black Holes in Subways"],"prefix":"10.1007","volume":"50","author":[{"given":"Paola","family":"Flocchini","sequence":"first","affiliation":[]},{"given":"Matthew","family":"Kellett","sequence":"additional","affiliation":[]},{"given":"Peter C.","family":"Mason","sequence":"additional","affiliation":[]},{"given":"Nicola","family":"Santoro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,7,28]]},"reference":[{"key":"9341_CR1","first-page":"121","volume-title":"ICALP 2008: Proceedings of the 35th International Colloquium Automata, Languages and Programming","author":"C. Avin","year":"2008","unstructured":"Avin, C., Kouck\u00fd, M., Lotker, Z.: How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In: ICALP 2008: Proceedings of the 35th International Colloquium Automata, Languages and Programming, pp. 121\u2013132 (2008)"},{"key":"9341_CR2","first-page":"58","volume-title":"COCOA 2010: Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications","author":"B. Balamohan","year":"2010","unstructured":"Balamohan, B., Flocchini, P., Miri, A., Santoro, N.: Time optimal algorithms for black hole search in rings. In: COCOA 2010: Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications, pp. 58\u201371 (2010)"},{"issue":"2","key":"9341_CR3","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1142\/S0129054103001728","volume":"14","author":"B. Bui\u00a0Xuan","year":"2003","unstructured":"Bui\u00a0Xuan, B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci. 14(2), 267 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9341_CR4","first-page":"1","volume-title":"INFOCOM 2006: Proceedings of the 25th IEEE International Conference on Computer Communications","author":"J. Burgess","year":"2006","unstructured":"Burgess, J., Gallagher, B., Jensen, D., Levine, B.N.: MaxProp: routing for vehicle-based disruption-tolerant networks. In: INFOCOM 2006: Proceedings of the 25th IEEE International Conference on Computer Communications, pp. 1\u201311 (2006)"},{"key":"9341_CR5","first-page":"111","volume-title":"TCS 2010: Proceedings of the 6th IFIP International Conference on Theoretical Computer Science","author":"A. Casteigts","year":"2010","unstructured":"Casteigts, A., Flocchini, P., Mans, B., Santoro, N.: Deterministic computations in time-varying graphs: broadcasting under unstructured mobility. In: TCS 2010: Proceedings of the 6th IFIP International Conference on Theoretical Computer Science, pp. 111\u2013124 (2010)"},{"key":"9341_CR6","volume-title":"IPDPS 2011: Proceedings of the 25th IEEE International Parallel and Distributed Processing Symposium","author":"A. Casteigts","year":"2011","unstructured":"Casteigts, A., Flocchini, P., Mans, B., Santoro, N.: Measuring temporal lags in delay-tolerant networks. In: IPDPS 2011: Proceedings of the 25th IEEE International Parallel and Distributed Processing Symposium (2011)"},{"issue":"3","key":"9341_CR7","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1109\/COMST.2008.4625806","volume":"10","author":"A. Chaintreau","year":"2008","unstructured":"Chaintreau, A., Mtibaa, A., Massoulie, L., Diot, C.: The diameter of opportunistic mobile networks. Commun. Surv. Tutor. 10(3), 74\u201388 (2008)","journal-title":"Commun. Surv. Tutor."},{"key":"9341_CR8","first-page":"108","volume-title":"DISC 2007: Proceedings of the 21st International Symposium on Distributed Computing","author":"J. Chalopin","year":"2007","unstructured":"Chalopin, J., Das, S., Santoro, N.: Rendezvous of mobile agents in unknown graphs with faulty links. In: DISC 2007: Proceedings of the 21st International Symposium on Distributed Computing, pp. 108\u2013122 (2007)"},{"key":"9341_CR9","first-page":"320","volume-title":"OPODIS 2006: Proceedings of the 10th International Conference on Principles of Distributed Systems","author":"C. Cooper","year":"2006","unstructured":"Cooper, C., Klasing, R., Radzik, T.: Searching for black-hole faults in a network using multiple agents. In: OPODIS 2006: Proceedings of the 10th International Conference on Principles of Distributed Systems, pp. 320\u2013332 (2006)"},{"key":"9341_CR10","first-page":"20","volume-title":"SIROCCO 2008: Proceedings of the 15th International Colloquium on Structural Information and Communication Complexity","author":"C. Cooper","year":"2008","unstructured":"Cooper, C., Klasing, R., Radzik, T.: Locating and repairing faults in a network with mobile agents. In: SIROCCO 2008: Proceedings of the 15th International Colloquium on Structural Information and Communication Complexity, pp. 20\u201332 (2008)"},{"issue":"2, 3","key":"9341_CR11","doi-asserted-by":"crossref","first-page":"229","DOI":"10.3233\/FUN-2006-712-305","volume":"71","author":"J. Czyzowicz","year":"2006","unstructured":"Czyzowicz, J., Kowalski, D., Markou, E., Pelc, A.: Complexity of searching for a black hole. Fundam. Inform. 71(2, 3), 229\u2013242 (2006)","journal-title":"Fundam. Inform."},{"issue":"4","key":"9341_CR12","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1017\/S0963548306008133","volume":"16","author":"J. Czyzowicz","year":"2007","unstructured":"Czyzowicz, J., Kowalski, D., Markou, E., Pelc, A.: Searching for a black hole in synchronous tree networks. Comb. Probab. Comput. 16(4), 595\u2013619 (2007)","journal-title":"Comb. Probab. Comput."},{"issue":"2","key":"9341_CR13","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/net.20095","volume":"47","author":"S. Dobrev","year":"2006","unstructured":"Dobrev, S., Flocchini, P., Kralovic, R., Ruzicka, P., Prencipe, G., Santoro, N.: Black hole search in common interconnection networks. Networks 47(2), 61\u201371 (2006)","journal-title":"Networks"},{"issue":"1","key":"9341_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00446-006-0154-y","volume":"19","author":"S. Dobrev","year":"2006","unstructured":"Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Searching for a black hole in arbitrary networks: Optimal mobile agents protocols. Distrib. Comput. 19(1), 1\u201319 (2006)","journal-title":"Distrib. Comput."},{"issue":"1","key":"9341_CR15","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/s00453-006-1232-z","volume":"48","author":"S. Dobrev","year":"2007","unstructured":"Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Mobile search for a black hole in an anonymous ring. Algorithmica 48(1), 67\u201390 (2007)","journal-title":"Algorithmica"},{"issue":"6","key":"9341_CR16","doi-asserted-by":"crossref","first-page":"1355","DOI":"10.1142\/S0129054108006327","volume":"19","author":"S. Dobrev","year":"2008","unstructured":"Dobrev, S., Santoro, N., Shi, W.: Using scattered mobile agents to locate a black hole in an un-oriented ring with tokens. Int. J. Found. Comput. Sci. 19(6), 1355\u20131372 (2008)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9341_CR17","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Ilcinkas, D., Santoro, N.: Ping pong in dangerous graphs: optimal black hole search with pure tokens. Algorithmica (to appear). An earlier version appeared in DISC 2008","DOI":"10.1007\/978-3-540-87779-0_16"},{"key":"9341_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/IPDPS.2009.5161080","volume-title":"IPDPS 2009: Proceedings of the 23rd IEEE International Symposium on Parallel & Distributed Processing","author":"P. Flocchini","year":"2009","unstructured":"Flocchini, P., Kellett, M., Mason, P., Santoro, N.: Map construction and exploration by mobile agents scattered in a dangerous network. In: IPDPS 2009: Proceedings of the 23rd IEEE International Symposium on Parallel & Distributed Processing, pp. 1\u201310 (2009)"},{"key":"9341_CR19","first-page":"534","volume-title":"ISAAC 2009: Proceedings of the 20th International Symposium on Algorithms and Computation","author":"P. Flocchini","year":"2009","unstructured":"Flocchini, P., Mans, B., Santoro, N.: Exploration of periodically varying graphs. In: ISAAC 2009: Proceedings of the 20th International Symposium on Algorithms and Computation, pp. 534\u2013543 (2009)"},{"key":"9341_CR20","first-page":"128","volume-title":"ALGOSENSORS 2009: Proceedings of the 5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks","author":"P. Glaus","year":"2009","unstructured":"Glaus, P.: Locating a black hole without the knowledge of incoming links. In: ALGOSENSORS 2009: Proceedings of the 5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks, pp. 128\u2013138 (2009)"},{"key":"9341_CR21","first-page":"145","volume-title":"SIGCOMM 2004: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication","author":"S. Jain","year":"2004","unstructured":"Jain, S., Fall, K., Patra, R.: Routing in a delay tolerant network. In: SIGCOMM 2004: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, pp. 145\u2013158 (2004)"},{"issue":"8","key":"9341_CR22","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1109\/TMC.2007.1016","volume":"6","author":"E.P.C. Jones","year":"2007","unstructured":"Jones, E.P.C., Li, L., Schmidtke, J.K., Ward, P.A.S.: Practical routing in delay-tolerant networks. IEEE Trans. Mob. Comput. 6(8), 943\u2013959 (2007)","journal-title":"IEEE Trans. Mob. Comput."},{"issue":"2\u20133","key":"9341_CR23","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/j.tcs.2007.04.024","volume":"384","author":"R. Klasing","year":"2007","unstructured":"Klasing, R., Markou, E., Radzik, T., Sarracco, F.: Hardness and approximation results for black hole search in arbitrary networks. Theor. Comput. Sci. 384(2\u20133), 201\u2013221 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9341_CR24","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1002\/net.20233","volume":"52","author":"R. Klasing","year":"2008","unstructured":"Klasing, R., Markou, E., Radzik, T., Sarracco, F.: Approximation bounds for black hole search problems. Networks 52(4), 216\u2013226 (2008)","journal-title":"Networks"},{"key":"9341_CR25","first-page":"86","volume-title":"OPODIS 2009: Proceedings of the 13th International Conference on the Principles of Distributed Systems","author":"A. Kosowski","year":"2009","unstructured":"Kosowski, A., Navarra, A., Pinotti, M.C.: Synchronization helps robots to detect black holes in directed graphs. In: OPODIS 2009: Proceedings of the 13th International Conference on the Principles of Distributed Systems, pp. 86\u201398 (2009)"},{"issue":"9","key":"9341_CR26","doi-asserted-by":"crossref","first-page":"1325","DOI":"10.1109\/TPDS.2008.218","volume":"20","author":"C. Liu","year":"2009","unstructured":"Liu, C., Wu, J.: Scalable routing in cyclic mobile networks. IEEE Trans. Parallel Distrib. Syst. 20(9), 1325\u20131338 (2009)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"9341_CR27","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1145\/1080810.1080828","volume-title":"DIALM-POMC \u201905: Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing","author":"R. O\u2019Dell","year":"2005","unstructured":"O\u2019Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: DIALM-POMC \u201905: Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing, pp. 104\u2013110 (2005)"},{"key":"9341_CR28","first-page":"3","volume-title":"CHANTS 2007: Proceedings of the 2nd ACM Workshop on Challenged Networks","author":"R. Ramanathan","year":"2007","unstructured":"Ramanathan, R., Basu, P., Krishnan, R.: Towards a formalism for routing in challenged networks. In: CHANTS 2007: Proceedings of the 2nd ACM Workshop on Challenged Networks, pp. 3\u201310 (2007)"},{"key":"9341_CR29","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1145\/1287853.1287876","volume-title":"MobiCom \u201907: Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking","author":"X. Zhang","year":"2007","unstructured":"Zhang, X., Kurose, J., Levine, B.N., Towsley, D., Zhang, H.: Study of a bus-based disruption-tolerant network: mobility modeling and impact on routing. In: MobiCom \u201907: Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, pp. 195\u2013206 (2007)"},{"issue":"1","key":"9341_CR30","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/COMST.2006.323440","volume":"8","author":"Z. Zhang","year":"2006","unstructured":"Zhang, Z.: Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges. IEEE Commun. Surv. Tutor. 8(1), 24\u201337 (2006)","journal-title":"IEEE Commun. Surv. Tutor."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9341-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9341-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9341-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T20:24:10Z","timestamp":1741379050000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9341-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7,28]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["9341"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9341-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2011,7,28]]}}}