A short summery of A, Yeo's Publications
November 19, 1998
In referring to papers I will use
the notation that (i) refers to the i'th paper in my list of publications,
while [i] refers to the list of
references in 'Survey of Anders Yeo's papers'.
I furthermore assume that the reader is familiar with
standard graph theoretical terminology and refer the reader to
section 10 of 'Survey of Anders Yeo's papers' for some non-standard
terminology.
I have done work in the following areas of
mathematics and theoretical computer science:
graph theory, combinatorics, probability, combinatorial optimization,
complexity theory,
operational research and algorithmics.
Even though I have looked at a broad area of mathematics
and theoretical computer science, most of my work has been on
path and cycle problems in directed graphs. I will now describe some
of my results:
Semicomplete multipartite digraphs (SMD)
In (4) I solved three
conjectures, by C.Q. Zhang (stated 1989),
by Guo and Volkmann and by Bang-Jensen,
Gutin and myself, respectively. The
result conjectured by C.Q. Zhang, was that all diregular SMD's
are Hamiltonian. Several papers (see
(13,20,21,28,31)
and [61]) have since
been devoted to generalizing this result. They all use the
structural result obtained in (4).
My structural result
in (4) has furthermore been used by
several other researches, in order to
prove results on SMD's.
In particular the results
obtained in (21,28,31)
prove the following:
All diregular c-partite tournaments are vertex-pancyclic,
when c < 4, all diregular 4-partite
tournaments are vertex-pancyclic,
except for possibly a finite number, and finally
all almost diregular c-partite tournaments are vertex-pancyclic,
when c > 4, except for possibly a finite number.
The results in (21,28) prove a conjecture from [61]
(except for possibly a finite number of counter-examples).
In (13) we prove a
result on which irregularity in a SMD
guarantees Hamiltonicity. This result also implies the
conjecture by C.Q. Zhang, and is of crucial importance in the papers
(21,22,28,29,31).
The result in (13) also solves a couple of
conjecture by Volkmann, [61].
The structural result obtained in (4)
is also used to show results
on tournaments (see (5,22))
as well as other results on SMD's (see
(7,13,15,20,21,24,28,29,31)).
One of the first question
asked about a class of digraphs is if the Hamilton cycle problem
is polynomially solvable. The Hamiltonian cycle problem for SMD's
has therefore naturally attracted the interest of many researchers
(see e.g. [5,64]), and it was posed
as a conjecture in [33],
and mentioned to Bang-Jensen by C. Thomassen more than ten years ago.
In (7) we were finally able
to give a polynomial algorithm for the
Hamiltonian cycle problem for SMD's.
Recently, in (24), I have extended this result,
by giving an algorithm,
which in polynomial time can find a cycle covering any given set
of vertices in a SMD (if such a cycle exists). The existens of such
an algorithm was conjectured in (7).
In 1982, [57], Thomassen
conjectured that if I is a set of
k-1 arcs in a k-strong tournament T,
then T-I has a Hamiltonian
cycle. This conjecture was proved by Fraisse and
Thomassen in 1987, [24].
In (5) we
prove a stronger result, which easily implies the result
by Fraisse and Thomassen. Our result will in many
cases prove that T-I in Hamiltonian,
even when the strong connectivity
of T is smaller than k.
In order to obtain the result in (5),
we again needed to use the structural result obtained in (4).
In (22) we furthermore give a best possible bound on which arcs
can be deleted from a tournament with given irregularity, such that
the resulting digraph is still Hamiltonian.
Other Areas
In (6) Gutin and myself proved that a hypertournament
is Hamiltonian if and only if it is strongly connected, thus extending
the 'main' basic theorem for tournaments (see section 6, in
'Survey of Anders Yeo's papers', for definitions on hypertournaments).
We also proved the surprising result that, despite this characterization
of which hypertournaments are Hamiltonian, it is still NP-complete to
decide if a k-hypertournament is Hamiltonian (k >= 4).
In (8) I extend a result
by Grossman and Haggkvist (see [28])
from 1983 on 2-edge coloured graphs, to arbitrary edge-coloured graphs.
That is I give a precise characterization of which edge-coloured graphs
contain an alternating cycle. In (9) and (10) I, together with
coauthors, do more work in the area of edge-coloured graphs and
arc-coloured digraphs.
I have also done some work in extremal
graph theory. In (14) I, together
with Jing Huang, give good bounds for the maximum and minimum number
of edges in vertex-critical graphs of diameter two. This problem
was started decades ago by Erdos and his collaborators, and has since
attracted the attention of several researchers.
Our results also gives a negative answer to a question asked implicitly
by Plesnik.
In (12) Bang-Jensen, Huang and
myself introduce a new class of graphs,
called round graphs. We show that round graphs have
nice structural properties. In (12) we identify two
subclasses of round graphs,
namely, round graphs of type I and round graphs of type II. These two
classes can be transformed to each other by
taking the complementary graphs.
We observe that, by a result of Tucker [60], round
graphs of type I form a class of graphs,
which properly contains the class of
proper circular arc graphs and is properly contained in the class
of general circular arc graphs. This makes round graphs of type I
an interesting class of graphs to study.
In (12) we show that round graphs of type I
(and hence of type II) can be recognized in linear time,
even though there is still no known polynomial
algorithm to recognize a general round graph.
Furthermore we describe optimal
linear time algorithms for finding
a maximum clique, a maximum matching, and a Hamiltonian cycle (if
one exists), for the class of round graphs of type II.
Finally, we pose a number of open problems and conjectures
concerning the structure and algorithmic properties of round
graphs.
The Travelling Salesman Problem (TSP) & The
Quadratic Assignment Problem (QAP)
Finally I have done some work on the
traveling salesman problem, which is one of the best known
problems in graph theory, and in combinatorial optimization.
In (16) we for each tour, t, give a set of tours
S(t), such
that we can find the optimal tour in S(t) in polynomial time.
We furthermore construct the sets S(t), such that for any
two tours t1 and t5, there exists tours
t2, t3 and t4 such that
t2 lies in S(t1),
t3 lies in S(t2),
t4 lies in S(t3),
and t5 lies in S(t4),
In contrast,
for pyramidal neighbourhoods considered
by J. Carlier and P. Villon (1990), one needs up to c*log n
intermediate tours to 'move' from a tour to another one (where
c is some constant.
Deineko and Woeginger asked if
there exists a polynomial time
searchable set of size at least
(a*n)!, for some a > 1/2,
where n is the number of vertices in the TSP.
In (19) I prove that such a set exist for all
a < 1.
Using a slight variation of the above algorithm we can
search a set of
size (a*n)!
in time O(n^{1+2a}), for any 0 < a < 1.
Deineko and Woeginger proved (indirectly) that if P is
not equal to NP then
no algorithm for searching a neighbourhood of size
(a*n)! can
run faster then O(n^{1+a}).
The algorithm
in (19) has also been tested in practice and
performed very well.
Recently, in (26), we have
in fact demonstarted the existens of polynomial
time searchable sets of size (n-2)!
for the TSP, which is the best-known
result to date. We furthermore demonstrated the existens of polynomial
time searchable sets of size (n-2)! for the QAP.
This is the first polynomial
time searchable set, for the QAP, which has size
greater than a polynomial in n.
Anders Yeo
<yeo@Math.UVic.CA>