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:
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
x1,...,xm for the equation
s=gcd(s1,...,sm)=
x1s1+...+xmsm,
where s1,...,sm 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,q2) 2-arc transitive graphs GAMMA of valency
9 such that Aut(GAMMA)=Z3.G, for some almost
simple group G with socle PSU(3,q2). 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
lp-norm shortest Extended GCD multiplier problem:
given a1,...,an in Z, find an
lp-norm shortest gcd multiplier for
a1,...,an, i.e., a vector x in
Zn with minimum
sum(|xi|p)1/p satisfying
sum(xiai) =
gcd(a1,...,an).
First, we prove that the shortest GCD multiplier problem (in its feasibility recognition form) is NP-complete for every lp-norm with p in N. We then strengthen this negative result by ruling out even polynomial-time algorithms which only approximate an lp-norm shortest gcd multiplier within a factor n1/(p logg n), for g an arbitrary small positive constant, under the widely accepted complexity theory assumption NP not in DTIME(npoly(log n)).
For positive results we focus on the l2-norm GCD multiplier problem. We show that approximating this problem within a factor of n1/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 l2-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.
