𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Polynomial-Time Analysis of Toroidal Periodic Graphs

✍ Scribed by F. Höfting; E. Wanke

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
177 KB
Volume
34
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

A toroidal periodic graph G D is defined by an integral d = d matrix D and a directed graph G in which the edges are associated with d-dimensional integral vectors. The periodic graph has a vertex for each vertex of the static graph and for each integral position in the parallelpiped defined by the columns of D. There is an edge from vertex u at position y to vertex ¨at position z in the periodic graph if and only if there is an edge from u to ¨with vector t in the static graph such Ž . that the difference z y y q t is the sum of integral multiples of columns of D.

Ž . We show that 1 the general path problem in toroidal periodic graphs can be Ž . solved with methods from linear integer programming, 2 path problems for toroidal periodic graphs G D can be solved in polynomial time if G has a bounded Ž . number of strongly connected components, 3 the number of strongly connected components in a toroidal periodic graph can be determined in polynomial time, Ž .

D and 4 a periodic description for each strongly connected component of G can be found in polynomial time.

📜 SIMILAR VOLUMES

A HYBRID FORMULATION FOR THE ANALYSIS OF
A HYBRID FORMULATION FOR THE ANALYSIS OF TIME-PERIODIC LINEAR SYSTEMS VIA CHEBYSHEV POLYNOMIALS
✍ E.A. Butcher; S.C. Sinha 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 239 KB

## 1.  Recently several studies (see e.g. references [1,2]) have been reported in which the solutions of both constant and time-varying systems are expressed in terms of Chebyshev polynomials. The first applications of orthogonal polynomials to differential equations with periodic coeff

Separation of the time periods with domi
Separation of the time periods with dominant climatologic parameters by multivariate statistical analysis
✍ Mira Paskota; Nedeljko Todorović; Dragana Vujović 📂 Article 📅 2012 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

## Abstract Climatology is one of the areas that rely on collecting huge quantities of data. The longer a time period is observed, the better; the more parameters are included, the better. But the human mind cannot easily extract useful information from the abundance of data; thus, many valuable fa

THE INFLUENCE OF PERIOD VARIATION ON TIM
THE INFLUENCE OF PERIOD VARIATION ON TIME–FREQUENCY ANALYSIS OF THE WESTLAND HELICOPTER DATA
✍ SOON-SENG LAU; PETER J. SHERMAN 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 287 KB

In this work, we address the in#uence of period variation on the Westland CH-46E helicopter vibration data. The estimation of the time-varying shaft speed by using a newly developed constrained AR(2) estimator and the well-known EKF estimator will be discussed. The in#uence that the period variation