Journal Publications:

  1. Y. Han. The proof of P=NP. https://www.techrxiv.org/articles/preprint/The_Proof_of_P_NP/22790897/2

    or

    https://doi.org/10.36227/techrxiv.22790897.v2


  2. Y. Han. An O(n2log4nloglogn) time matrix multiplication algorithm. Paper 1612.04208 in arXiv.


  3. Y. Han, S. Saxena. Storage in computational geometry. Paper 2302.11821 in arXiv.org.


  4. Y. Han. Uniform linked list contraction. Paper 2002.05034 in arXiv.org.


  5. X. He, H. Zhang, Y. Han. On Petrie cycle and Petrie tour partitions of 3- and 4-regular plane graphs. Mathematical Structures in Computer Science, Cambridge University Press, 2022;32(2):240-256. doi:10.1017/S0960129522000238


  6. Y. Han, X. He. More efficient parallel integer sorting. International Journal of Foundations of Computer Science, Vol. 33, No. 05, 411-427(2022).


  7. S. Chaganti, Y. Han. Point location in constant time. Paper 2401.02440 in arXiv.org.


  8. Y. Han, T. Sreevalli. Parallel merging and sorting on linked list. Int. J. Computer and Information Technology (IJCIT), Vol 10, Issue 2, 92-95(March 2021), https://doi.org/10.24203/ijcit.v10i2.85.


  9. Y. Han, C. Sun. An O(nlog n/log w) time algorithm for ridesharing. Computer and Information Science, Vol 14, No. 1, 8-13(2021).


  10. Y. Han, N. Goyal, H. Koganti. Sort Integers into a Linked List. Computer and Information Science. Vol. 13, No.1, 51-57(2020).


  11. Y. Han, S. Mishra, M. U. G. Syed. An NC algorithm for sorting real numbers in O(nlog n/\sqrt{loglog n}) operations. Open Journal of Applied Sciences, 9, 403-408(2019).


  12. Y. Han. Sorting real numbers in O(nlog1/2n) time and linear space. Algorithmica 82, 966-978(2020).


  13. R. Tarafdar. Y. Han. Finding majority for integer elements. Journal of Computing Sciences in Colleges, 33, 5, 187-192(2018).


  14. Y. Han. S. Saxena. Algorithms for testing occurrences of length 4 patterns in permutations. Journal of Combinatorial Optimization , DOI 10.1007/s10878-017-0163-8, (2017).


  15. Y. Han. Construct a perfect word hash function in time independent of the size of integers. Information Processing Letters , 128, 5-10(2017).


  16. Y. Han, T. Takaoka. An O(n3 log log n/log2 n) time algorithm for all pairs shortest paths. Journal of Discrete Algorithms , Vol. 38-41, 9-19(2016)


  17. Y. Han. Tight bound for matching. Journal of Combinatorial Optimization , Vol. 23, Issue 3, 322-330(2012). (There is an error in the paper and an erratum is published to correct the error. The corrected maximum matching lower bound is m/k-m/(Lk) and this bound remains to be tight. The erratum is published as ``Erratum to: Tight bound for matching,'' Journal of Combinatorial Optimization, Vol. 26, Issue 2, 412-414(2013). )


  18. Y. Han, S. Saxena, X. Shen. An efficient parallel algorithm for building the separating tree. Journal of Parallel and Distributed Computing, Vol. 70, Issue 6, 625-629(2010).


  19. Y. Han. An O(n3(loglog n/log n)5/4) time algorithm for all pairs shortest paths. Algorithmica 51, 4, 428-434(August 2008).


  20. Y. Han. A note of an O(n3/log n) time algorithm for all pairs shortest paths. Information Processing Letters, 105, 114-116(2008).


  21. Y. Han. Optimal parallel selection. ACM Transactions on Algorithms, Article No. 38, Vol. 3, Issue 4, (November 2007).


  22. Y. Han. Improved algorithm for the symmetry number problem on trees. Information Processing Letters, 98(4), 130-132(2006).


  23. Y. Han. Improved algorithm for all pairs shortest paths. Information Processing Letters, 91, 245-250(2004).


  24. Y. Han. Deterministic sorting in O(nloglogn) time and linear space. Journal of Algorithms, 50, 96-105(2004).


  25. H. Shen, Y. Han, Y. Pan, D.J. Evans. Optimal parallel algorithms for multiselection on mesh-connected computers. International Journal of Computer Mathematics,Vol. 80(2), 165-179(2003).


  26. K. W. Chong, Y. Han, Y. Igarashi, T. W. Lam. Improving the efficiency of parallel minimum spanning tree algorithms. Discrete Applied Mathematics, Vol. 126, No. 1, 33-54(2003).


  27. Y. Han, X. Shen. Parallel integer sorting is more efficient than parallel comparison sorting on exclusive write PRAMs. SIAM Journal on Computing 31, 6, 1852-1878(2002).


  28. Y. Han, Y. Pan, H. Shen. Sublogarithmic deterministic selection on arrays with a reconfigurable optical bus. IEEE Transactions on Computers, Vol. 51, No. 6, 702-707(June 2002).


  29. Y. Han. Improved fast integer sorting in linear space. Information and Computation. Vol. 170, No. 1, 81-94(Oct. 2001).


  30. Y. Han, W. Liang, X. Shen. Very fast parallel algorithms for approximate edge coloring. Discrete Applied Mathematics 108, 227-238(2001).


  31. K. W. Chong, Y. Han, T. W. Lam. Concurrent threads and optimal parallel minimum spanning tree algorithm. Journal of ACM. Vol. 48. No. 2, 297-323(March 2001).


  32. Y. Han, Y. Igarashi. Fast PROFIT/COST algorithms through fast derandomization. Acta Informatica, Vol. 36, Facs. 3, 215-232(1999).


  33. Y. Han, V. Y. Pan, and J. H. Reif. Efficient parallel algorithms for computing all pair shortest paths in directed graphs. Algorithmica (1997) 17,399-415.


  34. J. Chen and Y. Han. Shortest paths on a polyhedron, Part I: Computing shortest paths. International Journal of Computational Geometry and Applications, Vol. 6, No. 2, pp. 127-144, June 1996.


  35. Y. Han. A fast derandomization scheme and its applications, SIAM Journal on Computing Vol. 25, No. 1, pp. 52-82, February 1996.


  36. Y. Han. An improvement on parallel computation of a maximal matching. Information Processing Letters 56, 343-348(1995).


  37. Y. Han, Y. Igarashi, K. Kanai and K. Miura. Broadcasting in faulty binary jumping networks. Journal of Parallel and Distributed Computing 23 , 462-467(1994).


  38. Y. Han, B. Narahari, H.-A. Choi. Mapping a chain task to chained processors. Information Processing Letters 44 (1992)141-148.


  39. Y. Han, Y. Igarashi, M. Truszczynski. Indexing functions and time lower bounds for sorting on a mesh-connected computer. Discrete Applied Mathematics, 36 141-152(1992).


  40. Y. Han. An optimal linked list prefix algorithm on a -local memory computer. IEEE Transactions on Computers, Vol. 40 , No. 10, 1149-1152(1991).


  41. Y. Han, R. A. Wagner. A fast and efficient parallel connected component algorithm. Journal of ACM Vol. 37 , No. 3, 626-642(July 1990).


  42. Y. Han, Y. Igarashi. Time lower bounds for parallel sorting on multi-dimensional mesh-connected processor arrays. Information Processing Letters, Vol. 33, No. 5, 10, 233-238(January 1990).


  43. Y. Han, Y. Igarashi. Time lower bounds for parallel sorting on a mesh-connected processor array. Acta Informatica , Vol. 26, Facs. 7, 643-656(1989).


  44. Y. Han. Parallel algorithms for computing linked list prefix. Journal of Parallel and Distributed Computing 6, 537-557(1989).


  45. L.D. Duval, R.A. Wagner, Y. Han, D.W. Loveland. Finding test-and-treatment procedures using parallel computation. Journal of Parallel and Distributed Computing 4, 309-318(1987).


Articles in Published Books:

  1. Y. Han. Parallel algorithms for maximal independent set and maximal matching. ``Handbook of Parallel Computing: Models, Algorithms and Applications''; , Chapter 25, (edited by S. Rajasekaran and J. Reif), Chapman \& Hall/CRC, 2008.


  2. Y. Han. Parallel derandomization techniques. ``Advances in Parallel Algorithms'', (edited by L. Kronsjo and D. Shumsheruddin), Blackwell Scientific Publications, 368-388, 1992.


Conference Publications:

  1. Y. Han, S. Kunapuli. Sorting real numbers into a linked list using n2/logc n processors, IAARHIES International Conference on IT & Computer Science, Edmonton-Canada, 21-22(May, 2022).


  2. Y. Han, P. Kasani. Time processor trade-off for sorting real numbers into a linked list. Proc. International Conference on Computation Structures and Algorithms. 40-44(2021).


  3. Y. Han, P. Kasani. Sorting real numbers into a linked list on the PRAM model. Proceedings of the 2021 Int. Conf. on Life Sciences, Engineering and Technology . 45-49(2021).


  4. Y. Han, C. Sun. An O(nlog n/log w) time algorithm for ridesharing. ISCA 29th Int. Conf. on Software Engineering and Data Engineering (SEDE'2020), vol 76, 49-55(2021). https://doi.org/10.29007/gl1k


  5. Y. Han, H. Koganti, N. Goyal. Sort integers into a linked list. Proc. 2019 Int. Conf. on Foundations of Computer Science (FCS'2019), 43-48(2019).


  6. Y. Han, M, Sneha, U. Syed. An NC algorithm for sorting real numbers in O((nlog n)/(\log \log n)1/2) operations. Proc. 34th Int. Conf. on Computers and Their Applications (CATA'2019), Vol. 58, 93-98(2019).


  7. Y. Han, H. Koganti. Searching in a Sorted Linked List. In Proceedings of the 17th Int. Conf. on Information Technology (ICIT'2018).


  8. R. Tarafdar, Y. Han. Finding majority for integer elements. In Central Plains 2018 Conference (2018 CCSC) , (2018).


  9. R. Tarafdar, Y. Han. Algorithms for the majority problem. Proc. 2017 Int. Conf. Foundations of Computer Science (FCS'2017), 32-37(2017).


  10. M. Chadalavada, Y. Han. Improving cuckoo hashing with perfect hashing. Proc. 2017 Int. Conf. Software Engineering Research and Practice (SERP'2017), 143-145(2017).


  11. Y. Han. S. Nakano. On r-gatherings on the Line. Proc. 2016 Int. Conf. on Foundations of Computer Science (FCS'2016), in WORLDCOMP'2016. 99-104(2016).


  12. A. Pimidi, Y. Han. An algorithm for counting the number of edge covers for graphs with intersecting cycles. Proc. Int. Conf. on Foundations of Computer Science (FCS'2016), in WORLDCOMP'2016, 9-15(2016).


  13. N. Sharma, Y. Han. Set intersection and document search algorithms using tries and graphs. Proc. Int. Conf. on Foundations of Computer Science (FCS'2016), in WORLDCOMP'2016, 16-22(2016).


  14. Y. Han. Construct a perfect hash function in time independent of the size of integers. Proc. 2015 Int. Conf. on Foundations of Computer Science (FCS'15), 86-89(2015).


  15. Y. Han. A linear time algorithm for ordered partition. Proc. 2015 International Frontiers in Algorithmics Workshop (FAW'15), LNCS 9130, 89-103(2015).


  16. O. Titti, Y. Han. Data structures and algorithms for partitioning a set into sets on non-descending cardinality. Proc. 2015 Int. Conf. on Foundations of Computer Science(FCS'15), 10-15(2015).


  17. Y. Han, S. Saxena. Parallel algorithms for testing length four permutations, Proc. 2014 IEEE Int. Symp. on Parallel Architectures, Algorithms and Programming (PAAP'2014) , 81-86(2014), wins the best paper award of the conference.


  18. Y. Han, S. Saxena. Algorithms for testing length four permutations. Proceedings 2013 International Frontiers in Algorithmic Workshop (FAW-AAIM'2013) LNCS 7924, 17-23(2013)


  19. Y. Han, T. Takaoka. An O(n3loglogn/log2n) time algorithm for all pairs shortest paths. Proceedings 2012 Scandinavian Symposium and Workshop on Algorithm Theory (SWAT'2012), LNCS 7357, 131-141(2012).


  20. Y. Han, X. He. More efficient parallel integer sorting. Proceedings 2012 Frontiers of Algorithmic Workshop (FAW-AAIM'2012), LNCS 7285, 279-290(2012).


  21. Y. Han. Tight bound for matching. Proceedings of 2009 International Conference on Foundations of Computer Science (FCS'2009), 68-74(2009).


  22. J. Lopes, Y. Han. Modified granular index scheme for XML database. Proceedings of 2009 International Conference Information and Knowledge Engineering (IKE'09), 200-203(2009).


  23. Y. Han. Matching for graphs of bounded degree. Proceedings of the Second International Workshop on Frontiers in Algorithmics (FAW'08), Lecture Notes in Computer Science 5059, 171-173(June 2008).


  24. S. Rokkam, Y. Han. Data warehousing: a functional overview. Proceedings 2008 International Conference on Data Mining (DMIN'08), Vol. II, 362-369. (July 2008).


  25. Y. Han. Maximum flow with a faster way of computing a blocking flow. Proceedings of the 2007 International Conference on Foundations on Computer Science, (FCS’07), 52-56(2007).


  26. N. Gopathi, Y. Han. Design of software systems using web services: an overview and extension. Proceedings of the 2007 International Conference on Software Engineering Research and Practice, (SERP’07), Vol. 1, 217-223(2007).


  27. M. F. Arif, H. Razzaq, Y. Han. Multi-agent teacher assistant, a case study intended for multi-agent applications. Proceedings of the 2007 International Conference on Software Engineering Research and Practice, (SERP’07), Vol. 2, 501-507(2007).


  28. Z. Li. Y. Han. Modeling organization structures in UML. Proceedings of the 2007 International Conference on Software Engineering Research and Practice, (SERP’07), Vol. 1, 177-180(2007).


  29. A. Bodapunti, Y. Han. TCP over satellite, its evolution and variants. Proceedings of the 2007 International Conference on Wireless Networks, (ICWN’07), 3-11(2007).


  30. H. Razzaq, M. F. Arif, Y. Han. Mobile agent peer discovery and information protocol, an advance peer discovery technique in P2P networks. Proceedings of the 2007 International Conference on Internet Computing (ICOMP’07), 234-238(2007).


  31. Y. Han. Computing lowest common ancestors in directed acyclic graphs. Proceedings 22nd International Conference on Computers and Their Applications, (CATA-2007), 36-37(2007).


  32. Y. Han. An O(n3(loglog n/log n)5/4) time algorithm for all pairs shortest paths. Proceedings 14th Annual European Symposium on Algorithms (ESA'06), Lecture Notes in Computer Science 4168. 411-417(2006).


  33. Y. Han. Improving the efficiency of sorting by reversals. Proceedings of the 2006 International Conference on Bioinformatics and Computational Biology (BIOCOMP'06), 406-409(2006).


  34. Y. Han. An efficient parallel algorithm for building the separating tree. Proceedings 2006 International Conference on Parallel and Distributed Techniques and Applications (PDPTA'06), 369-373(2006).


  35. Y. Han. Achieving O(n3/log n) time for all pairs shortest paths by using a smaller table. Proceedings 21st International Conference on Computers and Their Applications (CATA'2006), 36-37(2006).


  36. Y. Han. Improved algorithm for the symmetry number problem on trees. Proceedings 21st International Conference on Computers and Their Applications (CATA'2006), 38-40(2006).


  37. S.R. Mohan, E.K. Park, Y. Han. An adaptive intrusion detection system using a data mining approach. Computational Intelligence in Data Mining, Proceedings of a workshop held in conjunction with the Fifth IEEE International Conference on Data Mining. 71-77(2005).


  38. S.R. Mohan, E.K. Park, Y. Han. Data mining for adaptive web cache maintenance. Multiagent Data Warehousing (MADW) and Multiagent Data Mining (MADM), Proceedings of a Workshop held in Conjunction with 2005 IEEE International Conference on Data Mining. 36-43(2005).


  39. S.R. Mohan. E.K. Park, Y. Han. Association rule based data mining agents for personalized web caching. Proceedings The Twenty-Ninth Annual International Computer Software and Applications Conference (COMPSAC05).37-38(2005).


  40. S. Polusani, Y. Han, E.U. Park. A scalable architecture for web caching. Proceedings of the 8th World Multi-Conference on Systemics, Cybernetics and Informatics (SCI'2004), 185-190(July 2004).


  41. Y. Han. Optimal parallel selection. Proceedings 2003 ACM-SIAM Symposium on Discrete Algorithms (SODA'03), 1-9(2003).


  42. Y. Han, M. Thorup. Integer sorting in O(n(loglog n)1/2) expected time and linear space. Proceedings of the 43nd IEEE Symposium on Foundations of Computer (FOCS'02), 135-144(2002).


  43. Y. Han. Deterministic sorting in O(nloglog n) time and linear space. Proceedings 2002 ACM Symposium on Theory of Computing (STOC'02), 702-707(2002).


  44. Kyoosang Cho, Yijie Han, Yugyung Lee, and E. K. Park. Dynamic and hierarchical spatial access method using integer searching. Proceedings of the 2001 ACM International Conference on Information and Knowledge Management. 341-384(2001).


  45. Y. Han. Improved fast integer sorting in linear space. Proceedings 2001 ACM-SIAM Symposium on Discrete Algorithms (SODA'01), 793-796(Jan. 2001).


  46. Y. Han, Y. Lee. Parallel computation for managing transitive relations. Proceedings IASTED 2000 International Conference on Parallel and Distributed Systems, Vol. I, 37-43(Nov. 2000).


  47. Y. Han. Fast integer sorting in linear space. Proceedings 2000 Symposium on Theoretical Aspects of Computing (STACS'2000), Lecture Notes in Computer Science 1170, 242-253.


  48. K. W. Chong, Y. Han, Y. Igarashi, T. W. Lam. Improve parallel computation with fast integer sorting. Proceedings of the 5th International Conference on Computing and Combinatorics, Lecture Notes in Computer Sciecn 1627, 452-461(1999).


  49. Y. Han, Y. Pan, H. Shen. Fast parallel selection on the linear array with reconfigurable pipelined bus system. Proceedings of the IEEE Seventh Symposium on the Frontiers of Massively Parallel Computation (Frontiers'99), 286-293(1999).


  50. Y. Han, X. Shen. Parallel integer sorting is more efficient than parallel comparison sorting on exclusive write PRAMs. Proceedings 1999 Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), 419-428(January 1999).


  51. K. W. Chong, Y. Han, T. W. Lam. On the parallel time complexity of undirected connectivity and minimum spanning trees. Proceedings 1999 Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), 225-234(January 1999).


  52. Y. Han, W. Liang, X. Shen. Very fast parallel algorithms for approximate edge coloring. Proceedings 1998 10th IASTED International Conference on Parallel and Distributed Computing and Systems, 244-249(October 1998).


  53. Y. Han, X. Shen. Conservative algorithms for parallel and sequential integer sorting. Proceedings 1995 International Computing and Combinatorics Conference, Lecture Notes in Computer Science 959, 324-333(August, 1995).


  54. Y. Han, Y. Igarashi. Efficient parallel shortest path algorithms for banded matrices. Proceedings 1993 International Conference on Parallel Processing, Vol. 3, 223-226, (Aug. 1993).


  55. Y. Han, V.Y. Pan, J.H. Reif. Efficient parallel algorithms for computing all pair shortest paths in directed graphs. Proceedings 4th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'92), San Diego, California. 353-362(1992).


  56. Y. Han, Y. Igarashi, K. Kanai, K. Miura. Broadcasting in faulty binary jumping networks. Proceedings 3rd International Symposium on Algorithms and Computation (ISAAC'92) Nagoya, Japan, December 1992, Lecture Notes in Computer Science, Vol. 650, 145-154(1992).


  57. Y. Han. A parallel algorithm for the PROFIT/COST problem. Proceedings 1991 International Conference on Parallel Processing, Vol. 3, 103-112(August 1991).


  58. Y. Han. A fast derandomization scheme and its applications. Proceedings 2nd Workshop on Algorithms and Data Structures (WADS'91), Ottawa, Canada, Lecture Notes in Computer Science 519, 177-188(August, 1991).


  59. J. Chen and Y. Han. Storing shortest paths for a polyhedron. Proceedings 1991 International Conference on Computing and Information, Lecture Notes in Computer Science 497, 169-180(May 1991).


  60. J. Chen and Y. Han. Shortest paths on a polyhedron. Proceedings 6th Annual ACM Symposium on Computational Geometry. 360-369 (June 1990).


  61. Y. Han. Parallel algorithms for linked list and beyond. (invited paper). Proceedings SIGAL Symposium on Algorithms, Lecture Notes in Computer Science 450, 86-100(August 1990).


  62. Y. Han, Y. Igarashi. Derandomization by exploiting redundancy and mutual independence. Proceedings SIGAL Symposium on Algorithms, Tokyo, Japan, Lecture Notes in Computer Science 450, 328-337(August 1990).


  63. Y. Han. Matching partition a linked list and its optimization. Proc. 1989 ACM Symposium on Parallel Algorithms and Architectures (SPAA'89), 246-253(June 1989).


  64. Y. Han. An optimal linked list prefix algorithm on a local memory computer. Proceedings 1989 Computer Science Conference (CSC'89), 278-286(Feb., 1989).


  65. Y. Han, R. Finkel. An optimal scheme for disseminating information. Proceedings 1988 International Conference on Parallel Processing, Vol. 2, 198-203(August 1988).


  66. Y. Han, Y. Igarashi. Time lower bounds for parallel sorting on multi-dimensional mesh-connected processor arrays. Proceedings 1988 International Conference on Parallel Processing, Vol. 3., 194-197(August 1988).


  67. Y. Han, Y. Igarashi. Time lower bounds for parallel sorting on a mesh-connected processor array. Proceedings 3rd Aegean Workshop on Computing (AWOC'88), Lecture Notes in Computer Science 319, 434-443(June/July 1988).


  68. R.A. Wagner, Y. Han. Parallel algorithms for bucket sorting and the data dependent prefix problem. Proceedings 1986 International Conference on Parallel Processing, 924-930(August 1986).


  69. L. D. Duval, R. A. Wagner, Y. Han, D.W. Loveland. Finding test-and-treatment procedures using parallel computation. Proceedings 1986 International Conference on Parallel Processing, 688-690(August 1986).


  70. Y. Han. A family of parallel sorting algorithms. Proceedings 1985 International Conference on Parallel Processing, 851-853(August 1985).


     Ph.D. Thesis.