Approximating schedules for dynamic process graphs efficiently

A model for parallel and distributed programs, the dynamic process graph (DPG), is investigated under graph-theoretic and complexity aspects. Such graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. They are capable of representing all possible executions of a parallel or distributed program in a very compact way. The size of this representation can be as small as logarithmic with respect to the size of any execution of the program.

In a preceding paper [A. Jakoby, et al., Scheduling dynamic graphs, in: Proc. 16th Symposium on Theoretical Aspects in Computer Science STACS'99, LNCS, vol. 1563, Springer, 1999, pp. 383–392] we have analysed the expressive power of the general model and various variants of it. We have considered the scheduling problem for DPGs given enough parallelism taking into account communication delays between processors when exchanging data. Given a DPG the question arises whether it can be executed (that means whether the corresponding parallel program has been specified correctly), and what is its minimum schedule length.

In this paper we study a subclass of dynamic process graphs called -output DPGs, which are appropriate in many situations, and investigate their expressive power. In a previous paper we have shown that the problem to determine the minimum schedule length is still intractable for this subclass, namely this problem is -complete as is the general case. Here we will investigate structural properties of the executions of such graphs. A natural graph-theoretic conjecture that executions must always split into components that are isomorphic to subgraphs turns out to be wrong. We are able to prove a weaker property. This implies a quadratic upper bound on the schedule length that may be necessary in the worst case, in contrast to the general case, where the optimal schedule length may be exponential with respect to the size of the representing DPG. Making this bound constructive, we obtain an approximation to a -complete problem. Computing such a schedule and then executing the program can be done on a parallel machine in polynomial time in a highly distributive fashion.     

Compact directed acyclic word graphs for a sliding window

Suffix trees are a well-known and widely-studied data structure highly useful for string matching. The suffix tree of a string w can be constructed in O(n) time and space, where n denotes the length of w. Larsson achieved an efficient algorithm to maintain suffix trees for a sliding window. It contributes to prediction by partial matching (PPM) style statistical data compression scheme. Compact directed acyclic word graphs (CDAWGs) are a more space-economical data structure for indexing strings. In this paper we propose a linear-time algorithm to maintain CDAWGs for a sliding window.     

Learning to See: Making Sense of the Mathematics of Change in Middle School

In this article, we will describe the results of a study of 6th grade students learning about the mathematics of change. The students in this study worked with software environments for the computer and the graphing calculator that included a simulation of a moving elevator, linked to a graph of its velocity vs. time. We will describe how the students and their teacher negotiated the mathematical meanings of these representations, in interaction with the software and other representational tools available in the classroom. The class developed ways of selectively attending to specific features of stacks of centimeter cubes, hand-drawn graphs, and graphs (labeled velocity vs. time) on the computer screen. In addition, the class became adept at imagining the motions that corresponded to various velocity vs. time graphs. In this article, we describe this development as a process of learning to see mathematical representations of motion. The main question this article addresses is: How do students learn to see mathematical representations in ways that are consistent with the discipline of mathematics? This revised version was published online in July 2006 with corrections to the Cover Date.     

Families of Line-Graphs and Their Quantization

Any directed graph G with N vertices and J edges has an associated line-graph L(G) where the J edges form the vertices of L(G). We show that the non-zero eigenvalues of the adjacency matrices are the same for all graphs of such a family L ⁿ (G). We give necessary and sufficient conditions for a line-graph to be quantisable and demonstrate that the spectra of associated quantum propagators follow the predictions of random matrices under very general conditions. Line-graphs may therefore serve as models to study the semiclassical limit (of large matrix size) of a quantum dynamics on graphs with fixed classical behaviour.     

A graph-theoretic approach to modeling metabolic pathways

Summary The metabolic pathways of medazepam, oxazepam, and diazepam were modeled using graph-theoretic transforms which are incorporable into computer-assisted metabolic analysis programs. The information, represented in the form of a graph-theoretic transform kit, which was obtained from these pathways was then used to predict the metabolites of other benzodiazepine compounds. The transform kits gave statistically significant predictions with respect to a statistical method for evaluating the performance of the transform kits.     

A rigid graph for every set

A graph G is called rigid if the identical mapping V(G)→V(G) is the only homomorphism G→G. In this note we give a simple construction of a rigid oriented graph on every set. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 108–110, 2002     

Gk^d图的平面性和平面图的色数

利用欧拉公式研究了Gdk图的平面性,获得了一个重要定理,并由此得到了关于平面图色数的一个结论.     

Geometric and Combinatorial Realizations of Crystal Graphs

For irreducible integrable highest weight modules of the finite and affine Lie algebras of type A and D, we define an isomorphism between the geometric realization of the crystal graphs in terms of irreducible components of Nakajima quiver varieties and the combinatorial realizations in terms of Young tableaux and Young walls. For type A_n⁽¹⁾, we extend the Young wall construction to arbitrary level, describing a combinatorial realization of the crystals in terms of new objects which we call Young pyramids. Presented by P. Littleman Mathematics Subject Classifications (2000) Primary 16G10, 17B37. Alistair Savage: This research was supported in part by the Natural Sciences and Engineering Research Council (NSERC) of Canada and was partially conducted by the author for the Clay Mathematics Institute.