Explanipedia

Research on Hydrodynamics of Trans-Media Vehicles Considering Underwater Time-Varying Attitudes Open

Shuo Liu, Chihao Du, Yijie Han, Yu Zhang, Wanglin Lin , et al. · 2024

A trans-media vehicle is a new type of equipment that can adapt to two environments, water and air, to maintain optimal hydrodynamic and aerodynamic performance. However, no matter what kind of trans-media vehicle, its dynamics are much mo…

Constant Storage for Storing Shortest Paths for a Polyhedron Open

Jindong Chen, Sraawya Chintala, Yijie Han · 2024

We present a new scheme for storing shortest path information for a polyhedron. This scheme is obtained by applying the constant storage scheme of Han and Saxena [4] on the outward layout of Sharir and Schorr [8]. We achieve constant stora…

Point Location in Constant Time Open

Sairam Chaganti, Yijie Han · 2023

We preprocess the input subdivision with $n$ points on the plane in $O(n\sqrt{\log n})$ time to facilitate point location in constant time. Previously the preprocessing time is $O(n\log n)$ and point location takes $O(\log n)$ time.

The Proof of P=NP Open

Yijie Han · 2023

We show that the 3-satisfiability problem can be solved in polynomial time, thereby proving that P=NP. The result of this paper is derived based on my matrix multiplication paper titled “An $O(n^2\log^4 n \log \log n)$ Time Matrix Multipli…

The Proof of P=NP Open

Yijie Han · 2023

We show that the 3-satisfiability problem can be solved in polynomial time, thereby proving that P=NP. The result of this paper is derived based on my matrix multiplication paper titled "An $O(n^2\log^3 n\log \log n)$ Time Matrix Multiplic…

The Proof of P=NP Open

Yijie Han · 2023

We show that the 3-satisfiability problem can be solved in polynomial time, thereby proving that P=NP. The result of this paper is derived based on my matrix multiplication paper titled "An $O(n^4\log^4 n\log \log n)$ Time Matrix Multiplic…

Storage in Computational Geometry Open

Yijie Han, Sanjeev Saxena · 2023

We show that $n$ real numbers can be stored in a constant number of real numbers such that each original real number can be fetched in $O(\log n)$ time. Although our result has implications for many computational geometry problems, we show…

Sorting Real Numbers in Constant Time Using n^2/log^cn Processors Open

Yijie Han, Pruthvi Kasani, Sai Swathi Kunapuli · 2022

We study the sorting of real numbers into a linked list on the PRAM (Parallel Random-Access Machine) model. We show that n real numbers can be sorted into a linked list in constant time using n2 processors. Previously n numbers can be sort…

On Petrie cycle and Petrie tour partitions of 3- and 4-regular plane graphs Open

Xin He, Huaming Zhang, Yijie Han · 2022

Given a plane graph $G=(V,E)$ , a Petrie tour of G is a tour P of G that alternately turns left and right at each step. A Petrie tour partition of G is a collection ${\mathscr P}=\{P_1,\ldots,P_q\}$ of Petrie tours so that each edge of G i…

Parallel Merging and Sorting on Linked List Open

Yijie Han, Sreevalli Tata · 2021

We study linked list sorting and merging on the PRAM model. In this paper we show that n real numbers can be sorted into a linked list in constant time with n2+e processors or in ) time with n2 processors. We also show that two sorted link…

An O(nlogn/logw) Time Algorithm for Ridesharing Open

Yijie Han, Chen Sun · 2021

In the ridesharing problem different people share private vehicles because they have similar itineraries. The objective of solving the ridesharing problem is to minimize the number of drivers needed to carry all load to the destination. Th…

An O(nlogn/logw) Time Algorithm for Ridesharing Open

Yijie Han, Chen Sun · 2021

In the ridesharing problem different people share private vehicles because they have similar itineraries. The objective of solving the ridesharing problem is to minimize the number of drivers needed to carry all load to the destination. Th…

Uniform Linked Lists Contraction Open

Yijie Han · 2020

We present a parallel algorithm (EREW PRAM algorithm) for linked lists contraction. We show that when we contract a linked list from size $n$ to size $n/c$ for a suitable constant $c$ we can pack the linked list into an array of size $n/d$…

Sort Integers into a Linked List Open

Yijie Han, Hemasree Koganti, Nikita Goyal · 2020

We show that n integers in {0, 1, …, m-1} can be sorted into a linked list in constant time using nlogm processors on the Priority CRCW PRAM model, and they can be sorted into a linked list in O(loglogm/logt) time using nt processor…

Correction to: Sorting Real Numbers in $$O(n\sqrt{\log n})$$ Time and Linear Space Open

Yijie Han · 2019

An NC Algorithm for Sorting Real Numbers in O(nlogn/√loglogn) Operations Open

Yijie Han, Sneha Mishra, Md Usman Gani Syed · 2019

We apply the recent important results of serial sorting of real numbers in O(n√logn) time to the design of a parallel algorithm for sorting real numbers in O(log1+n) time and O(nlogn/√loglogn) operations. This is the first NC algorithm kn…

An NC Algorithm for Sorting Real Numbers in <em>O</em>(nlogn/√<span style="margin-left:-4px;margin-right:2px;border-top:2px solid black">loglogn</span>) Operations Open

Yijie Han, Sneha Mishra, Md Usman Gani Syed · 2019

We apply the recent important result of serial sorting of n real numbers in time to the design of a parallel algorithm for sorting real numbers in time and operations. This is the first NC algorithm known to take operations for sorting rea…

Sorting Real Numbers in $O(n\sqrt{\log n})$ Time and Linear Space Open

Yijie Han · 2017

We present an $O(n\sqrt{\log n})$ time and linear space algorithm for sorting real numbers. This breaks the long time illusion that real numbers have to be sorted by comparison sorting and take $Ω(n\log n)$ time to be sorted.

An $O(n^2\log^4 n \log \log n)$ Time Matrix Multiplication Algorithm Open

Yijie Han · 2016

We show, for the input vectors $(a_0, a_1, ..., a_{n-1})$ and $(b_0, b_1, ..., b_{n-1})$, where $a_i$'s and $b_j$'s are real numbers, after $O(n\log^4 n)$ time preprocessing for each of them, the vector multiplication $(a_0, a_1, ..., a_{n…

An Õ$(n^2)$ Time Matrix Multiplication Algorithm Open

Yijie Han · 2016

We show, for the input vectors $(a_0, a_1, ..., a_{n-1})$ and $(b_0, b_1, ..., b_{n-1})$, where $a_i$'s and $b_j$'s are real numbers, after O$(n)$ time preprocessing for each of them, the vector multiplication $(a_0, a_1, ..., a_{n-1})(b_0…

An $n^2(\log \log n)^{O((\log \log n)^2)}$ Time Matrix Multiplication Algorithm Open

Yijie Han · 2016

We show, for the input vectors $(a_0, a_1, ..., a_{n-1})$ and $(b_0, b_1, ..., b_{n-1})$, where $a_i$'s and $b_j$'s are real numbers, after O$(n)$ time preprocessing for each of them, the vector multiplication $(a_0, a_1, ..., a_{n-1})(b_0…

A $\theta(n^2)$ Time Matrix Multiplication Algorithm Open

Yijie Han · 2016

Yijie Han YOU? Author Swipe