Information Technology has enabled new levels of convenience to our daily life. While providing people with astonishingly good experiences, computer science has still a long way to meet the needs from the users for various scenarios. As a good example, path selection problem is an important and common problem which finds applications in location based services, internet routing and navigation systems. Choosing the most cost effective and time saving routines plays an essential role in both theory and engineering. Although a plethora of classical solutions have been made to the static shortest path problem, dynamic shortest path problem has not been thoroughly studied. To address this critical issue, this paper investigates the dynamic shortest path problem by optimizing existing work and conducting extensive experiments. The studies fall into three main variants of the problem: unweighted shortest paths, weighted shortest paths, and shortest paths on the map. We present a comprehensive comparison of our optimizations and existing solutions which demonstrates the effectiveness and efficiency of our algorithms.

No abstract uploaded!

In 1976, Thurston proved that taut foliations on closed hyperbolic 3-manifolds have Euler class of norm at most 1, and conjectured that conversely, any integral second cohomology class with norm equal to one is the Euler class of a taut foliation. This is the first from a series of two papers that together give a negative answer to Thurston’s conjecture. Here counter-examples have been constructed conditional on the fully marked surface theorem. In the second paper, joint with David Gabai, a proof of the fully marked surface theorem is given.

No abstract uploaded!

No abstract uploaded!