{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T15:49:28Z","timestamp":1740152968832,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T00:00:00Z","timestamp":1555372800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T00:00:00Z","timestamp":1555372800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003382","name":"Core Research for Evolutional Science and Technology","doi-asserted-by":"publisher","award":["JPMJR1402"],"award-info":[{"award-number":["JPMJR1402"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17K00016","JP17K00024"],"award-info":[{"award-number":["JP17K00016","JP17K00024"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Rev Socionetwork Strat"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s12626-019-00036-2","type":"journal-article","created":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T08:03:57Z","timestamp":1555401837000},"page":"143-161","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Experimental Evaluation of Approximation and Heuristic Algorithms for Maximum Distance-Bounded Subgraph Problems"],"prefix":"10.1007","volume":"13","author":[{"given":"Yuichi","family":"Asahiro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomohiro","family":"Kubo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eiji","family":"Miyano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,16]]},"reference":[{"key":"36_CR1","unstructured":"Abello, J., Resende, M.G., Sudarsky, S. (2002). Massive quasi-clique detection. In: Proc of LATIN 2002 (pp. 598\u2013612). Springer."},{"issue":"1","key":"36_CR2","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1080\/0022250X.1973.9989826","volume":"3","author":"RD Alba","year":"1973","unstructured":"Alba, R. D. (1973). A graph-theoretic definition of a sociometric clique. Journal of Mathematical Sociology, 3(1), 113\u2013126.","journal-title":"Journal of Mathematical Sociology"},{"key":"36_CR3","unstructured":"Asahiro, Y., Doi, Y., Miyano, E., Shimizu, H. (2015). Optimal approximation algorithms for maximum distance-bounded subgraph problems. In: Proc of COCOA (pp. 586\u2013600). Springer."},{"issue":"6","key":"36_CR4","doi-asserted-by":"publisher","first-page":"1834","DOI":"10.1007\/s00453-017-0344-y","volume":"80","author":"Y Asahiro","year":"2018","unstructured":"Asahiro, Y., Doi, Y., Miyano, E., & Shimizu, H. (2018). Optimal approximation algorithms for maximum distance-bounded subgraph problems. Algorithmica, 80(6), 1834\u20131856.","journal-title":"Algorithmica"},{"key":"36_CR5","unstructured":"Asahiro, Y., Kubo, T., Miyano, E. (2016). Experimental evaluation of approximation algorithms for maximum distance-bounded subgraph problems. In: Proc of SCIS & ISIS (pp. 892\u2013897)."},{"key":"36_CR6","unstructured":"Asahiro, Y., Miyano, E., Samizo, K. (2010). Approximating maximum diameter-bounded subgraphs. In: Proc of LATIN 2010 (pp. 615\u2013626). Springer."},{"key":"36_CR7","unstructured":"Batagelj, V., Mrvar, A.: Graph files in bajek datasets. http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/pajek\/data\/gphs.htm . Accessed Dec 2018."},{"key":"36_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068","volume-title":"Random graphs","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B. (2001). Random graphs. Cambridge: Cambridge University Press."},{"key":"36_CR9","unstructured":"boost C++ Libraries \u2013 johnson\\_all\\_pairs\\_shortest\\_paths: http:\/\/www.boost.org\/doc\/libs\/1_60_0\/libs\/graph\/doc\/johnson_all_pairs_shortest.html . Accessed Nov 2017."},{"key":"36_CR10","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1016\/S0305-0548(99)00047-7","volume":"27","author":"JM Bourjolly","year":"2000","unstructured":"Bourjolly, J. M., Laporte, G., & Pesant, G. (2000). Heuristics for finding $$k$$-clubs in an undirected graph. Computers & Operations Research, 27, 559\u2013569.","journal-title":"Computers & Operations Research"},{"issue":"6","key":"36_CR11","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/0167-6377(90)90057-C","volume":"9","author":"R Carraghan","year":"1990","unstructured":"Carraghan, R., & Pardalos, P. (1990). An exact algorithm for the maximum clique problem. Operations Research Letters, 9(6), 375\u2013382.","journal-title":"Operations Research Letters"},{"key":"36_CR12","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P., & R\u00e9nyi, A. (1959). On random graphs I. Publicationes Mathematicae, 6, 290\u2013297.","journal-title":"Publicationes Mathematicae"},{"key":"36_CR13","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1006\/inco.1997.2620","volume":"134","author":"Z Galil","year":"1977","unstructured":"Galil, Z., & Margalit, O. (1977). All pairs shortest distances for graphs with small integer length edges. Information & Computation, 134, 103\u2013139.","journal-title":"Information & Computation"},{"key":"36_CR14","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1006\/jcss.1997.1385","volume":"54","author":"Z Galil","year":"1977","unstructured":"Galil, Z., & Margalit, O. (1977). All pairs shortest paths for graphs with small integer length edges. Journal of Computer and System Sciences, 54, 243\u2013254.","journal-title":"Journal of Computer and System Sciences"},{"key":"36_CR15","unstructured":"Grossman, J., Ion, P., Castro, R.: Erd\u0151s number project. https:\/\/oakland.edu\/enp\/ . Accessed Dec 2018."},{"issue":"2","key":"36_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1023\/B:HEUR.0000026264.51747.7f","volume":"10","author":"A Grosso","year":"2004","unstructured":"Grosso, A., Locatelli, M., & Croce, F. (2004). Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem. Journal of Heuristics, 10(2), 135\u2013152.","journal-title":"Journal of Heuristics"},{"issue":"1","key":"36_CR17","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J. (1999). Clique is hard to approximate within $$n^{1-\\varepsilon }$$. Acta Mathematics, 182(1), 105\u2013142.","journal-title":"Acta Mathematics"},{"key":"36_CR18","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Reducibility among combinatorial problems. Complexity of computer computations","author":"R Karp","year":"1972","unstructured":"Karp, R. (1972). Reducibility among combinatorial problems. Complexity of computer computations (pp. 85\u2013103). Boston: Springer."},{"issue":"5","key":"36_CR19","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1016\/j.ipl.2005.05.010","volume":"95","author":"K Katayama","year":"2005","unstructured":"Katayama, K., Hamamoto, A., & Narihisa, H. (2005). An effective local search for the maximum clique problem. Information Processing Letters, 95(5), 503\u2013511.","journal-title":"Information Processing Letters"},{"key":"36_CR20","doi-asserted-by":"crossref","unstructured":"Le\u00a0Gall, F. (2014) Powers of tensors and fast matrix multiplication. In: Proc of ISAAC, pp. 296\u2013303.","DOI":"10.1145\/2608628.2608664"},{"key":"36_CR21","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF02289146","volume":"14","author":"R Luce","year":"1949","unstructured":"Luce, R., & Perry, A. (1949). A method of matrix analysis of group structure. Psychometrika, 14, 95\u2013116.","journal-title":"Psychometrika"},{"issue":"2","key":"36_CR22","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02289199","volume":"15","author":"RD Luce","year":"1950","unstructured":"Luce, R. D. (1950). Connectivity and generalized cliques in sociometric group structure. Psychometrika, 15(2), 169\u2013190.","journal-title":"Psychometrika"},{"key":"36_CR23","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/S0012-365X(01)00091-7","volume":"244","author":"J Marin\u010dek","year":"2002","unstructured":"Marin\u010dek, J., & Mohar, B. (2002). On approximating the maximum diameter ratio of graphs. Discrete Mathematics, 244, 323\u2013330.","journal-title":"Discrete Mathematics"},{"issue":"1","key":"36_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10898-013-0075-9","volume":"59","author":"E Maslov","year":"2014","unstructured":"Maslov, E., Batsyn, M., & Pardalos, P. (2014). Speeding up branch and bound algorithms for solving the maximum clique problem. Journal of Global Optimization, 59(1), 1\u201321.","journal-title":"Journal of Global Optimization"},{"key":"36_CR25","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF00139635","volume":"13","author":"RJ Mokken","year":"1979","unstructured":"Mokken, R. J. (1979). Cliques, clubs and clans. Quality and Quantity, 13, 161\u2013173.","journal-title":"Quality and Quantity"},{"key":"36_CR26","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199233212.001.0001","volume-title":"The nature of computation","author":"C Moore","year":"2011","unstructured":"Moore, C., & Mertens, S. (2011). The nature of computation. Oxford: Oxford University Press."},{"issue":"1","key":"36_CR27","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(01)00290-6","volume":"120","author":"P \u00d6sterg\u0227rd","year":"2002","unstructured":"\u00d6sterg\u0227rd, P. (2002). A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120(1), 197\u2013207.","journal-title":"Discrete Applied Mathematics"},{"key":"36_CR28","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.disopt.2012.02.002","volume":"9","author":"FM Pajouh","year":"2012","unstructured":"Pajouh, F. M., & Balasundaram, B. (2012). On inclusionwise maximal and maximum cardinality $$k$$-clubs in graphs. Descrete Optimization, 9, 84\u201397.","journal-title":"Descrete Optimization"},{"issue":"4\u20135","key":"36_CR29","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1080\/15427951.2014.986778","volume":"11","author":"B Pattabiraman","year":"2015","unstructured":"Pattabiraman, B., Patwary, M. M. A., Gebremedhin, A. H., Liao, Wk, & Choudhary, A. (2015). Fast algorithms for the maximum clique problem on massive graphs with applications to overlapping community detection. Internet Mathematics, 11(4\u20135), 421\u2013448.","journal-title":"Internet Mathematics"},{"key":"36_CR30","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1995.1078","volume":"51","author":"R Seidel","year":"1995","unstructured":"Seidel, R. (1995). On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of Computer and System Sciences, 51, 400\u2013403.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"36_CR31","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0378-8733(83)90028-X","volume":"5","author":"SB Seidman","year":"1983","unstructured":"Seidman, S. B. (1983). Network structure and minimum degree. Social Networks, 5(3), 269\u2013287.","journal-title":"Social Networks"},{"issue":"1","key":"36_CR32","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1080\/0022250X.1978.9989883","volume":"6","author":"SB Seidman","year":"1978","unstructured":"Seidman, S. B., & Foster, B. L. (1978). A graph-theoretic generalization of the clique concept. Journal of Mathematical Sociology, 6(1), 139\u2013154.","journal-title":"Journal of Mathematical Sociology"},{"key":"36_CR33","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/s10878-012-9473-z","volume":"26","author":"S Shahinpour","year":"2013","unstructured":"Shahinpour, S., & Butenko, S. (2013). Algorithms for the maximum $$k$$-club problem in graphs. Journal of Combinatorial Optimization, 26, 520\u2013554.","journal-title":"Journal of Combinatorial Optimization"},{"key":"36_CR34","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/3-540-45066-1_22","volume-title":"Discrete Mathematics and Theoretical Computer Science","author":"Etsuji Tomita","year":"2003","unstructured":"Tomita, E., Seki, T. (2003). An efficient branch-and-bound algorithm for finding a maximum clique. In: Proc of DMTCS (pp. 278\u2013289)."},{"key":"36_CR35","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/978-3-642-11440-3_18","volume-title":"WALCOM: Algorithms and Computation","author":"Etsuji Tomita","year":"2010","unstructured":"Tomita, E., Sutani, Y., Higashi, T., Takahashi, S., Wakatsuki, M. (2010) A simple and faster branch-and-bound algorithm for finding a maximum clique. In: Proc of WALCOM (pp. 191\u2013203)."},{"key":"36_CR36","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D. (2007). Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3, 103\u2013128.","journal-title":"Theory of Computing"}],"container-title":["The Review of Socionetwork Strategies"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12626-019-00036-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12626-019-00036-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12626-019-00036-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T19:50:45Z","timestamp":1694807445000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12626-019-00036-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,16]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["36"],"URL":"https:\/\/doi.org\/10.1007\/s12626-019-00036-2","relation":{},"ISSN":["2523-3173","1867-3236"],"issn-type":[{"type":"print","value":"2523-3173"},{"type":"electronic","value":"1867-3236"}],"subject":[],"published":{"date-parts":[[2019,4,16]]},"assertion":[{"value":"25 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}