Página 16 dos resultados de 14568 itens digitais encontrados em 0.016 segundos

Finding Heavy Paths in Graphs: A Rank Join Approach

Khabbaz, Mohammad; Bhagat, Smriti; Lakshmanan, Laks V. S.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.52%
Graphs have been commonly used to model many applications. A natural problem which abstracts applications such as itinerary planning, playlist recommendation, and flow analysis in information networks is that of finding the heaviest path(s) in a graph. More precisely, we can model these applications as a graph with non-negative edge weights, along with a monotone function such as sum, which aggregates edge weights into a path weight, capturing some notion of quality. We are then interested in finding the top-k heaviest simple paths, i.e., the $k$ simple (cycle-free) paths with the greatest weight, whose length equals a given parameter $\ell$. We call this the \emph{Heavy Path Problem} (HPP). It is easy to show that the problem is NP-Hard. In this work, we develop a practical approach to solve the Heavy Path problem by leveraging a strong connection with the well-known Rank Join paradigm. We first present an algorithm by adapting the Rank Join algorithm. We identify its limitations and develop a new exact algorithm called HeavyPath and a scalable heuristic algorithm. We conduct a comprehensive set of experiments on three real data sets and show that HeavyPath outperforms the baseline algorithms significantly, with respect to both $\ell$ and $k$. Further...

Integration of time-varying cocyclic one-forms against rough paths

Lyons, Terry J.; Yang, Danyu
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.52%
We introduce the cocyclic one-forms on a group, recast the integration in the theory of rough paths as a special example of the integration of a time-varying cocyclic one-form against a group-valued path, and give back, for example, the extension theorem and the integral developed by Lyons and Gubinelli. We introduce a family of Banach-space valued paths which can be represented as the integrals of a cocyclic one-form against a given group-valued path, and demonstrate that this family of paths is stable under basic operations.

Pairs of Noncrossing Free Dyck Paths and Noncrossing Partitions

Chen, William Y. C.; Pang, Sabrina X. M.; Qu, Ellen X. Y.; Stanley, Richard P.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.52%
Using the bijection between partitions and vacillating tableaux, we establish a correspondence between pairs of noncrossing free Dyck paths of length $2n$ and noncrossing partitions of $[2n+1]$ with $n+1$ blocks. In terms of the number of up steps at odd positions, we find a characterization of Dyck paths constructed from pairs of noncrossing free Dyck paths by using the Labelle merging algorithm.; Comment: 9 pages, 5 figures, revised version, to appear in Discrete Mathematics

On Relative Stabilities of Distinct Polyenes. An Extension of the Concept of Conjugated Paths

Gineityte, Viktorija
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 20/01/2015
Relevância na Pesquisa
26.52%
The study continues the previous development [MATCH, 72 (2014) 39-73] of the perturbative approach to relative stabilities of pi-electron systems of conjugated hydrocarbons modeled as sets of weakly-interacting initially-double (C=C) bonds. Distinct isomers of acyclic hydrocarbons (polyenes) are now under focus. The relevant total pi-electron energies (E) are expressed in the form of power series containing members (E_(k)) of even orders (k=0,2,4,...) with respect to the averaged resonance parameter of initially-single (C-C) bonds. Terms to within the sixth order (k=6) inclusive are shown to be of importance for discrimination between similar isomers. In this connection, missing expressions for corrections E_(6) are originally derived. Conjugated paths of various lengths (i.e. linear chains consisting of C=C and C-C bonds alternately) are shown to be the most important (but not the only) fragments contributing to stabilization of any acyclic pi-electron system. Again, new types of fragments (substructures) are revealed (viz. the so-called composite conjugated paths) that contribute to destabilization of the system concerned. As a result, formation of the total energy of an acyclic pi-electron system is concluded to be governed by an interplay between stabilizing and destabilizing factors. Accordingly...

Online Dual Edge Coloring of Paths and Trees

Favrholdt, Lene M.; Mikkelsen, Jesper W.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.52%
We study a dual version of online edge coloring, where the goal is to color as many edges as possible using only a given number, $k$, of available colors. All of our results are with regard to competitive analysis. For paths, we consider $k=2$, and for trees, we consider any $k \geq 2$. We prove that a natural greedy algorithm called First-Fit is optimal among deterministic algorithms on paths as well as trees. This is the first time that an optimal algorithm for online dual edge coloring has been identified for a class of graphs. For paths, we give a randomized algorithm, which is optimal and better than the best possible deterministic algorithm. Again, it is the first time that this has been done for a class of graphs. For trees, we also show that even randomized algorithms cannot be much better than First-Fit.; Comment: WAOA 2014

Menger's Paths with Minimum Mergings

Han, Guangyue
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.52%
For an acyclic directed graph with multiple sources and multiple sinks, we prove that one can choose the Merger's paths between the sources and the sinks such that the number of mergings between these paths is upper bounded by a constant depending only on the min-cuts between the sources and the sinks, regardless of the size and topology of the graph. We also give bounds on the minimum number of mergings between these paths, and discuss how it depends on the min-cuts.; Comment: 28 pages, 7 figures

On the rough-paths approach to non-commutative stochastic calculus

Deya, Aurélien; René, Schott
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 26/01/2013
Relevância na Pesquisa
26.52%
We study different possibilities to apply the principles of rough paths theory in a non-commutative probability setting. First, we extend previous results obtained by Capitaine, Donati-Martin and Victoir in Lyons' original formulation of rough paths theory. Then we settle the bases of an alternative non-commutative integration procedure, in the spirit of Gubinelli's controlled paths theory, and which allows us to revisit the constructions of Biane and Speicher in the free Brownian case. New approximation results are also derived from the strategy.; Comment: arXiv admin note: text overlap with arXiv:1110.2703 by other authors

Arithmetic area for m planar Brownian paths

Desbois, Jean; Ouvry, Stephane
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 04/02/2012
Relevância na Pesquisa
26.52%
We pursue the analysis made in [1] on the arithmetic area enclosed by m closed Brownian paths. We pay a particular attention to the random variable S{n1,n2, ...,n} (m) which is the arithmetic area of the set of points, also called winding sectors, enclosed n1 times by path 1, n2 times by path 2, ...,nm times by path m. Various results are obtained in the asymptotic limit m->infinity. A key observation is that, since the paths are independent, one can use in the m paths case the SLE information, valid in the 1-path case, on the 0-winding sectors arithmetic area.; Comment: 12 pages, 2 figures

Edge-intersection graphs of grid paths: the bend-number

Heldt, Daniel; Knauer, Kolja; Ueckerdt, Torsten
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.52%
We investigate edge-intersection graphs of paths in the plane grid, regarding a parameter called the bend-number. I.e., every vertex is represented by a grid path and two vertices are adjacent if and only if the two grid paths share at least one grid-edge. The bend-number is the minimum $k$ such that grid-paths with at most $k$ bends each suffice to represent a given graph. This parameter is related to the interval-number and the track-number of a graph. We show that for every $k$ there is a graph with bend-number $k$. Moreover we provide new upper and lower bounds of the bend-number of graphs in terms of degeneracy, treewidth, edge clique covers and the maximum degree. Furthermore we give bounds on the bend-number of $K_{m,n}$ and determine it exactly for some pairs of $m$ and $n$. Finally, we prove that recognizing single-bend graphs is NP-complete, providing the first such result in this field.; Comment: 33 pages, 20 figures

Untangling the SVD's of Random Matrix Sample Paths

Browne, D. W.; Browne, M. W.; Fitz, M. P.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 02/10/2006
Relevância na Pesquisa
26.52%
Singular Value Decomposition (SVD) is a powerful tool for multivariate analysis. However, independent computation of the SVD for each sample taken from a bandlimited matrix random process will result in singular value sample paths whose tangled evolution is not consistent with the structure of the underlying random process. The solution to this problem is developed as follows: (i) a SVD with relaxed identification conditions is proposed, (ii) an approach is formulated for computing the SVD's of two adjacent matrices in the sample path with the objective of maximizing the correlation between corresponding singular vectors of the two matrices, and (iii) an efficient algorithm is given for untangling the singular value sample paths. The algorithm gives a unique solution conditioned on the seed matrix's SVD. Its effectiveness is demonstrated on bandlimited Gaussian random-matrix sample paths. Results are shown to be consistent with those predicted by random-matrix theory. A primary application of the algorithm is in multiple-antenna radio systems. The benefit promised by using SVD untangling in these systems is that the fading rate of the channel's SVD factors is greatly reduced so that the performance of channel estimation, channel feedback and channel prediction can be increased.; Comment: 8 pages. Submitted to Forty-Fourth Annual Allerton Conference On Communication...

Non-Uniqueness of the Homotopy Class of Bounded Curvature Paths

Ayala, José; Rubinstein, Hyam
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 19/03/2014
Relevância na Pesquisa
26.52%
A bounded curvature path is a continuously differentiable piecewise $C^2$ path with bounded absolute curvature that connects two points in the tangent bundle of a surface. In this work we study the homotopy classes of bounded curvature paths for generic points in the tangent bundle of the Euclidean plane. In particular, we characterize the behavior of homotopies of such paths in terms of boundedness or unboundedness of their path length. Moreover, for a type of configuration of elements in the tangent bundle we prove the existence of a compact planar region in which no bounded curvature path lying on it can be made homotopic to a path outside of the region. In particular, we establish that for such type of configuration, the space of bounded curvature paths is divided into two disjoint components.; Comment: 23 pages, 12 figures

Global paths of time-periodic solutions of the Benjamin-Ono equation connecting pairs of traveling waves

Ambrose, David M.; Wilkening, Jon
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.52%
We classify all bifurcations from traveling waves to non-trivial time-periodic solutions of the Benjamin-Ono equation that are predicted by linearization. We use a spectrally accurate numerical continuation method to study several paths of non-trivial solutions beyond the realm of linear theory. These paths are found to either re-connect with a different traveling wave or to blow up. In the latter case, as the bifurcation parameter approaches a critical value, the amplitude of the initial condition grows without bound and the period approaches zero. We then prove a theorem that gives the mapping from one bifurcation to its counterpart on the other side of the path and exhibits exact formulas for the time-periodic solutions on this path. The Fourier coefficients of these solutions are power sums of a finite number of particle positions whose elementary symmetric functions execute simple orbits (circles or epicycles) in the unit disk of the complex plane. We also find examples of interior bifurcations from these paths of already non-trivial solutions, but we do not attempt to analyze their analytic structure.; Comment: 35 pages, 14 figures; changed title slightly, added 7 references, changed conjecture to a theorem and proved it, moved some material to appendices

Catalan paths, Quasi-symmetric functions and Super-Harmonic Spaces

Aval, Jean-Christophe; Bergeron, Nantel
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 20/09/2001
Relevância na Pesquisa
26.52%
We investigate the quotient ring $R$ of the ring of formal power series $\Q[[x_1,x_2,...]]$ over the closure of the ideal generated by non-constant quasi-\break symmetric functions. We show that a Hilbert basis of the quotient is naturally indexed by Catalan paths (infinite Dyck paths). We also give a filtration of ideals related to Catalan paths from $(0,0)$ and above the line $y=x-k$. We investigate as well the quotient ring $R_n$ of polynomial ring in $n$ variables over the ideal generated by non-constant quasi-symmetric polynomials. We show that the dimension of $R_n$ is bounded above by the $n$th Catalan number.; Comment: 14 pages

Efficiently listing bounded length st-paths

Rizzi, Romeo; Sacomoto, Gustavo; Sagot, Marie-France
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 25/11/2014
Relevância na Pesquisa
26.52%
The problem of listing the $K$ shortest simple (loopless) $st$-paths in a graph has been studied since the early 1960s. For a non-negatively weighted graph with $n$ vertices and $m$ edges, the most efficient solution is an $O(K(mn + n^2 \log n))$ algorithm for directed graphs by Yen and Lawler [Management Science, 1971 and 1972], and an $O(K(m+n \log n))$ algorithm for the undirected version by Katoh et al. [Networks, 1982], both using $O(Kn + m)$ space. In this work, we consider a different parameterization for this problem: instead of bounding the number of $st$-paths output, we bound their length. For the bounded length parameterization, we propose new non-trivial algorithms matching the time complexity of the classic algorithms but using only $O(m+n)$ space. Moreover, we provide a unified framework such that the solutions to both parameterizations -- the classic $K$-shortest and the new length-bounded paths -- can be seen as two different traversals of a same tree, a Dijkstra-like and a DFS-like traversal, respectively.; Comment: 12 pages, accepted to IWOCA 2014

Sampling diffusive transition paths

Miller III, Thomas F.; Predescu, Cristian
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.52%
We address the problem of sampling double-ended diffusive paths. The ensemble of paths is expressed using a symmetric version of the Onsager-Machlup formula, which only requires evaluation of the force field and which, upon direct time discretization, gives rise to a symmetric integrator that is accurate to second order. Efficiently sampling this ensemble requires avoiding the well-known stiffness problem associated with sampling infinitesimal Brownian increments of the path, as well as a different type of stiffness associated with sampling the coarse features of long paths. The fine-feature sampling stiffness is eliminated with the use of the fast sampling algorithm (FSA), and the coarse-feature sampling stiffness is avoided by introducing the sliding and sampling (S&S) algorithm. A key feature of the S&S algorithm is that it enables massively parallel computers to sample diffusive trajectories that are long in time. We use the algorithm to sample the transition path ensemble for the structural interconversion of the 38-atom Lennard-Jones cluster at low temperature.; Comment: 13 pages 5 figures

Electron paths and double-slit interference in the scanning gate microscopy

Kolasiński, K.; Szafran, B.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 06/03/2015
Relevância na Pesquisa
26.52%
We analyze electron paths in a solid-state double-slit interferometer based on the two-dimensional electron gas and their mapping by the scanning gate microscopy (SGM). A device with a quantum point source contact of a split exit and a drain contact used for electron detection is considered. We study the SGM maps of source-drain conductance ($G$) as functions of the probe position and find that for a narrow drain the classical electron paths are clearly resolved but without any trace of the double-slit interference. The latter is present in the SGM maps of backscattering ($R$) probability only. The double-slit interference is found in the $G$ maps for a wider drain contact but at the expense of the loss of information on the electron trajectories. Stability of $G$ and $R$ maps versus the geometry parameters of the scattering device is also discussed. We discuss the interplay of the Young interference and interference effects between various electron paths introduced by the tip and the electron detector.

Time Discrete Geodesic Paths in the Space of Images

Berkels, Benjamin; Effland, Alexander; Rumpf, Martin
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.52%
In this paper the space of images is considered as a Riemannian manifold using the metamorphosis approach, where the underlying Riemannian metric simultaneously measures the cost of image transport and intensity variation. A robust and effective variational time discretization of geodesics paths is proposed. This requires to minimize a discrete path energy consisting of a sum of consecutive image matching functionals over a set of image intensity maps and pairwise matching deformations. For square-integrable input images the existence of discrete, connecting geodesic paths defined as minimizers of this variational problem is shown. Furthermore, $\Gamma$-convergence of the underlying discrete path energy to the continuous path energy is proved. This includes a diffeomorphism property for the induced transport and the existence of a square-integrable weak material derivative in space and time. A spatial discretization via finite elements combined with an alternating descent scheme in the set of image intensity maps and the set of matching deformations is presented to approximate discrete geodesic paths numerically. Computational results underline the efficiency of the proposed approach and demonstrate important qualitative properties.; Comment: 27 pages...

Continuity of scalar-fields characterized by smooth paths fulfilling $\|\bs(t)\|\|\bs'(t)\| < +\infty$

Hafstein, Sigurdur F.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/02/2013
Relevância na Pesquisa
26.52%
A function $f$ from a subset of $\R^n$ to $\R$ is continuous at the origin, if and only if $\lim_{t\to 0+} f(\bs(t))=f(\bnull)$ for all continuous paths $\bs$ with $\lim_{t\to 0+} \bs(t)=\bnull$. The continuity of $f$ can, however, be characterized by a much smaller class of paths. We show that the class of all paths fulfilling $\lim_{t\to 0+} \bs(t)=\bnull$, $\bs\in [\cC^\infty(]0,a[)]^n$, and $\sup_{t\in\,]0,a[}\|\bs(t)\|\|\bs'(t)\| < +\infty$ is sufficient. Further, given any sequences $(\bx_k)_{k\in\N}$ and $(\by_k)_{k\in\N}$ in $\R^n\setminus\{\bnull\}$, such that $\lim_{k\to+\infty}\bx_k=\bnull$, $\bx_k\cdot\by_k \ge 0$, and $\|\by_k\|=1$ for all $k\in\N$, we show that there exist a path of this class, such that $\bs(\|\bx_k\|)=\bx_k$ and $\bs'(\|\bx_k\|)=\by_k$ for an infinite number of $k\in\N$.; Comment: 7 pages

Elliptic enumeration of nonintersecting lattice paths

Schlosser, Michael
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.52%
We enumerate lattice paths in the planar integer lattice consisting of positively directed unit vertical and horizontal steps with respect to a specific elliptic weight function. The elliptic generating function of paths from a given starting point to a given end point evaluates to an elliptic generalization of the binomial coefficient. Convolution gives an identity equivalent to Frenkel and Turaev's 10-V-9 summation. This appears to be the first combinatorial proof of the latter, and at the same time of some important degenerate cases including Jackson's 8-phi-7 and Dougall's 7-F-6 summation. By considering nonintersecting lattice paths we are led to a multivariate extension of the 10-V-9 summation which turns out to be a special case of an identity originally conjectured by Warnaar, later proved by Rosengren. We conclude with discussing some future perspectives.; Comment: minor changes, 17 pages, to appear in JCTA

Riordan Paths and Derangements

Chen, William Y. C.; Deng, Eva Y. P.; Yang, Laura L. M.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/02/2006
Relevância na Pesquisa
26.52%
Riordan paths are Motzkin paths without horizontal steps on the x-axis. We establish a correspondence between Riordan paths and $(321,3\bar{1}42)$-avoiding derangements. We also present a combinatorial proof of a recurrence relation for the Riordan numbers in the spirit of the Foata-Zeilberger proof of a recurrence relation on the Schr\"oder numbers.; Comment: 9 pages, 2 figures