{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T11:44:42Z","timestamp":1775648682420,"version":"3.50.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,4,16]],"date-time":"2024-04-16T00:00:00Z","timestamp":1713225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,4,16]],"date-time":"2024-04-16T00:00:00Z","timestamp":1713225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Genet Program Evolvable Mach"],"published-print":{"date-parts":[[2024,6]]},"DOI":"10.1007\/s10710-024-09487-1","type":"journal-article","created":{"date-parts":[[2024,4,16]],"date-time":"2024-04-16T02:01:25Z","timestamp":1713232885000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Hierarchical non-dominated sort: analysis and improvement"],"prefix":"10.1007","volume":"25","author":[{"given":"Ved","family":"Prakash","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sumit","family":"Mishra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,4,16]]},"reference":[{"issue":"4","key":"9487_CR1","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/s40747-017-0057-5","volume":"3","author":"Y Tian","year":"2017","unstructured":"Y. Tian, H. Wang, X. Zhang, Y. Jin, Effectiveness and efficiency of non-dominated sorting for evolutionary multi-and many-objective optimization. Complex Intell. Syst. 3(4), 247\u2013263 (2017)","journal-title":"Complex Intell. Syst."},{"issue":"2","key":"9487_CR2","doi-asserted-by":"publisher","first-page":"1001","DOI":"10.3934\/jimo.2020009","volume":"17","author":"Q Long","year":"2021","unstructured":"Q. Long, X. Wu, C. Wu, Non-dominated sorting methods for multi-objective optimization: review and numerical comparison. J. Ind. Manag. Optim. 17(2), 1001 (2021)","journal-title":"J. Ind. Manag. Optim."},{"issue":"2","key":"9487_CR3","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1109\/4235.996017","volume":"6","author":"K Deb","year":"2002","unstructured":"K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evolut. Comput. 6(2), 182\u2013197 (2002)","journal-title":"IEEE Trans. Evolut. Comput."},{"key":"9487_CR4","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.jocs.2017.09.015","volume":"23","author":"C Bao","year":"2017","unstructured":"C. Bao, L. Xu, E.D. Goodman, L. Cao, A novel non-dominated sorting algorithm for evolutionary multi-objective optimization. J. Comput. Sci. 23, 31\u201343 (2017)","journal-title":"J. Comput. Sci."},{"key":"9487_CR5","doi-asserted-by":"crossref","unstructured":"P. Nigam, S. Mishra, Counterexample to the best-case running time of efficient non-dominated sorting algorithm, in Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u20192022) (2022), pp. 798\u2013800","DOI":"10.1145\/3520304.3528777"},{"issue":"2","key":"9487_CR6","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1109\/TEVC.2014.2308305","volume":"19","author":"X Zhang","year":"2015","unstructured":"X. Zhang, Y. Tian, R. Cheng, J. Yaochu, An efficient approach to nondominated sorting for evolutionary multiobjective optimization. IEEE Trans. Evolut. Comput. 19(2), 201\u2013213 (2015)","journal-title":"IEEE Trans. Evolut. Comput."},{"issue":"3","key":"9487_CR7","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1162\/evco.1994.2.3.221","volume":"2","author":"N Srinivas","year":"1994","unstructured":"N. Srinivas, K. Deb, Multiobjective optimization using nondominated sorting in genetic algorithms. Evolut. Comput. 2(3), 221\u2013248 (1994)","journal-title":"Evolut. Comput."},{"key":"9487_CR8","doi-asserted-by":"crossref","unstructured":"W. Habenicht, Quad trees, a datastructure for discrete vector optimization problems, in Essays and Surveys on Multiple Criteria Decision Making: International Conference on Multiple Criteria Decision Making (Springer, 1983), pp. 136\u2013145","DOI":"10.1007\/978-3-642-46473-7_12"},{"issue":"4","key":"9487_CR9","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1287\/ijoc.8.4.367","volume":"8","author":"M Sun","year":"1996","unstructured":"M. Sun, R.E. Steuer, Quad-trees and linear lists for identifying nondominated criterion vectors. INFORMS J. Comput. 8(4), 367\u2013375 (1996)","journal-title":"INFORMS J. Comput."},{"key":"9487_CR10","doi-asserted-by":"crossref","unstructured":"S. Mostaghim, J. Teich, Quad-trees: a data structure for storing pareto sets in multiobjective evolutionary algorithms with elitism, in Evolutionary Multiobjective Optimization: Theoretical Advances and Applications (Springer, 2005), pp. 81\u2013104","DOI":"10.1007\/1-84628-137-7_5"},{"issue":"3","key":"9487_CR11","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1016\/0377-2217(94)00228-2","volume":"89","author":"M Sun","year":"1996","unstructured":"M. Sun, R.E. Steuer, InterQuad: an interactive quad tree based procedure for solving the discrete alternative multiple criteria problem. Eur. J. Oper. Res. 89(3), 462\u2013472 (1996)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"9487_CR12","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1109\/TEVC.2003.810733","volume":"7","author":"JE Fieldsend","year":"2003","unstructured":"J.E. Fieldsend, R.M. Everson, S. Singh, Using unconstrained elite archives for multiobjective optimization. IEEE Trans. Evolut. Comput. 7(3), 305\u2013323 (2003)","journal-title":"IEEE Trans. Evolut. Comput."},{"key":"9487_CR13","doi-asserted-by":"crossref","unstructured":"O. Sch\u00fctze, A new data structure for the nondominance problem in multi-objective optimization, in International Conference on Evolutionary Multi-Criterion Optimization (Springer, 2003), pp. 509\u2013518","DOI":"10.1007\/3-540-36970-8_36"},{"key":"9487_CR14","unstructured":"X. Chen, Pareto tree searching genetic algorithm: approaching pareto optimal front by searching pareto optimal tree. Technical Report NK-CS-2001-002, 1\u201310 (2001)"},{"issue":"5","key":"9487_CR15","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1109\/TEVC.2014.2366498","volume":"19","author":"M Drozdik","year":"2015","unstructured":"M. Drozdik, Y. Akimoto, H. Aguirre, K. Tanaka, Computational cost reduction of nondominated sorting using the M-Front. IEEE Trans. Evolut. Comput. 19(5), 659\u2013678 (2015)","journal-title":"IEEE Trans. Evolut. Comput."},{"issue":"5","key":"9487_CR16","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1109\/TEVC.2018.2799684","volume":"22","author":"A Jaszkiewicz","year":"2018","unstructured":"A. Jaszkiewicz, T. Lust, ND-Tree-based update: a fast algorithm for the dynamic nondominance problem. IEEE Trans. Evolut. Comput. 22(5), 778\u2013791 (2018)","journal-title":"IEEE Trans. Evolut. Comput."},{"issue":"1","key":"9487_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/EVCO_a_00041","volume":"20","author":"K McClymont","year":"2012","unstructured":"K. McClymont, E. Keedwell, Deductive sort and climbing sort: new methods for non-dominated sorting. Evolut. Comput. 20(1), 1\u201326 (2012)","journal-title":"Evolut. Comput."},{"issue":"1","key":"9487_CR18","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1162\/evco_a_00204","volume":"26","author":"P Gustavsson","year":"2018","unstructured":"P. Gustavsson, A. Syberfeldt, A new algorithm using the non-dominated tree to improve non-dominated sorting. Evolut. Comput. 26(1), 89\u2013116 (2018)","journal-title":"Evolut. Comput."},{"issue":"1","key":"9487_CR19","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1109\/TEVC.2016.2600642","volume":"22","author":"X Zhang","year":"2018","unstructured":"X. Zhang, Y. Tian, R. Cheng, Y. Jin, A decision variable clustering-based evolutionary algorithm for large-scale many-objective optimization. IEEE Trans. Evolut. Comput. 22(1), 97\u2013112 (2018)","journal-title":"IEEE Trans. Evolut. Comput."},{"key":"9487_CR20","doi-asserted-by":"crossref","unstructured":"S. Mishra, S. Saha, S. Mondal, Divide and conquer based non-dominated sorting for parallel environment, in IEEE Congress on Evolutionary Computation (CEC\u20192016) (IEEE Press, 2016), pp. 4297\u20134304. ISBN: 978-1-5090-0623-6","DOI":"10.1109\/CEC.2016.7744336"},{"key":"9487_CR21","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1016\/j.swevo.2018.08.011","volume":"44","author":"S Mishra","year":"2019","unstructured":"S. Mishra, S. Saha, S. Mondal, C.A. Coello Coello, A divide-and-conquer based efficient non-dominated sorting approach. Swarm Evolut. Comput. 44, 748\u2013773 (2019)","journal-title":"Swarm Evolut. Comput."},{"issue":"9","key":"9487_CR22","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JL Bentley","year":"1975","unstructured":"J.L. Bentley, Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509\u2013517 (1975)","journal-title":"Commun. ACM"},{"key":"9487_CR23","volume-title":"An Introduction to Data Structures and Algorithms","author":"JA Storer","year":"2001","unstructured":"J.A. Storer, An Introduction to Data Structures and Algorithms (Springer, Birkh\u00e4user, Boston, 2001)"},{"key":"9487_CR24","doi-asserted-by":"crossref","unstructured":"F.L. Heller, A.L. Tharp, The* M-ary Tree and* ternary hillsort, in Proceedings of the 1992 ACM Annual Conference on Communications (1992), pp. 41\u201348","DOI":"10.1145\/131214.131220"},{"issue":"1","key":"9487_CR25","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1109\/TEVC.2016.2567648","volume":"21","author":"Y Zhou","year":"2017","unstructured":"Y. Zhou, Z. Chen, J. Zhang, Ranking vectors by means of the dominance degree matrix. IEEE Trans. Evolut. Comput. 21(1), 34\u201351 (2017)","journal-title":"IEEE Trans. Evolut. Comput."},{"key":"9487_CR26","doi-asserted-by":"crossref","unstructured":"P.C. Roy, M.M. Islam, K. Deb, Best order sort: a new algorithm to non-dominated sorting for evolutionary multi-objective optimization, in Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u20192016) (ACM Press, Denver, 2016), pp. 1113\u20131120. ISBN: 978-1-4503-4323-7","DOI":"10.1145\/2908961.2931684"},{"key":"9487_CR27","doi-asserted-by":"crossref","unstructured":"S. Mishra, S. Saha, S. Mondal, MBOS: modified best order sort algorithm for performing non-dominated sorting, in IEEE Congress on Evolutionary Computation (CEC\u20192018) (IEEE Press, Rio de Janeiro, 2018), pp. 725\u2013732. ISBN: 978-1-5090-6017-7","DOI":"10.1109\/CEC.2018.8477804"},{"key":"9487_CR28","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/j.swevo.2018.06.003","volume":"43","author":"S Mishra","year":"2018","unstructured":"S. Mishra, S. Mondal, S. Saha, C.A. Coello Coello, GBOS: generalized best order sort algorithm for non-dominated sorting. Swarm Evolut. Comput. 43, 244\u2013264 (2018)","journal-title":"Swarm Evolut. Comput."},{"key":"9487_CR29","first-page":"1","volume":"99","author":"PC Roy","year":"2018","unstructured":"P.C. Roy, K. Deb, M.M. Islam, An efficient nondominated sorting algorithm for large number of fronts. IEEE Trans. Cybern. 99, 1\u201311 (2018)","journal-title":"IEEE Trans. Cybern."},{"issue":"12","key":"9487_CR30","doi-asserted-by":"publisher","first-page":"6154","DOI":"10.1109\/TCYB.2020.2968301","volume":"51","author":"J Moreno","year":"2020","unstructured":"J. Moreno, D. Rodriguez, A.J. Nebro, J.A. Lozano, Merge nondominated sorting algorithm for many-objective optimization. IEEE Trans. Cybern. 51(12), 6154\u20136164 (2020)","journal-title":"IEEE Trans. Cybern."},{"issue":"4","key":"9487_CR31","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1145\/321906.321910","volume":"22","author":"H-T Kung","year":"1975","unstructured":"H.-T. Kung, F. Luccio, F.P. Preparata, On finding the maxima of a set of vectors. J. ACM 22(4), 469\u2013476 (1975)","journal-title":"J. ACM"},{"issue":"5","key":"9487_CR32","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1109\/TEVC.2003.817234","volume":"7","author":"MT Jensen","year":"2003","unstructured":"M.T. Jensen, Reducing the run-time complexity of multiobjective EAs: the NSGA-II and other algorithms. IEEE Trans. Evolut. Comput. 7(5), 503\u2013515 (2003)","journal-title":"IEEE Trans. Evolut. Comput."},{"key":"9487_CR33","unstructured":"F.-A. Fortin, S. Greiner, M. Parizeau, Generalizing the improved run-time complexity algorithm for non-dominated sorting, in Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u20192013) (ACM Press, New York, 2013), pp. 615\u2013622. ISBN: 978-1-4503-1963-8"},{"key":"9487_CR34","doi-asserted-by":"crossref","unstructured":"M. Buzdalov, A. Shalyto, A provably asymptotically fast version of the generalized Jensen algorithm for non-dominated sorting, in International Conference on Parallel Problem Solving from Nature\u2014PPSN XIII (Springer, Ljubljana, 2014), pp. 528\u2013537","DOI":"10.1007\/978-3-319-10762-2_52"},{"key":"9487_CR35","doi-asserted-by":"crossref","unstructured":"M. Buzdalov, Make evolutionary multiobjective algorithms scale better with advanced data structures: Van Emde Boas tree for non-dominated sorting, in International Conference on Evolutionary Multi-Criterion Optimization (EMO\u20192019) (Springer, East Lansing, 2019), pp. 66\u201377. ISBN: 978-3-030-12597-4","DOI":"10.1007\/978-3-030-12598-1_6"},{"issue":"1","key":"9487_CR36","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P Emde Boas","year":"1976","unstructured":"P. Emde Boas, R. Kaas, E. Zijlstra, Design and implementation of an efficient priority queue. Math. Syst. Theory 10(1), 99\u2013127 (1976)","journal-title":"Math. Syst. Theory"},{"key":"9487_CR37","doi-asserted-by":"crossref","unstructured":"P. Emde\u00a0Boas, Preserving order in a forest in less than logarithmic time, in Annual Symposium on Foundations of Computer Science (SFCS\u20191975) (IEEE, 1975), pp. 75\u201384","DOI":"10.1109\/SFCS.1975.26"},{"issue":"3","key":"9487_CR38","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1162\/evco.2008.16.3.355","volume":"16","author":"H Fang","year":"2008","unstructured":"H. Fang, Q. Wang, Y.-C. Tu, M.F. Horstemeyer, An efficient non-dominated sorting method for evolutionary algorithms. Evolut. Comput. 16(3), 355\u2013384 (2008)","journal-title":"Evolut. Comput."},{"key":"9487_CR39","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2019.100580","volume":"51","author":"S Mishra","year":"2019","unstructured":"S. Mishra, S. Saha, S. Mondal, C.A. Coello Coello, Divide-and-conquer based non-dominated sorting with reduced comparisons. Swarm Evolut. Comput. 51, 100580 (2019)","journal-title":"Swarm Evolut. Comput."},{"key":"9487_CR40","doi-asserted-by":"crossref","unstructured":"S. Mishra, M. Buzdalov, If unsure, shuffle: deductive sort is $$\\Theta (MN^3)$$, but $${\\cal{O}}(MN^2)$$ in expectation over input permutations, in Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u20192020) (2020), pp. 516\u2013523","DOI":"10.1145\/3377930.3390246"},{"key":"9487_CR41","doi-asserted-by":"crossref","unstructured":"S. Mishra, V. Prakash, Time complexity analysis of the deductive sort in the best case, in Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO\u20192021) (2021), pp. 337\u2013338","DOI":"10.1145\/3449726.3459416"},{"key":"9487_CR42","doi-asserted-by":"crossref","unstructured":"S. Mishra, M. Buzdalov, R. Senwar, Time complexity analysis of the dominance degree approach for non-dominated sorting, in Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO\u20192020) (2020), pp. 169\u2013170","DOI":"10.1145\/3377929.3389900"},{"key":"9487_CR43","doi-asserted-by":"crossref","unstructured":"J. Wang, C. Li, Y. Diao, S. Zeng, H. Wang, An efficient nondominated sorting algorithm, in Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u20192018) (ACM, 2018), pp. 203\u2013204","DOI":"10.1145\/3205651.3205663"},{"key":"9487_CR44","doi-asserted-by":"crossref","unstructured":"S. Mishra, M. Buzdalov, Filter sort is $$\\Omega (N^3)$$ in the worst case, in International Conference on Parallel Problem Solving from Nature\u2014PPSN XVI (Springer, 2020), pp. 675\u2013685","DOI":"10.1007\/978-3-030-58115-2_47"},{"key":"9487_CR45","doi-asserted-by":"crossref","unstructured":"V. Prakash, S. Mishra, C.A. Coello\u00a0Coello, On the computational complexity of efficient non-dominated sort using binary search, in International Conference on Evolutionary Multi-Criterion Optimization (EMO\u20192023) (Springer, 2023), pp. 419\u2013432","DOI":"10.1007\/978-3-031-27250-9_30"},{"issue":"1","key":"9487_CR46","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1109\/TCYB.2013.2247594","volume":"44","author":"H Wang","year":"2014","unstructured":"H. Wang, X. Yao, Corner sort for Pareto-based many-objective optimization. IEEE Trans. Cybern. 44(1), 92\u2013102 (2014)","journal-title":"IEEE Trans. Cybern."},{"key":"9487_CR47","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/j.swevo.2017.08.003","volume":"38","author":"RF Alexandre","year":"2018","unstructured":"R.F. Alexandre, C.H.N.D.R. Barbosa, J.A.D. Vasconcelos, LONSA: a labeling-oriented non-dominated sorting algorithm for evolutionary many-objective optimization. Swarm Evolut. Comput. 38, 275\u2013286 (2018)","journal-title":"Swarm Evolut. Comput."}],"container-title":["Genetic Programming and Evolvable Machines"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10710-024-09487-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10710-024-09487-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10710-024-09487-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,25]],"date-time":"2024-05-25T08:20:19Z","timestamp":1716625219000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10710-024-09487-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,16]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["9487"],"URL":"https:\/\/doi.org\/10.1007\/s10710-024-09487-1","relation":{},"ISSN":["1389-2576","1573-7632"],"issn-type":[{"value":"1389-2576","type":"print"},{"value":"1573-7632","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,16]]},"assertion":[{"value":"17 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 March 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare through the submission of this document that they have no conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}],"article-number":"14"}}