搜索结果：Floyd

This research investigates the efficiency of Floyd algorithm for obstacle-free path planning for autonomous aerial vehicles (UAVs) or drones. Floyd algorithm is used to generate the shortest paths for UAVs to fly from any place to the destination in a large-scale field with obstacles which UAVs cannot fly over. The simulation results demonstrated that Floyd algorithm effectively plans the shortest obstacle-free paths for UAVs to fly to a destination. It is verified that Floyd algorithm holds a time complexity of O(n3). This research revealed a correlation of a cubic polynomial relationship between the time cost and the size of the field, no correlation between the time cost and the number of obstacles, and no correlation between the time cost and the number of UAVs in the tested field. The applications of the research results are discussed in the paper as well.

We study minimal idempotents $J^{\mathrm{min}}(X)$ in the Ellis semigroup $E(X)$ associated with a Floyd-Auslander system $(X,T)$. We show that $(X,T)$ is non-tame if and only if $|J^{\mathrm{min}}(X)| > 2^{\aleph_0}$, which happens exactly when the factor map onto the maximal equicontinuous factor possesses uncountably many non-invertible fibres. This yields an easy-to-check criterion for distinguishing tame from non-tame Floyd-Auslander systems and, more importantly, provides an entire family of regular almost automorphic systems with $|J^{\mathrm{min}}(X)| > 2^{\aleph_0}$. Notably, all previously known regular almost automorphic non-tame systems exhibited only a small (i.e. $\leq 2^{\aleph_0}$) set of minimal idempotents. We obtain our result by leveraging an alternative characterisation of (non)-tameness through, what we call, choice domains.

The celebrated Floyd-Warshall algorithm efficiently computes the all-pairs shortest path, and its simplicity made it a staple in computer science classes. Frequently, students discover a variant of this Floyd-Warshall algorithm by mixing up the loop order, ending up with the incorrect APSP matrix. This paper considers a computational problem of computing this incorrect APSP matrix. We will propose efficient algorithms for this problem and prove that this incorrect variant is APSP-complete.

Suppose $G$ is a finitely generated infinite group, and $\mathcal G$ is a graph of groups decomposition of $G$ such that the edge groups are finite. This paper establishes that the topology of the Floyd boundary of $G$ is uniquely determined by the topology of the Floyd boundary of each vertex group of $\mathcal G$.

We formulate and prove a Conner-Floyd isomorphism for the algebraic K-theory of arbitrary qcqs derived schemes. To that end, we study a stable $\infty$-category of non-$\mathbb A^1$-invariant motivic spectra, which turns out to be equivalent to the $\infty$-category of fundamental motivic spectra satisfying elementary blowup excision, previously introduced by the first and third authors. We prove that this $\infty$-category satisfies $\mathbb P^1$-homotopy invariance and weighted $\mathbb A^1$-homotopy invariance, which we use in place of $\mathbb A^1$-homotopy invariance to obtain analogues of several key results from $\mathbb A^1$-homotopy theory. These allow us in particular to define a universal oriented motivic $\mathbb E_\infty$-ring spectrum $\mathrm{MGL}$. We then prove that the algebraic K-theory of a qcqs derived scheme $X$ can be recovered from its $\mathrm{MGL}$-cohomology via a Conner-Floyd isomorphism \[\mathrm{MGL}^{**}(X)\otimes_{\mathrm L}\mathbb Z[β^{\pm 1}]\simeq \mathrm K^{**}(X),\] where $\mathrm L$ is the Lazard ring and $\mathrm K^{p,q}(X)=\mathrm K_{2q-p}(X)$. Finally, we prove a Snaith theorem for the periodized version of $\mathrm{MGL}$.

The Floyd-Warshall algorithm is the most popular algorithm for determining the shortest paths between all pairs in a graph. It is very a simple and an elegant algorithm. However, if the graph does not contain any negative weighted edge, using Dijkstra's shortest path algorithm for every vertex as a source vertex to produce all pairs shortest paths of the graph works much better than the Floyd-Warshall algorithm for sparse graphs. Also, for the graphs with negative weighted edges, with no negative cycle, Johnson's algorithm still performs significantly better than the Floyd-Warshall algorithm for sparse graphs. Johnson's algorithm transforms the graph into a non-negative one by using the Bellman-Ford algorithm, then, applies the Dijkstra's algorithm. Thus, in general the Floyd-Warshall algorithm becomes very inefficient especially for sparse graphs. In this paper, we show a simple improvement on the Floyd-Warshall algorithm that will increases its performance especially for the sparse graphs, so it can be used instead of more complicated alternatives.

The paper consists of two parts. In the first one we show that a relatively hyperbolic group $G$ splits as a star graph of groups whose central vertex group is finitely generated and the other vertex groups are maximal parabolic subgroups. As a corollary we obtain that every group which admits 3-discontinuous and 2-cocompact action by homeomorphisms on a compactum is finitely generated with respect to a system of parabolic subgroups. The second part essentially uses the methods of topological entourages developed in the first part. Using also Floyd metrics we obtain finer properties of finitely generated relatively hyperbolic groups. We show that there is a system of "tight" curves satisfying the property of horospherical quasiconvexity. We then prove that the Floyd quasigeodesics are tight and so the parabolic subgroups of $G$ are quasiconvex with respect to the Floyd metrics. As a corollary we obtain that the preimage of a parabolic point by the Floyd map is the Floyd boundary of its stabilizer.

We introduce the notion of controlled Floyd separation between geodesic rays starting at the identity in a finitely generated group G. Two such geodesic rays are said to be Floyd separated with respect to quasigeodesics if the (Floyd) length of c-quasigeodesics (for fixed but arbitrary c) joining points on the geodesic rays is asymptotically bounded away from zero. This is always satisfied by Morse geodesics. The main purpose of this paper is to furnish an example of a finitely generated group $G$ such that 1) all finitely presented subgroups of G are hyperbolic, 2) G has an uncountable family of geodesic rays that are Floyd separated with respect to quasigeodesics, 3) G is not hyperbolic relative to any collection of proper subgroups. 4) G is a direct limit of hyperbolic CAT(0) cubulated groups. 5) G has trivial Floyd boundary in the usual sense. On the way towards constructing $G$, we construct a malnormal infinitely generated (and hence non-quasiconvex) subgroup of a free group, giving negative evidence towards a question of Swarup and Gitik.

We show that for a uniformly irreducible random walk on a graph, with bounded range, there is a Floyd function for which the random walk converges to its corresponding Floyd boundary. Moreover if we add the assumptions, $p^{(n)}(v,w)\leq C ρ^n$, where $ρ< 1$ is the spectral radius, then for any Floyd function $f$ that satisfies $\sum_{n=1}^{\infty}nf(n)<\infty$, the Dirichlet problem with respect to the Floyd boundary is solvable.

The murder of George Floyd by police in May 2020 sparked international protests and renewed attention in the Black Lives Matter movement. Here, we characterize ways in which the online activity following George Floyd's death was unparalleled in its volume and intensity, including setting records for activity on Twitter, prompting the saddest day in the platform's history, and causing George Floyd's name to appear among the ten most frequently used phrases in a day, where he is the only individual to have ever received that level of attention who was not known to the public earlier that same week. Further, we find this attention extended beyond George Floyd and that more Black victims of fatal police violence received attention following his death than during other past moments in Black Lives Matter's history. We place that attention within the context of prior online racial justice activism by showing how the names of Black victims of police violence have been lifted and memorialized over the last 12 years on Twitter. Our results suggest that the 2020 wave of attention to the Black Lives Matter movement centered past instances of police violence in an unprecedented way, demonstrati

Classical Floyd-Warshall algorithm is used to solve all-pairs shortest path problem on a directed graph. The classical algorithm runs in \mathcal{O} (V^{3}) time where V represents the number of nodes. Here we have modified the algorithm and proposed a quantum algorithm analogous to Floyd-Warshall algorithm which exploits the superposition principle and runs in \mathcal{O} (Vlog_{2}V) time.

The Floyd--Warshall algorithm is a well-known algorithm for the all-pairs shortest path problem that is simply implemented by triply nested loops. In this study, we show that the incorrect implementations of the Floyd--Warshall algorithm that misorder the triply nested loops give correct solutions if these are repeated three times.

We clarify the exposition of Phases 2 and 3a in "The Floyd-Warshall Algorithm, the AP and the TSP". We also improve and simplify theorem 3.6 . In line with clarifying the exposition, we change the matrices in examples 3.4 and 3.5 of "The Floyd-Warshall Algorithm, the AP and the TSP II".

We prove that thick groups (and more generally thick graphs) have trivial Floyd boundary. This shows a wide class of finitely generated groups that are non-relatively hyperbolic have trivial Floyd boundary. In addition to giving new examples, our result provides a common proof and framework for many of the known results in the literature.

For finitely supported random walks on finitely generated groups $G$ we prove that the identity map on $G$ extends to a continuous equivariant surjection from the Martin boundary to the Floyd boundary, with preimages of conical points being singletons. This yields new results for relatively hyperbolic groups. Our key estimate relates the Green and Floyd metrics, generalizing results of Ancona for random walks on hyperbolic groups and of Karlsson for quasigeodesics. We then apply these techniques to obtain some results concerning the harmonic measure on the limit sets of geometrically finite isometry groups of Gromov hyperbolic spaces. .

We prove that there is an action of the cyclic group $\mathbf{C}_2$ on the $10$-dimensional Floyd manifold which turns it into a conjugation manifold. The submanifold of fixed points is the $5$-dimensional Floyd manifold, whose cohomology is isomorphic to that of the large one, scaled down by dividing the cohomological degree by a factor two.

A continuous equivariant map from the Floyd boundary of a relatively hyperbolic group (RHG for short) to its Bowditch boundary is constructed. Such a map is unique unless the group is two-ended. In order to optimize the proof and the usage of the map theorem we propose two new definitions of relative hyperbolicity equivalent to the other known definitions. In our approach some "visibility" conditions in graphs are essential. We introduce a class of "visibility actions" that contains the class of relatively hyperbolic actions. The convergence property still holds for the visibility actions. We describe and make use a rather general construction of "attractor sum" of two actions of a locally compact group.

We improve proofs in "The Floyd-Warshall Algorithm, the AP and the TSP (III). We also simplify the method for obtaining a good upper bound for an optimal solution.