Search results for "Graph Theory"
showing 10 items of 784 documents
The existence of an a.c.i.p.m. for an expanding map of the interval; the study of a counterexample
1989
Convergence of GBS Operators
2018
In [59, 60], Bogel introduced a new concept of Bogel-continuous and Bogel-differentiable functions and also established some important theorems using these concepts. Dobrescu and Matei [80] showed the convergence of the Boolean sum of bivariate generalization of Bernstein polynomials to the B-continuous function on a bounded interval. Subsequently, Badea and Cottin [46] obtained Korovkin theorems for GBS operators.
An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid
2008
We investigate the intersection of two finitely generated submonoids of the free monoid on a finite alphabet. To this purpose, we consider automata that recognize such submonoids and we study the product automata recognizing their intersection. By using automata methods we obtain a new proof of a result of Karhumaki on the cha- racterization of the intersection of two submonoids of rank two, in the case of prefix (or suffix) generators. In a more general setting, for an arbitrary number of generators, we prove that if H and K are two finitely generated submonoids generated by prefix sets such that the product automaton associated to H ∩ K has a given special property then �(H ∩ K) ≤ �(H)�(K…
A new formulation of the loop-tree duality at higher loops
2019
We present a new formulation of the loop-tree duality theorem for higher loop diagrams valid both for massless and massive cases. $l$-loop integrals are expressed as weighted sum of trees obtained from cutting $l$ internal propagators of the loop graph. In addition, the uncut propagators gain a modified $i \delta$-prescription, named dual-propagators. In this new framework one can go beyond graphs and calculate the integrand of loop amplitudes as a weighted sum of tree graphs, which form a tree-like object. These objects can be computed efficiently via recurrence relations.
The computational complexity of the criticality problems in a network with interval activity times
2002
Abstract The paper analyzes the criticality in a network with interval activities duration times. A natural generalization of the criticality notion (for a path, an activity and an event) for the case of network with interval activity duration times is given. The computation complexity of five problems linked to the introduced criticality notion is presented.
An integral representation for decomposable measures of measurable functions
1994
We start with a measurem on a measurable space (Ω,A), decomposable with respect to an Archimedeant-conorm ⊥ on a real interval [0,M], which generalizes an additive measure. Using the integral introduced by the second author, a Radon-Nikodym type theorem, needed in what follows, is given.
The Asynchronous Leontief Model
1992
International audience; The traditional dynamic Leontief model is synchronous: every vertex acts simultaneously. A model with delays of action has been proposed, but it still remains synchronous. In this paper we propose an asynchronous version of the model that allows realistic computations. We fiurnish an algorithm and a program.
The small-world of 'Le Petit Prince': Revisiting the word frequency distribution
2016
[EN] Many complex systems are naturally described through graph theory, and different kinds of systems described as networks present certain important characteristics in common. One of these features is the so-called scale-free distribution for its node s connectivity, which means that the degree distribution for the network s nodes follows a power law. Scale-free networks are usually referred to as small-world because the average distance between their nodes do not scale linearly with the size of the network, but logarithmically. Here we present a mathematical analysis on linguistics: the word frequency effect for different translations of the Le Petit Prince in different languages. Compar…
Time-Efficient Quantum Walks for 3-Distinctness
2013
We present two quantum walk algorithms for 3-Distinctness. Both algorithms have time complexity $\tilde{O}(n^{5/7})$, improving the previous $\tilde{O}(n^{3/4})$ and matching the best known upper bound for query complexity (obtained via learning graphs) up to log factors. The first algorithm is based on a connection between quantum walks and electric networks. The second algorithm uses an extension of the quantum walk search framework that facilitates quantum walks with nested updates.
Every triangle-free induced subgraph of the triangular lattice is(5m,2m)-choosable
2014
A graph G is (a,b)-choosable if for any color list of size a associated with each vertex, one can choose a subset of b colors such that adjacent vertices are colored with disjoint color sets. This paper proves that for any integer m>=1, every finite triangle-free induced subgraph of the triangular lattice is (5m,2m)-choosable.