共查询到20条相似文献,搜索用时 31 毫秒
1.
We describe a new algorithm, the (k, ℓ)-pebble game with colors, and use it to obtain a characterization of the family of (k, ℓ)-sparse graphs and algorithmic solutions to a family of problems concerning tree decompositions of graphs. Special instances
of sparse graphs appear in rigidity theory and have received increased attention in recent years. In particular, our colored
pebbles generalize and strengthen the previous results of Lee and Streinu [12] and give a new proof of the Tutte-Nash-Williams
characterization of arboricity. We also present a new decomposition that certifies sparsity based on the (k, ℓ)-pebble game with colors. Our work also exposes connections between pebble game algorithms and previous sparse graph algorithms
by Gabow [5], Gabow and Westermann [6] and Hendrickson [9].
Ileana Streinu; Research of both authors funded by the NSF under grants NSF CCF-0430990 and NSF-DARPA CARGO CCR-0310661 to
the first author. 相似文献
2.
Frank Duzaar 《Journal of Mathematical Analysis and Applications》2009,352(1):301-335
We give a survey of known and not known harmonic type approximation lemmas which are descendants of the classical De Giorgi's one, and we outline some of their recent or possible applications. 相似文献
3.
Tim Langtry Mary Coupland Beverley Moore 《International Journal of Mathematical Education in Science & Technology》2013,44(5):699-718
Aspects of the problem of teaching introductory undergraduate mathematics are considered in the context of both an increased participation rate in higher education as well as increasingly sophisticated computational technology. In particular, some of the changes in student and governmental expectations of course outcomes are canvassed, and an ongoing project initiated as a response both to these changes and to the availability of modern computational algebra systems that have sophisticated user interfaces is described. The project's aim is to develop students' mathematical understanding by undertaking practical laboratory work focused on applications that are perceived by students to be relevant to their social context and employment aspirations. 相似文献
4.
Jacky Cresson 《随机分析与应用》2018,36(2):224-239
We discuss a method, which was popularized by E. J. Allen and that is frequently used in applications to construct SDE models. The derivation procedure is based on information about the elementary processes involved in the dynamics and their corresponding probabilities. We formulate criteria for the viability of the resulting models. In particular, explicit necessary and sufficient conditions are deduced for the non-negativity and/or boundedness of solutions. Moreover, we show that the class of deterministic models for which the construction leads to an admissible SDE extension is strongly limited. Several examples are presented to illustrate the implications of our results. 相似文献
5.
Roland Pulch 《Mathematical and Computer Modelling of Dynamical Systems: Methods, Tools and Applications in Engineering and Related Sciences》2013,19(4):315-330
In radio frequency (RF) applications, slowly varying signals often modulate the amplitude and frequency of fast carrier waves. Thus a numerical simulation of the differential algebraic equations (DAEs) modelling the electric circuit becomes tedious. Alternative models are required to achieve efficient simulations. A multivariate formulation of signals yields a suitable representation via decoupling the widely separated time scales. Consequently, the circuit's DAEs change into warped multirate partial DAEs. On the other hand, the transient behaviour of the circuit can also be approximated by a parameter-dependent DAE model including a multivariate structure. The properties of this alternative strategy are investigated. In particular, the two multidimensional approaches are compared with respect to the simulation of RF signals. 相似文献
6.
K. C. Patidar 《Journal of Difference Equations and Applications》2016,22(6):817-849
In this paper, we review many recent developments and further applications of nonstandard finite difference (NSFD) methods encountered in the past decade. In particular, it is a follow up article of the one published in 2005 [K.C. Patidar, On the use of non-standard finite difference methods, J. Differ. Equ. Appl. 11 (2005), pp. 735–758]. It also includes those research contributions in this field that are very significant and published prior to the above article but were not included in the above paper simply because we did not have access to them when we wrote the above article. We also give a detailed account on various definitions/notions of NSFD methods appeared in the literature in past two decades. All contributions are listed chronologically except that in some instances we have grouped certain works to show connectivity in those fields. While categorizing these research contributions, we considered a number of different application areas. Moreover, due to space limitations, firstly, we have not included all works that used NSFD methodology but certainly important contributions are given due consideration, and secondly, we have only included the salient features of the proposed numerical schemes for many of these contributions and ignored other contents where the involved approaches sound fairly standard thus implying why these methods are known robust. Of course, the cases when there is a specific variation, in the theoretical analysis of these NSFD schemes, are highlighted with more details. 相似文献
7.
Stieltjes differential equations, which contain equations with impulses and equations on time scales as particular cases, simply consist on replacing usual derivatives by derivatives with respect to a nondecreasing function. In this paper we prove new existence results for functional and discontinuous Stieltjes differential equations and we show that such general results have real world applications. Specifically, we show that Stieltjes differential equations are specially suitable to study populations which exhibit dormant states and/or very short (impulsive) periods of reproduction. In particular, we construct two mathematical models for the evolution of a silkworm population. Our first model can be explicitly solved, as it consists on a linear Stieltjes equation. Our second model, more realistic, is nonlinear, discontinuous and functional, and we deduce the existence of solutions by means of a result proven in this paper. 相似文献
8.
Marcus A. Khuri 《Nonlinear Analysis: Theory, Methods & Applications》2011,74(17):6405-6415
In this paper we outline a general method for finding well-posed boundary value problems for linear equations of mixed elliptic and hyperbolic type, which extends previous techniques of Berezanskii, Didenko, and Friedrichs. This method is then used to study a particular class of fully nonlinear mixed type equations which arise in applications to differential geometry. 相似文献
9.
Silvia Noschese Paolo E. Ricci 《Journal of Computational Analysis and Applications》2003,5(3):333-340
We generalize the Bell polynomials in order to derive an operational tool for the differentiation of composite functions in several variables. In particular we show a formula that relates the Bell polynomials for multivariable composite functions to the classical ones. Some applications are suggested. 相似文献
10.
Advances in Computer Algebra software have made calculations possible that were previously intractable. Our particular interest is in the investigation of limit cycles of nonlinear differential equations. We describe some recent developments in handling very large computations involving resultants and present an example of a nonlinear differential system of degree three with nine small amplitude limit cycles surrounding a focus. We know of no examples of cubic systems with more than this number bifurcating from a fine focus, as opposed to a centre. Our example appears to be the first to have been obtained without recourse to some numerical calculation. 相似文献
11.
Knut S. Eckhoff. 《Mathematics of Computation》1998,67(223):1063-1087
By splitting a given singular function into a relatively smooth part and a specially structured singular part, it is shown how the traditional Fourier method can be modified to give numerical methods of high order for calculating derivatives and integrals. Singular functions with various types of singularities of importance in applications are considered. Relations between the discrete and the continuous Fourier series for the singular functions are established. Of particular interest are piecewise smooth functions, for which various important applications are indicated, and for which numerous numerical results are presented.
12.
David Mercier Éric Lefèvre François Delmotte 《International Journal of Approximate Reasoning》2012,53(2):146-158
In this article, the contextual discounting of a belief function, a classical discounting generalization, is extended and its particular link with the canonical disjunctive decomposition is highlighted. A general family of correction mechanisms allowing one to weaken the information provided by a source is then introduced, as well as the dual of this family allowing one to strengthen a belief function. 相似文献
13.
Marcos J. CorreiaPaulo C. Rech 《Applied mathematics and computation》2012,218(12):6711-6715
In this paper we propose a numerical method to characterize hyperchaotic points in the parameter-space of continuous-time dynamical systems. The method considers the second largest Lyapunov exponent value as a measure of hyperchaotic motion, to construct two-dimensional parameter-space color plots. Different levels of hyperchaos in these plots are represented by a continuously changing yellow-red scale. As an example, a particular system modeled by a set of four nonlinear autonomous first-order ordinary differential equations is considered. Practical applications of these plots include, by instance, walking in the parameter-space of hyperchaotic systems along desirable paths. 相似文献
14.
O. V. Borodin A. O. Ivanova M. Montassier P. Ochem A. Raspaud 《Journal of Graph Theory》2010,65(2):83-93
A graph G is (k,0)‐colorable if its vertices can be partitioned into subsets V1 and V2 such that in G[V1] every vertex has degree at most k, while G[V2] is edgeless. For every integer k?0, we prove that every graph with the maximum average degree smaller than (3k+4)/(k+2) is (k,0)‐colorable. In particular, it follows that every planar graph with girth at least 7 is (8, 0)‐colorable. On the other hand, we construct planar graphs with girth 6 that are not (k,0)‐colorable for arbitrarily large k. © 2009 Wiley Periodicals, Inc. J Graph Theory 65:83–93, 2010 相似文献
15.
Darryn Bryant 《Journal of Combinatorial Theory, Series A》2010,117(8):1258-1284
Let m1,m2,…,mt be a list of integers. It is shown that there exists an integer N such that for all n?N, the complete graph of order n can be decomposed into edge-disjoint cycles of lengths m1,m2,…,mt if and only if n is odd, 3?mi?n for i=1,2,…,t, and . In 1981, Alspach conjectured that this result holds for all n, and that a corresponding result also holds for decompositions of complete graphs of even order into cycles and a perfect matching. 相似文献
16.
We study functions on the class group of a toric variety measuring the rates of growth of the cohomology groups of multiples of divisors. We show that these functions are piecewise polynomial with respect to finite polyhedral chamber decompositions. As applications, we express the self-intersection number of a T-Cartier divisor as a linear combination of the volumes of the bounded regions in the corresponding hyperplane arrangement and prove an asymptotic converse to Serre vanishing. 相似文献
17.
V. A. Gutnikov V. Yu. Kiryakin I. K. Lifanov A. V. Setukha S. L. Stavtsev 《Computational Mathematics and Mathematical Physics》2007,47(12):2002-2013
A mathematical model of sound propagation from a noise source in urban areas is constructed. The exterior Neumann problem for the scalar Helmholtz equation is reduced to a system of hypersingular integral equations. A numerical method for solving the system of integral equations is described. The convergence of the quadrature formulas underlying the numerical method is estimated. Numerical results are presented for particular applications. 相似文献
18.
Yuri Berest 《Acta Appl Math》1998,53(2):125-185
We develop a new unified approach to the problem of constructing linear hyperbolic partial differential operators that satisfy Huygens' principle in the sense of J. Hadamard. The underlying method is essentially algebraic and based on a certain nonlinear extension of similarity (gauge) transformations in the ring of analytic differential operators.The paper provides a systematic and self-consistent review of classical and recent results on Huygens' principle in Minkowski spaces. Most of these results are carried over to more general pseudo-Riemannian spaces with the metric of a plane gravitational wave.A particular attention is given to various connections of Huygens' principle with integrable systems and the soliton theory. We discuss the link to nonlinear KdV-type evolution equations, Darboux–Bäcklund transformations and the bispectral problem in the sense of Duistermaat, Grünbaum and Wilson. 相似文献
19.
Changfeng Gui 《Journal of Functional Analysis》2008,254(4):904-933
New identities for elliptic partial differential equations are obtained. Several applications are discussed. In particular, Young's law for the contact angles in triple junction formation is proven rigorously. Structure of level curves of saddle solutions to Allen-Cahn equation are also carefully analyzed. 相似文献
20.
In certain applications of stochastic differential equations a numerical solution must be found corresponding to a particular sample path of the driving process. The order of convergence of approximations based on regular samples of the path is limited, and some approximations are asymptotically efficient in that they minimise the leading coefficient in the expansion of mean-square errors as power series in the sample step size. This paper considers approximations based on irregular samples taken at the passage times of the driving process through a series of thresholds. Such approximations can involve less computation than their regular sample counterparts, particularly for real-time applications. The orders of convergence of the Euler and Milshtein approximations are derived and a new approximation is defined which is asymptotically efficient with respect to the irregular samples. Its asymptotic mean-square error is less than half that of efficient approximations based on regular sample 相似文献