Discrete Mathematics and Theoretical Computer Science

TITLE: "Computational Support for Discrete Mathematics"

EDITORS: Nathaniel Dean, Gregory E. Shannon

Published by the American Mathematical Society

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the
AMS Bookstore and
order directly from there.
DIMACS ** does not** distribute or sell these books.

This volume contains papers based on talks given at the DIMACS Workshop on Computational Support for Discrete Mathematics, March 12-14, 1992 at Rutgers University in Piscataway, New Jersey. This workshop was designed to facilitate working relationships among a diverse group of researchers concerned with the development of software for various aspects of experimental discrete mathematics. Their goal is to provide effective computational tools for research, applications prototyping, and various levels of education. We are grateful to DIMACS and NSF for their generous support.

With the recent technological advances in workstations, graphics, graphical user interfaces, and object oriented programming languages, a significant number of researchers are developing general-purpose software and integrated software systems for domains in discrete mathematics, including graph theory, combinatorics, combinatorial optimization, and sets. The goal of such software is to provide effective computational tools for research, applications prototyping, and teaching in these domains. Developing such software leads to new problems that are significant in their own right. Such problems include: effectively managing large objects or sets internally and externally; designing reusable software, interfaces, and algorithm libraries; developing effective object models for interactive algorithm design and programming; and developing user interfaces that effectively display excessively large and complex combinatorial objects.

Unfortunately, there are no obvious conferences, journals, special interest groups, or newsletters for researchers, developers, and educators interested in such software to report results, announce new systems, exchange ideas, or outline important research directions and strategies. With this lack of communication, there is gross duplication of effort, ad hoc progress in research, and a lack of viability, acceptability, and application of this area's work.

The primary goal of the workshop was to facilitate working relations between the researchers, developers, and educators, identify common research interests and applications, to demonstrate current systems, and to identify how and where workers in this area can regularly communicate and meet. A second and equally important goal was to document the current and past research in this area through a substantial proceedings.

The program was exciting. There were three excellent, inspiring talks by the keynote speakers: Ronald Read "Computer-assisted graph theory: recollections and speculations", Jon Bentley "Computational support for discrete algorithms", and Marc Brown "Algorithm animation: techniques, a system, and a novel application". The breath and depth of the invited and contributed talks were enormous, the informal discussion sessions were informative, and the software demonstrations were outstanding. There were also papers related to education and to experimental discrete mathematics. These included descriptions of current software for discrete mathematics, experience with specific implementation issues, experimental techniques and results, and applications. All of the papers were refereed.

The editors hope and expect that the considerable interest and collaborative efforts generated by this workshop will lead to continued developments with significant impact on theoretical research, applications and education.

Forward ix Preface xi Analyzing Integer Sequences 1 A. Bhansali and S.S. Skiena GDR: A Visualization Tool for Graph Algorithms 17 M. Stallmann, R. Cleaveland, and P. Hebbar Application of Computational Tools for Finitely Presented Groups 29 G. Havas and E.F. Robertson Animated Algorithms Computer Science Education with Algorithm Animation 41 P.A. Gloor, I. Lee, and A. Velez-Sosa AGE: An Animated Graph Environment 57 J. Abello, S. Sudarsky, T. Veatch, and J. Waller An Interactive, Graphical, Educationally Oriented Graph Analysis Package 71 D.S. Dillon and F.R. Smietana Network Assistant to Construct, Test, and Analyze Graph Network Algorithms 75 G.H. Bradley and H.F. Oliviera Computing Spanning Trees in NETPAD 85 Keh-Wei Lih, N. Dean, and M. Mihail An Empirical Assessment of Algorithms for Constructing a Minimum Spanning Tree 99 B.M.E. Moret and H.D. Shapiro Rectilinear Steiner Tree Minimization on a Workstation 119 C. Thomborson, B. Alpern, and L. Carter The XYZ GeoBench for the Experimental Evaluation of Geometric 137 P. Schorn Monitoring an Algorithm's Execution 153 D.A. Berque and M.K. Goldberg Implementation of Parallel Graph Algorithms on the MasPar 165 T.-S Hsu, V. Ramachandran, and N. Dean Monte Carlo and Markov Chain Techniques for Network Reliability and Sampling 199 A.L. Buchsbaum and M. Mihail Networks and Reliability in Maple 223 D.D. Harms, J.S. Devitt, and C.J. Colbourn GMP/X, An X-Windows Based Graph Manipulation Package 245 G. Zimmerman, A.H. Esfahanian, and D. Vasquez METANET: A System for Network Analysis 255 C. Gomez and M. Goursat Graph Tool: A Tool for Interactive Design and Manipulation of Graphs and Graph Algorithms 269 V.J. Leung, M.B. Dillencourt, and A.L. Bliss Improvements to GraphPack: A System to Manipulate Graphs and Digraphs 279 M. Krishnamoorthy, A. Suess, M. Onghena, F. Oxaal, and T. Spencer Extending a Graph Browser for Topological Graph Theory 297 J.I. Helfman and J.L. Gross Test Case Construction for the Vertex Cover Problem 315 L.A. Sanchis CalICo: Software for Combinatorics 327 M. Delest and N. Rouillon Formal Calculus and Enumerative Combinatorics 335 M. Delest Implementing Finite State Machines 347 K. Sutner NPDA: A Tool for Visualizing and Simulating Nondeterministic Pushdown Automata 365 D. Caugherty and S.H. Rodger Recognizing the Hidden Structure of Cayley Graphs 379 I.J. Dejter A Concept for the Representation of Data and Algorithms 391 D. Moller and R. Muller

Index of Volumes

DIMACS Homepage

Contacting the Center

Document last modified on October 28, 1998.