Abstract We explore the use of qualitative reasoning to predict the behaviour of a dynamical system given a change in one of its parameters based upon a qualitative representation of its bifurcation diagram. We present three algorithms to perform this task. The first algorithm generates a qualitative representation from a quantitative representation of the bifurcation diagram of the system. The second uses the qualitative representation to simulate the behaviour of the system given a sequence of parameter adjustments or perturbations. The third algorithm solves the opposite, control problem: it determines what parameters to change to take the system from an initial to a given goal state. The first algorithm segments a quantitative bifurcation diagram into MSs having the same qualitative behaviour. These MSs are then interconnected into a relational network. The network is used by the other two algorithms to simulate and plan the behaviour of the system from an initial situation. We present examples illustrating the qualitative representations and the behaviours of the simulation and planning algorithms for dynamical systems of one parameter.

Computer science graduates face unprecedented opportunities and unforeseen challenges in today's highly global economy. These students will have to work and to think with international perspectives and cultural awareness. In this paper, we report on our experiences organizing and teaching the Pacific Rim Summer Schools in Global Distributed Software Development. We describe the motivation for our focus, our summer school curricula and programs, provide information on the costs of organizing and running the summer schools, and examine the sustainability of our program. We conclude with a discussion of the role of such experiences in computer science curricula and in the education of American and international computer science professionals.

Internationalization of computer science education involves incorporating awareness, knowledge and skills of professional life in a global environment. Through an NSF CPATH1 grant we have established a Pacific Rim community of computer science departments, high tech industry and international programs exploring a new model of computer science education that focuses on the knowledge, skills and competencies necessary for professional success and leadership in a global context. This paper describes our progress in building an international community of computer science educators, as well as our efforts in curricular innovation and establishment of international summer schools. Internationalization of computer science education will help attract the best and brightest students and broaden the appeal of computer science to a much more diverse population. Computer science will be seen as a pathway to a career not in an isolated cubicle but in the wide-open world.

We give efficient algorithms for listing equivalence classes of k-ary strings under reversal and permutation of alphabet symbols. As representative of each equivalence class, we choose that string which is lexicographically smallest. These algorithms use space O(n) and time $O(\sqrt{k} N)$, where N is the total number of strings generated and n is the length of each string. For k = 2, we obtain a recursive decomposition of the set of binary strings that allows the strings to be generated without rejecting any strings. For $k \ge 3$, some strings must be rejected. The algorithm is simple but its exact analysis is rather complicated. In the analysis we determine a quantity of independent interest---the average length of the common prefix of two randomly chosen infinite length "restricted-growth" strings.

In this paper, we consider a large class of vertex partitioning problems and apply to them the theory of algorithm design for problems restricted to partial k-trees. We carefully describe the details of algorithms and analyze their complexity in an attempt to make the algorithms feasible as solutions for practical applications. We give a precise characterization of vertex partitioning problems, which include domination, coloring and packing problems, and their variants. Several new graph parameters are introduced as generalizations of classical parameters. This characterization provides a basis for a taxonomy of a large class of problems, facilitating their common algorithmic treatment and allowing their uniform complexity classification. We present a design methodology of practical solution algorithms for generally $\NP$-hard problems when restricted to partial k-trees (graphs with treewidth bounded by k). This "practicality" accounts for dependency on the parameter k of the computational complexity of the resulting algorithms. By adapting the algorithm design methodology on partial k-trees to vertex partitioning problems, we obtain the first algorithms for these problems with reasonable time complexity as a function of treewidth. As an application of the methodology, we give the first polynomial-time algorithm on partial k-trees for computation of the Grundy number.

We consider different plane embeddings of partial 2-trees and give an efficient algorithm constructing a minimum cardinality cover of faces, where each face is covered by exactly one vertex. These tasks are facilitated by a unique tree representation of plane embeddings of 2-trees.

article Free Access Share on An algebraic theory of graph reduction Authors: Stefan Arnborg The Royal Institute of Technology, Stockholm, Sweden The Royal Institute of Technology, Stockholm, SwedenView Profile , Bruno Courcelle Bordeaux-1 University, Talence, France Bordeaux-1 University, Talence, FranceView Profile , Andrzej Proskurowski University of Oregon, Eugene, Oregon University of Oregon, Eugene, OregonView Profile , Detlef Seese University of Karlsruhe, Karlsruhe, Germany University of Karlsruhe, Karlsruhe, GermanyView Profile Authors Info & Claims Journal of the ACMVolume 40Issue 5Nov. 1993 pp 1134–1164https://doi.org/10.1145/174147.169807Published:01 November 1993Publication History 88citation1,580DownloadsMetricsTotal Citations88Total Downloads1,580Last 12 Months72Last 6 weeks11 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Abstract A network is immune to a set of failures if all message transfers between operative sites can be completed in the presence of such failures. A set of line failures is isolated if no two failing lines are incident to the same site. Several classes of isolated line failure immune (ILFI) networks are defined, including a class with fewest lines for a given number of sites. An algorithm is presented which turns an arbitrary tree into one of these minimum ILFI networks and computes routing tables for the new network.

We consider classes of undirected, not weighted graphs which have recursive representations; these include trees, maximal outplanar graphs, k-trees, chordal graphs, and minimally two-connected graphs. We investigate invariants of recursive labelings of some of these graphs. One consequence of the existence of such invariant relation is that we can describe a single-source, shortest-paths spanning tree in terms of the recursive representation. We also discuss reasons why we cannot do this as well for other types of recursive graphs.

"Broadcasting" is an information dissemination process in which a member of a system generates a message communicated to all other members. We model this process by ordered rooted trees and investigate a special class of rooted trees allowing broadcasting from the root to all other vertices of the tree in the minimum time (over all rooted trees with n vertices). We characterize trees from this class ("mbt") and give an algorithm deciding membership in the class. We also present an algorithm to construct all mbt's with a given number of vertices and give a recursive formula to count these trees.

No abstract available.