{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:13Z","timestamp":1750220653741,"version":"3.41.0"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,8,31]],"date-time":"2020-08-31T00:00:00Z","timestamp":1598832000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Queue"],"published-print":{"date-parts":[[2020,8,31]]},"abstract":"<jats:p>\n            Welcome to\n            <jats:italic>Drill Bits<\/jats:italic>\n            , a new column about programming. This inaugural episode shows how graph search algorithms can avoid unnecessary work. A simple modification to classic breadth-first search improves the lower bound on its running time: Whereas classic BFS always requires time proportional to the number of vertices plus the number of edges, the improved \"Efficient BFS\" sometimes runs in time proportional to the number of vertices alone. Both asymptotic analysis and experiments show that Efficient BFS can be much faster than classic BFS. All software used in the experiments is available for download, and suggestions for further explorations are provided.\n          <\/jats:p>","DOI":"10.1145\/3424302.3424304","type":"journal-article","created":{"date-parts":[[2020,9,13]],"date-time":"2020-09-13T22:05:40Z","timestamp":1600034740000},"page":"25-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Efficient Graph Search"],"prefix":"10.1145","volume":"18","author":[{"given":"Terence","family":"Kelly","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,9,13]]},"reference":[{"volume-title":"Network Flows (page 76)","author":"Ahuja R. K.","key":"e_1_2_1_1_1","unstructured":"Ahuja, R. K., Magnanti, T. L., Orlin, J. B. 1993. Network Flows (page 76). Upper Saddle River, NJ: Prentice Hall."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","unstructured":"Anderson E. Tucek J. 2010. Efficiency matters! SIGOPS Operating Systems Review 44(1):40?45; https:\/\/doi.org\/10.1145\/1740390.1740400.","DOI":"10.1145\/1740390.1740400"},{"key":"e_1_2_1_3_1","unstructured":"Boost graph library; https:\/\/dl.bintray.com\/boostorg\/release\/1.73.0\/source\/boost_1_73_0.tar.bz2."},{"volume-title":"Introduction to Algorithms","author":"Cormen T. H.","key":"e_1_2_1_4_1","unstructured":"Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. 2009. Introduction to Algorithms, third edition (page 595). Cambridge, MA: MIT Press."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","unstructured":"Dijkstra E. W. 1968. GOTO statement considered harmful. Communications of the ACM 11(3):147?148; https:\/\/doi.org\/10.1145\/362929.362947.","DOI":"10.1145\/362929.362947"},{"key":"e_1_2_1_6_1","unstructured":"GeeksforGeeks. Breadth-first search or BFS for a graph; https:\/\/www.geeksforgeeks.org\/breadth-first-search-or-bfs-for-a-graph\/."},{"volume-title":"Cracking the Coding Interview","author":"McDowell G. L.","key":"e_1_2_1_7_1","unstructured":"McDowell, G. L. 2016. Cracking the Coding Interview, sixth edition (page 108). Palo Alto, CA: CareerCup."},{"key":"e_1_2_1_8_1","unstructured":"McSherry F. Isard M. Murray D. G. 2015. Scalability! But at what COST? Usenix HotOS XV; https:\/\/www.usenix.org\/system\/files\/conference\/hotos15\/hotos15-paper-mcsherry.pdf."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001"},{"key":"e_1_2_1_10_1","unstructured":"Orwant J. Hietaniemi J. and John Macdonald J. 1999. Mastering Algorithms with Perl (page 307). O'Reilly."},{"volume-title":"Algorithms","author":"Sedgewick R.","key":"e_1_2_1_11_1","unstructured":"Sedgewick, R., Wayne, K. 2011. Algorithms, fourth edition (page 540). Addison-Wesley Professional."},{"key":"e_1_2_1_12_1","unstructured":"Wikipedia. Breadth-first search; https:\/\/en.wikipedia.org\/wiki\/Breadth-first_search"}],"container-title":["Queue"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3424302.3424304","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3424302.3424304","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:25Z","timestamp":1750197745000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3424302.3424304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,31]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8,31]]}},"alternative-id":["10.1145\/3424302.3424304"],"URL":"https:\/\/doi.org\/10.1145\/3424302.3424304","relation":{},"ISSN":["1542-7730","1542-7749"],"issn-type":[{"type":"print","value":"1542-7730"},{"type":"electronic","value":"1542-7749"}],"subject":[],"published":{"date-parts":[[2020,8,31]]},"assertion":[{"value":"2020-09-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}