DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME FIFTEEN
TITLE: "Computational Support for Discrete Mathematics"
EDITORS: Nathaniel Dean, Gregory E. Shannon
Published by the American Mathematical Society


Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

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.



PREFACE


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.


TABLE OF CONTENTS





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 Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.