**TITLE:** Groups of deficiency zero

**AUTHORS:** George Havas, M.F. Newman and E.A. O'Brien

**CITATION:** *Geometric and Computational Perspectives on Infinite Groups*, DIMACS Series in Discrete Mathematics and Theoretical Computer Science **25** (1996) 53-67

**ABSTRACT:** We make a systematic study of groups of deficiency zero, concentrating on groups of prime-power order. We prove that a number of p-groups have deficiency zero and give explicit balanced presentations for them. This significantly increases the number of such groups known. We describe a reasonably general computational approach which leads to these results. We also list some other finite groups of deficiency zero.

**TITLE:** A new algorithm and refined bounds for extended gcd computation

**AUTHORS:** David Ford and George Havas

**CITATION:** *Algorithmic Number Theory*, Lecture Notes in Computer Science **1122** (1996) 145-150

**ABSTRACT:** Extended gcd computation is interesting itself. It also plays a fundamental role in other calculations. We present a new algorithm for solving the extended gcd problem. This algorithm has a particularly simple description and is practical. It also provides refined bounds on the size of the multipliers obtained.

**TITLE:** Central factors of deficiency zero groups

**AUTHORS:** George Havas and Edmund F. Robertson

**CITATION:** Communications in Algebra **24** (1996) 3483-3487

**ABSTRACT:** We answer a question of some twenty years standing: are the central factors of nilpotent groups of deficiency zero 3-generated? We prove a negative answer by giving an explicit presentation for a 3-generator, 3-relator group of order 131072 and class 5 which has central factors which are 4-generated but not 3-generated. We outline the computational techniques which lead to this result.

**TITLE:** Empirical analysis of distributed depth-first search algorithms

**AUTHORS:** S.A.M. Makki and George Havas

**CITATION:** *Proc. Eighth IASTED Internat. Conf. Parallel and Distributed Computing and Systems*, Acta Press (1996) 292-296

**ABSTRACT:** We evaluate the practical performance of two improved distributed depth-first search algorithms applied to general and commonly used network structures. In particular we study the behavior of the algorithms in terms of a parameter which depends on the network topology and routing chosen. We deduce that performance is significantly enhanced for smaller networks of sizes which arise in practice. With increasing network size the extended version of the algorithm performs appreciably better than the basic algorithm. We present some unresolved questions about these algorithms.

**TITLE:** A family of perfect hashing methods

**AUTHORS:** Bohdan S. Majewski, Nicholas C. Wormald, George Havas and Zbigniew J. Czech

**CITATION:** Computer Journal **39** (1996) 547-554

**ABSTRACT:** Minimal perfect hash functions are used for memory efficient storage and fast retrieval of items from static sets. We present an infinite family of efficient and practical algorithms for generating order preserving minimal perfect hash functions. We show that almost all members of the family construct space and time optimal order preserving minimal perfect hash functions, and we identify the one with minimum constants. Members of the family generate a hash function in two steps. First a special kind of function into an r-graph is computed probabilistically. Then this function is refined deterministically to a minimal perfect hash function. We give strong theoretical evidence that the first step uses linear random time. The second step runs in linear deterministic time. The family not only has theoretical importance, but also offers the fastest known method for generating perfect hash functions.

**TITLE:** Distributed algorithms for depth-first search

**AUTHORS:** S.A.M. Makki and George Havas

**CITATION:** Information Processing Letters **60** (1996) 7-12

**ABSTRACT:** We present distributed algorithms for constructing a depth-first search tree for a communication network which are more efficient than previous methods. Our algorithms require 2|V|-2 messages and units of time in the worst case, where |V| is the number of sites in the network, and as little as |V| messages and time units in the best case. The actual number of messages and time units depends on the network topology and possibly on the routing chosen. We can interpret this to mean that the number of messages and time units is |V|(1+r) in the worst case, where 0<=r<1 and the value of r depends on the topology and the routing. In a best case for the simplest algorithm, for example when the underlying network has a ring topology, r=0 and our basic algorithm requires |V| messages and time units, regardless of routing. We extend the basic algorithm to achieve the same best case bound for other topologies. The worst case bound, which has r=1-2/|V|, applies if the network topology is a tree. The improvement over the best of previous algorithms is achieved by dynamic backtracking, with a minor increase in message length.

**TITLE:** Integer matrix diagonalization

**AUTHORS:** George Havas and Bohdan S. Majewski

**CITATION:** Journal of Symbolic Computation **24** (1997) 399-408 (open archive)

**ABSTRACT:** We consider algorithms for computing the Smith normal form of integer matrices. Various different strategies have been proposed, primarily trying to avoid the major obstacle that occurs in such computations -- explosive growth in size of intermediate entries. We present a new algorithm with excellent performance. We investigate the complexity of such computations, indicating a relationship with an NP-complete problem. On the other hand we prove that a substantial part of Smith normal form computation can be performed in an optimal way in polynomial time. Based on this we justify our new heuristics which perform well in practice. We present experimental evidence which shows our algorithm outperforming the previous methods.

**TITLE:** Practical parallel coset enumeration

**AUTHORS:** Gene Cooperman and George Havas

**CITATION:** *Workshop on High Performance Computing and Gigabit Local Area Networks*, Lecture Notes in Control and Information Sciences **226** (1997) 15-27

**ABSTRACT:** Coset enumeration is a most important procedure for investigating finitely presented groups. We present a practical parallel procedure for coset enumeration on shared memory processors. The shared memory architecture is particularly interesting because such parallel computation is both faster and cheaper. The lower cost comes when the program requires large amounts of memory, and additional CPU's allow us to lower the time that the expensive memory is being used. Rather than report on a suite of test cases, we take a single, typical case, and analyze the performance factors in-depth. The parallelization is achieved through a master-slave architecture. This results in an interesting phenomenon, whereby the CPU time is divided into a sequential and a parallel portion, and the parallel part demonstrates a speedup that is linear in the number of processors. We describe an early version for which only 40% of the program was parallelized, and we describe how this was modified to achieve 90% parallelization while using 15 slave processors and a master.

**TITLE:** Perfect hashing

**AUTHORS:** Zbigniew J. Czech, George Havas and Bohdan S. Majewski

**CITATION:** Theoretical Computer Science **182** (1997) 1-143 (open archive)

**AWARD:**The authors received awards for this paper from the Polish National Minister for Education

**CONTENTS:**

- Introduction
- Basic definitions
- Trial and error
- Space and time requirements
- Bibliographic remarks

- Number theoretical solutions
- Introduction
- Quotient and remainder reduction
- Reciprocal hashing
- A Chinese Remainder Theorem method
- A letter-oriented scheme
- A Chinese Remainder Theorem based variation
- Another Chinese Remainder Theorem based variation
- Bibliographic remarks

- Perfect hashing with segmentation
- Introduction
- Bucket distribution schemes
- A hash indicator table method
- Using backtracking to find a hash indicator table
- A method of very small subsets
- Bibliographic remarks

- Reducing the search space
- Mapping, ordering, searching
- Using letter frequency
- Minimum length cycles
- Skewed vertex degree distribution
- Minimum length fundamental cycles
- A linear time algorithm
- Quadratic minimal perfect hashing
- Large and small buckets
- Bibliographic remarks

- Sparse table compression
- Introduction
- A single displacement method
- A double displacement method
- A letter-oriented method
- Another letter-oriented method
- Bibliographic remarks

- Probabilistic Perfect Hashing
- Introduction
- The FKS algorithm and its modifications reinterpreted
- A random graph approach
- Random hypergraphs methods
- Modifications
- Advanced applications
- Graph theoretic obstacles
- Bibliographic remarks

- Dynamic perfect hashing
- Introduction
- The FKS based method
- A real time dictionary
- Bibliographic remarks

Acknowledgements

References

**TITLE:** An efficient method for constructing a distributed depth-first search tree

**AUTHORS:** S.A.M. Makki and George Havas

**CITATION:** *PDPTA'97* (Proc. Internat. Conf. Parallel and Distributed Processing Techniques and Applications), CSREA Press (1997) 660-666

**ABSTRACT:** An efficient distributed depth-first search algorithm is presented. The algorithm in the worst case requires (1+r)(|V|-1) messages and (1+r)(|V|-1) units of time, where 0<=r<1 and |V| is the number of sites in the network. The value of r depends on the search path and the graph topology. In the best case when r=0, the algorithm requires only |V|-1 messages and time units. This new algorithm improves over the best of previous algorithms by using a stack-type structure which enables better dynamic backtracking. The improvement in worst case complexity is only minor. However it is much better in practice, manifested by significantly smaller values of r.

**TITLE:** On the worst-case complexity of integer Gaussian elimination

**AUTHORS:** Xin Gui Fang and George Havas

**CITATION:** *ISSAC'97* (Proc. 1997 Internat. Sympos. on Symbolic and Algebraic Computation), ACM Press (1997) 28-31

**ABSTRACT:** Gaussian elimination is the basis for classical algorithms for computing canonical forms of integer matrices. Experimental results have shown that integer Gaussian elimination may lead to rapid growth of intermediate entries. On the other hand various polynomial time algorithms do exist for such computations, but these algorithms are relatively complicated to describe and understand. Gaussian elimination provides the simplest descriptions of algorithms for this purpose. These algorithms have a nice polynomial number of steps, but the steps deal with long operands. Here we show that there is an exponential length lower bound on the operands for a well-defined variant of Gaussian elimination when applied to Smith and Hermite normal form calculation. We present explicit matrices for which this variant produces exponential length entries. Thus, Gaussian elimination has worst-case exponential space and time complexity for such applications. The analysis provides guidance as to how integer matrix algorithms based on Gaussian elimination may be further developed for better performance, which is important since many practical algorithms for computing canonical forms are so based.

**TITLE:** Counting trees

**AUTHORS:** George Havas, Dean G. Hoffman and Colin Ramsay

**CITATION:** *Research on Combinatorial Algorithms* (Proc. Eighth Australasian Workshop on Combinatorial Algorithms), Queensland University of Technology (1997) 1-10

**ABSTRACT:** We consider the problem of enumerating particular kinds of spanning trees of a graph. The problem is interesting in its own right and has applications in the analysis of graph algorithms. The general problem seems hard to resolve. We present an algorithm to list depth-first trees for moderate sized graphs. We use this algorithm to count the number of depth-first spanning trees in a variety of graphs, and we give the results for hypercubes, meshes and tori, and complete bipartite graphs. We also give a proof of a theoretical result for complete multipartite graphs.

**TITLE:** NC approximation algorithms for 2-connectivity augmentation in a graph

**AUTHORS:** Weifa Liang and George Havas

**CITATION:** *Euro-Par'97 Parallel Processing*, Lecture Notes in Computer Science 1300 (1997) 430-439

**ABSTRACT:** We devise NC approximation algorithms for the optimal 2-edge connectivity and the optimal 2-vertex connectivity augmentation problems. Consequently, we find an approximation solution for the problem of the minimum 2-edge (biconnected) spanning subgraph on a weighted 2-edge connected (biconnected) graph.

**TITLE:** Parallel approximate edge coloring revisited

**AUTHORS:** Weifa Liang, George Havas and Anne Street

**CITATION:** *Proceedings of PART'97: The 4th Australasian Conference on Parallel and Real-Time Systems*, Springer-Verlag (1998) 95-103.

**ABSTRACT:** This paper presents a fast NC algorithm for edge coloring a graph with an approximately optimal number of colors.

**TITLE:** Finding the k most vital edges with respect to minimum spanning trees for k=2 and 3

**AUTHORS:** Weifa Liang and George Havas

**CITATION:** Computing Theory '98 (Proc. 4th Australasian Theory Symposium), Springer Verlag (1998) 37-50.

**ABSTRACT:** Let G(V,E) be a weighted, undirected, connected simple graph with n vertices and m edges. The k most vital edge problem with respect to minimum spanning trees is to find a set S of k edges from E such that the removal of all edges in S results in the greatest increase in the weight of the minimum spanning tree in the remaining graph G(V,E-S). In this paper we present a better algorithm to solve this problem for k=2 and 3. The algorithms can also be implemented on a CREW PRAM.

**TITLE:** Symmetric presentations and orthogonal groups

**AUTHORS:** C.M. Campbell, George Havas, S.A. Linton and E.F. Robertson

**CITATION:** *The Atlas of Finite Groups: Ten Years On*, London Mathematical Society Lecture Note Series 249, Cambridge University Press (1998) 1-10.

**ABSTRACT:** We examine series of finite presentations which are invariant under the full symmetric group acting on the set of generators. Evidence from computational experiments reveals a remarkable tendency for the groups in these series to be closely related to the orthogonal groups. We examine cases of finite groups in such series and look in detail at an infinite group with such a presentation. We prove some theoretical results about 3-generator symmetric presentations and make a number of conjectures regarding n-generator symmetric presentations.

**TITLE:** Extended gcd and Hermite normal form algorithms via lattice basis reduction

**AUTHORS:** George Havas, Bohdan S. Majewski and Keith R. Matthews

**CITATION:** Experimental Mathematics **8** (1999) 125-136 (open archive)

Addenda and errata Experimental Mathematics **8** (1999) 205 (open archive)

**ABSTRACT:** Extended gcd calculation has a long history and plays an important role in computational number theory and linear algebra. Recent results have shown that finding optimal multipliers in extended gcd calculations is difficult. We present an algorithm which uses lattice basis reduction to produce small integer multipliers x_{1},...,x_{m} for the equation s=gcd(s_{1},...,s_{m})= x_{1}s_{1}+...+x_{m}s_{m}, where s_{1},...,s_{m} are given integers. The method generalises to produce small unimodular transformation matrices for computing the Hermite normal form of an integer matrix.

**TITLE:** Improved Lightpath (Wavelength) Routing in Large WDM Networks

**AUTHORS:** Weifa Liang, George Havas and Xiaojun Shen

**CITATION:** *Proc. 18th International Conference on Distributed Computing Systems*, IEEE Computer Society (1998) 516-523

**ABSTRACT:** We address the problem of efficient circuit switching in wide area networks. The solution provided is based on finding optimal routes for lightpaths and semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining several lightpaths together, using wavelength conversion at their junctions. The problem thus is to find an optimal lightpath/semilightpath in the network in terms of the cost of wavelength conversion and the cost of using the wavelengths on links. We first present fast, efficient algorithms both for the general problem and for a natural restricted version. The new algorithms outperform earlier work, providing time improvements amounting to an almost linear time factor in most cases. Also, all our algorithms can be implemented on the network in a distributed way.

**TITLE:** Matrix reduction algorithms for Euclidean rings

**AUTHORS:** George Havas and Clemens Wagner

**CITATION:** Proc. 1998 Asian Symposium on Computer Mathematics, Lanzhou University Press (1998) 65-70

**ABSTRACT:** Reduction methods are the basis of algorithms for determining canonical forms of matrices over many computational domains. Experimental results have shown that various methods based on Gaussian elimination (which is a specialized kind of reduction algorithm) in Euclidean rings may lead to rapid growth of intermediate entries. On the other hand polynomial time algorithms do exist for such computations, but these algorithms are relatively complicated to describe and understand. Straightforward reduction methods provide the simplest descriptions of algorithms for this purpose. Such algorithms have a nice polynomial number of steps, but the steps may deal with operands with very large values. Here we show that there is a doubly exponential lower bound on the operands for a well-defined reduction algorithm when applied to Smith and Hermite normal form calculation for certain Euclidean rings. We present explicit matrices for which this variant produces doubly exponential entries. Thus, reduction algorithms have worst-case exponential space and time complexity for such applications. The analysis provides guidance as to how matrix algorithms for Euclidean rings which use reduction algorithms may be further developed for better performance, which is important since many practical algorithms for computing canonical forms are so based.

**TITLE:** Functional decomposition of a class of wild polynomials

**AUTHORS:** Robert Coulter, George Havas and Marie Henderson

**CITATION:** Journal of Combinatorial Mathematics and Combinatorial Computing **28** (1998) 87-94

**ABSTRACT:** No general algorithm is known for the functional decomposition of wild polynomials over a finite field. However partial solutions exist. In particular, a fast functional decomposition algorithm for linearised polynomials has been developed using factoring methods in skew-polynomial rings. This algorithm is extended to a related class of wild polynomials, which are sub-linearised polynomials.

**TITLE:** Elementary Algebra Revisited: Randomized Algorithms

**AUTHORS:** Gene Cooperman and George Havas

**CITATION:** *Randomization Methods in Algorithm Design*, DIMACS Series in Discrete Mathematics and Theoretical Computer Science **43** (1999) 37-44

**ABSTRACT:** We look at some simple algorithms for elementary problems in algebra that yield dramatic efficiency improvements over standard methods through randomization. The randomized algorithms are, in some sense, obvious. Their formal statement was delayed partly by the need for rigorous analysis, but more so by the need to re-think traditional approaches to elementary algorithms. We illustrate this philosophy with some basic problems in computational number theory (GCD of many integers), linear algebra (low-rank Gaussian elimination) and group theory (random subproducts for subgroup construction), along with a brief survey of other areas.

**TITLE:** Automorphism groups of certain non-quasiprimitive almost simple graphs

**AUTHORS:** Xin Gui Fang, George Havas and Jie Wang

**CITATION:** *Groups St Andrews 1997 in Bath, I*, London Mathematical Society Lecture Note Series **260**, Cambridge University Press (1999) 267-274

**ABSTRACT:** A graph GAMMA is G-quasiprimitive if G is a group of automorphisms of GAMMA such that each nontrivial normal subgroup of G acts transitively on the vertices of GAMMA. We consider GAMMA a finite, connected S-locally-primitive graph with S a nonabelian simple group. We give a set of conditions under which we may guarantee that either the full automorphism group of GAMMA is not quasiprimitive or there is a non-quasiprimitive subgroup Y of Aut(GAMMA) such that C.G is maximal in Y, where C is the centralizer of S in Aut(GAMMA) and G is an almost simple group with socle S. As an application of this result we show that, in certain circumstances, we can specify Aut(GAMMA).

**TITLE:** GCD of many integers

**AUTHORS:** Gene Cooperman, Sandra Feisel, Joachim von zur Gathen and George Havas

**CITATION:** *Computing and Combinatorics,* Lecture Notes in Computer Science **1627** (1999) 310-317

**ABSTRACT:** A probabilistic algorithm is exhibited that calculates the gcd of many integers using gcds of pairs of integers; the expected number of pairwise gcds required is less than two.

**TITLE:** On routing in circulant graphs

**AUTHORS:** Jin-Yi Cai, George Havas, Bernard Mans, Ajay Nerurkar, Jean-Pierre Seifert and Igor Shparlinski

**CITATION:** *Computing and Combinatorics,* Lecture Notes in Computer Science **1627** (1999) 360-369

**ABSTRACT:** We investigate various problems related to circulant graphs -- finding the shortest path between two vertices, finding the shortest loop, and computing the diameter. These problems are related to shortest vector problems in a special class of lattices. We give matching upper and lower bounds on the length of the shortest loop. We prove NP-hardness results, and establish a worst-case/average-case connection for the shortest loop problem. A pseudo-polynomial time algorithm for these problems is also given. Our main tools are results and methods from the geometry of numbers.

**TITLE:** Groups with exponent six

**AUTHORS:** George Havas, M.F. Newman, Alice C. Niemeyer and Charles C. Sims

**CITATION:** Communications in Algebra **27** (1999) 3619-3638

**ABSTRACT:** Burnside asked questions about periodic groups in his influential paper of 1902. The study of groups with exponent six is a special case of the study of the Burnside questions on which there has been significant progress. It has contributed a number of worthwhile aspects to the theory of groups and in particular to computation related to groups. Finitely generated groups with exponent six are finite. We investigate the nature of relations required to provide proofs of finiteness for some groups with exponent six. We give upper and lower bounds for the number of sixth powers needed to define the largest two-generator group with exponent six. We solve related questions about other groups with exponent six using substantial computations which we explain.

**TITLE:** A Family of Non-Quasiprimitive Graphs Admitting a Quasiprimitive 2-Arc Transitive Group Action

**AUTHORS:** Xin Gui Fang, George Havas and Jie Wang

**CITATION:** European Journal of Combinatorics **20** (1999) 551-557 (open archive)

**ABSTRACT:** Let GAMMA be a simple graph and let G be a group of automorphisms of GAMMA. The graph is (G,2)-arc transitive if G is transitive on the set of the 2-arcs of GAMMA. In this paper we construct a new family of PSU(3,q^{2}) 2-arc transitive graphs GAMMA of valency 9 such that Aut(GAMMA)=Z_{3}.G, for some almost simple group G with socle PSU(3,q^{2}). This gives a new infinite family of non-quasiprimitive almost simple graphs.

**TITLE:** On Sims' presentation for Lyons' simple group

**AUTHORS:** Holger W. Gollan and George Havas

**CITATION:** Computational Methods for Representations of Groups and Algebras, Progress in Mathematics **173** (1999) 235-240, Birkhaeuser

**ABSTRACT:** This paper gives a verification that the corrected Sims presentation is indeed a presentation of Lyons simple group. We prove that Lyons original characterization of his new simple group works inside a permutation group of degree 8,835,156.

**TITLE:** A presentation for the Lyons simple group

**AUTHORS:** George Havas and Charles C. Sims

**CITATION:** Computational Methods for Representations of Groups and Algebras, Progress in Mathematics **173** (1999) 241-249, Birkhaeuser

**ABSTRACT:** We give a presentation of the Lyons simple group together with information on a complete computational proof that the presentation is correct. This fills a longstanding gap in the literature on the sporadic simple groups. This presentation is a basis for various matrix and permutation representations of the group.

**TITLE:** Some challenging group presentations

**AUTHORS:** George Havas, Derek F. Holt, P.E. Kenne and Sarah Rees

**CITATION:** Journal of the Australian Mathematical Society (Series A) **67** (1999) 206-213 (open archive)

**ABSTRACT:** We study four challenging presentations which arise as groups of deficiency zero. We show that two presentations are for finite groups while two are for infinite groups. This answers three questions in the literature and provides the first published example of a group of deficiency zero with soluble length seven. The tools we use are coset enumeration and Knuth-Bendix rewriting, which are well-established as methods for proving finiteness or otherwise of a finitely presented group. We briefly comment on their capabilities and compare their performance.

**TITLE:** The complexity of the extended GCD problem

**AUTHORS:** George Havas and Jean-Pierre Seifert

**CITATION:** *Mathematical Foundations of Computer Science 1999,* Lecture Notes in Computer Science **1672** (1999) 103-113

**ABSTRACT:** We undertake a thorough complexity study of the following fundamental optimization problem, known as the l_{p}-norm shortest Extended GCD multiplier problem: given a_{1},...,a_{n} in Z, find an l_{p}-norm shortest gcd multiplier for a_{1},...,a_{n}, i.e., a vector **x** in Z^{n} with minimum sum(|x_{i}|^{p})^{1/p} satisfying sum(x_{i}a_{i}) = gcd(a_{1},...,a_{n}).

First, we prove that the shortest GCD multiplier problem (in its feasibility recognition form) is NP-complete for every l_{p}-norm with p in N. We then strengthen this negative result by ruling out even polynomial-time algorithms which only approximate an l_{p}-norm shortest gcd multiplier within a factor n^{1/(p logg n)}, for g an arbitrary small positive constant, under the widely accepted complexity theory assumption NP not in DTIME(n^{poly(log n)}).

For positive results we focus on the l_{2}-norm GCD multiplier problem. We show that approximating this problem within a factor of n^{1/2} is very unlikely NP-hard by placing it in NP intersection coAM through a simple constant-round interactive proof system. This result is complemented by a polynomial-time algorithm which computes an l_{2}-norm shortest gcd multiplier up to a factor of 2^{(n-1)/2}.

This study is motivated by the importance of extended gcd calculations in applications in computational algebra and number theory. Our results rest upon the close connection between the hardness of approximation and the theory of interactive proof systems.

**TITLE:** Some Performance Studies in Exact Linear Algebra

**AUTHORS:** George Havas and Clemens Wagner

**CITATION:** *Workshop on wide area networks and high performance computing*, Lecture Notes in Control and Information Sciences **249** (1999) 161-170

**ABSTRACT:** We consider parallel algorithms for computing the Hermite normal form of matrices over Euclidean rings. We use standard types of reduction methods which are the basis of many algorithms for determining canonical forms of matrices over various computational domains. Our implementations take advantage of well-performing sequential code and give very good performance.

**TITLE:** On the automorphism groups of quasiprimitive almost simple graphs

**AUTHORS:** Xin Gui Fang, George Havas and Cheryl E. Praeger

**CITATION:** Journal of Algebra **222** (1999) 271-283 (open archive)

**ABSTRACT:** A permutation group is said to be quasiprimitive if each of its nontrivial normal subgroups is transitive. A graph GAMMA is G-quasiprimitive if G is a group of automorphisms of GAMMA such that G acts quasiprimitively on the vertices of GAMMA. In this paper we assume that G is is an almost simple group and investigate the full automorphism group of a G-quasiprimitive graph GAMMA. We show that, for a connected nonbipartite G-quasiprimitive and G-locally-primitive graph GAMMA with G almost simple one of the following three situations holds: Aut(GAMMA) is quasiprimitive; or each intransitive minimal normal subgroup of Aut(GAMMA) centralizes the socle of G; or G is an almost simple group of Lie type of characteristic p, and the socle of Aut(GAMMA) involves an explicitly known faithful GF(p)G-module M, with G, M belonging to a (short) explicit list.

**TITLE:** Finding a Low-Diameter and Low-Weight *k*-Connected Subgraph

**AUTHORS:** Weifa Liang, George Havas and Anne Street

**CITATION:** Congressus Numerantium **136** (1999) 161-175

**ABSTRACT:** Low-diameter, low-weight subgraphs have useful applications in networks. The problem is how to find them. Given a weighted undirected k-connected graph G=(V,E), let diam(G) denote the diameter of G and let w(G) the sum of the weights of the edges in G. In this context, the problem is to find a k-connected spanning subgraph G'=(V,E') of G such that the diameter and the weight of G' are minimized simultaneously. Since this problem is NP-hard, it is unlikely that there is a polynomial algorithm for it. We present an approximate solution with a performance guarantee. That is, we find a k-connected spanning subgraph G' in polynomial time such that diam(G')<=a×diam(G) and w(G')<=b×w(G*) for any fixed a>1, where G* is a minimum k-connected spanning subgraph of G and b is a constant depending on a and k.