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

## Finding Heavy Paths in Graphs: A Rank Join Approach

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...

Link permanente para citações:

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

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.

Link permanente para citações:

## Pairs of Noncrossing Free Dyck Paths and Noncrossing Partitions

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

Link permanente para citações:

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

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...

Link permanente para citações:

## Online Dual Edge Coloring of Paths and Trees

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

Link permanente para citações:

## Menger's Paths with Minimum Mergings

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

Link permanente para citações:

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

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

Link permanente para citações:

## Arithmetic area for m planar Brownian paths

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

Link permanente para citações:

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

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

Link permanente para citações:

## Untangling the SVD's of Random Matrix Sample Paths

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...

Link permanente para citações:

## Non-Uniqueness of the Homotopy Class of Bounded Curvature Paths

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 19/03/2014

Relevância na Pesquisa

26.52%

#Mathematics - Metric Geometry#Mathematics - Geometric Topology#Primary 49Q10, Secondary 90C47, 51E99, 68R99

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

Link permanente para citações:

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

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

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 20/09/2001

Relevância na Pesquisa

26.52%

#Mathematics - Combinatorics#Mathematics - Commutative Algebra#Mathematics - Rings and Algebras#05E99#05A10#13P10

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

Link permanente para citações:

## Efficiently listing bounded length st-paths

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

Link permanente para citações:

## Sampling diffusive transition paths

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

Link permanente para citações:

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

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.

Link permanente para citações:

## Time Discrete Geodesic Paths in the Space of Images

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...

Link permanente para citações:

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

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

Link permanente para citações:

## Elliptic enumeration of nonintersecting lattice paths

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

26.52%

#Mathematics - Combinatorics#Mathematics - Classical Analysis and ODEs#05A15 (Primary) 05A17, 05A19, 05E10, 11B65, 33D15, 33E20 (Secondary)

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

Link permanente para citações:

## Riordan Paths and Derangements

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

Link permanente para citações: