| ||||
---|---|---|---|---|

1. | Authors: |
A. J. Yeo & G. F. Yeo
| ||

Title: | Selecting a Satisfactory Secretary. | |||

Download: | Not available | |||

Abstract: |
The probability of selecting the a'th best out of n
rankable applicants is evaluated for any given monotone stopping
rule; it is assumed that arrivals are in random order and
selection for a single position is based only on the relative ranks
of the successive arrivals. This formulation leads to
an explicit optimizing
function for selecting (with weights) one of the k best
applicants, and which can be solved directly both for a finite
and for an infinite number of applicants.
Keywords: Secretary problem, optimal stopping, best weighted choice,
combinatorics, asymptotics.
| |||

| ||||

2. | Authors: |
J. Bang-Jensen, G. Gutin & A. Yeo
| ||

Title: | On k-strong and k-cyclic Digraphs. | |||

Download: | Not available | |||

Abstract: |
Thomassen proved that there is no
degree of strong connectivity which guarantees
a cycle through two given vertices in a digraph (
Combinatorica 11 (1991) 393-395). In
this paper we consider a large family of digraphs,
including symmetric digraphs (i.e. digraphs
obtained from undirected graphs by replacing
each edge by a directed cycle of length two),
semicomplete bipartite digraphs, locally
semicomplete digraphs and all digraphs that
can be obtained from acyclic digraphs and those
mentioned above, by repeated substitutions of
digraphs from one of these classes for vertices.
We prove that for every natural number $k$,
every k-strong digraph D from the family
above is k-cyclic, i.e. for every set X of
k vertices of D, there exists a cycle of
D containing all the vertices of X. In
particular, this implies that every k-strong
quasi-transitive digraph is k-cyclic. We prove
that if X is a set of vertices in a
k-strong digraph D such that the maximum
size of an independent set in the digraph induced
by X is at most k, then D has a
collection of disjoint cycles (possibly one)
covering all the vertices of X. This generalizes
a previous result by Jackson and Ordaz (
Disc. Math. 57 (1985) 199-201). Finally,
we consider k-cyclic semicomplete multipartite
digraphs (SMD). We conjecture that
every k-strong SMD is k-cyclic and provide
some support for this conjecture.
| |||

| ||||

3. | Authors: |
G. Gutin & A. Yeo
| ||

Title: | Ranking the Vertices of a Complete Multipartite Paired Comparison Digraph. | |||

Download: | Not available | |||

Abstract: |
A paired comparison digraph (abbreviated to
PCD) D=(V,A) is a weighted digraph in which the
sum of the weights of arcs, if any, joining
two distinct vertices equals one. A one-to-one mapping
a from V onto {1,2,...,|V|} is called
a ranking of D. For every ranking a, an arc vu
in A is said to be forward if a(v) < a(u),
and backward, otherwise. The length of an arc vu is
B(vu)= p(vw)|a(v)-a(u)|, where p(vw)
is the weight of vu. The forward ( backward)
length f_D(a) (b_D(a)) of a is the
sum of the lengths of all forward (backward) arcs of
D. A ranking a is forward (backward) optimal
if f(a) is maximum ( b(a) is minimum). M.
Kano (Disc. Appl. Math., 17 (1987) 245-253)
characterized all backward optimal rankings of a
complete multipartite PCD D and raised the
problem to characterize all forward optimal rankings of
a complete multipartite PCD L. We show how
to transform the last problem into the single machine
job sequencing problem of minimizing total
weighted completion time subject to precedence "parallel
chains" constraints. This provides an algorithm
for generating all forward optimal rankings of $L$ as
well as a polynomial algorithm for finding the
average rank of every vertex in L over all forward
optimal rankings of L.
| |||

| ||||

4. | Authors: |
A. Yeo
| ||

Title: | One-Diregular Subgraphs in Semicomplete Multipartite Digraphs. | |||

Download: | Not available | |||

Abstract: |
The problem of finding necessary and sufficient
conditions for a semicomplete multipartite digraph
(SMD) to be Hamiltonian, seems to be both very
interesting and difficult. In [1]
Bang-Jensen, Gutin and Huang proved a sufficient
condition for a SMD to be Hamiltonian. A
strengthening of this condition, shown in this
paper, allows us to prove the following three results.
We prove that every k-strong SMD with at most
k-vertices in each color class is Hamiltonian
and every k-strong SMD has a cycle through
any set of k vertices. These two statements were
stated as conjectures in [3] and [2],
respectively. We also prove that every diregular
SMD is Hamiltonian, which was conjectured in a
weaker form in [4].
[1] J. Bang-Jensen, G. Gutin and J. Huang A sufficient condition for a complete multipartite digraph to be
hamiltonian, submitted.
[2] J. Bang-Jensen, G. Gutin and A. Yeo On ,
Discrete Mathematics 162 (1996) 1-11
k-strong and k-cyclic Digraphs[3] Lutz Volkmann, a talk at {\bf The Second Krakow Conference of Graph Theory,} 1994. [4] C.-Q. Zhang Hamilton paths in multipartite oriented graphs.
Ann. Discrete Math. 41 (1989) 499-514.
| |||

| ||||

5. | Authors: |
J. Bang-Jensen, G. Gutin & A. Yeo
| ||

Title: | Hamiltonian Cycles Avoiding Prescribed Arcs in Tournaments. | |||

Download: | Not available | |||

Abstract: |
In [1], 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
[2]. We prove the following stronger result. Let
T=(V,A) be a k-strong tournament on
n vertices and let X_1,X_2,...,X_l be a
partition of the vertex set V of T such that
|X_1| <= |X_2| <= ... <= |X_l|. If k >=
\sum_{i=1}^{l-1} \lfloor |X_i|/2 \rfloor + |X_l|, then
T-\cup_{i=1}^{l} \{xy\in A:\ x,y\in X_i\} has a
Hamiltonian cycle. The bound on k is sharp.
[1] C. Thomassen, Edge-disjoint Hamiltonian paths and
cycles in tournaments. Proc. London Math. Soc. 45
(1982) 151-168.
[1] P. Fraisse and C. Thomassen, Hamiltonian dicycles
avoiding prescribed arcs in tournaments. Graphs and Combin.
3 (1987) 239-250.
| |||

| ||||

6. | Authors: |
G. Gutin & A. Yeo
| ||

Title: | Hamiltonian Paths and Cycles in Hypertournaments. | |||

Download: | Not available | |||

Abstract: |
Given two integers n and k, n >=k> 1, a
k-hypertournament T on n vertices is a pair
(V,A), where V is a set of vertices, |V|=n
and A is a set of k-tuples of vertices, called
arcs, so that for any k-subset S of V, A
contains exactly one of the k! k-tuples
whose entries belong to S. A 2-hypertournament
is merely an (ordinary) tournament. A path is a
sequence v_1a_1v_2a_2v_3...v_{t-1}a_{t-1}v_t
of distinct vertices v_1,v_2,...,v_t and distinct
arcs a_1,...,a_{t-1} such that v_i precedes
v_{i+1} in a_i, 1 <= i <= t-1. A cycle can be
defined analogously. A path or cycle containing
all vertices of T (as v_i's) is Hamiltonian. T is
strong if T has a path from x to y for every
choice of distinct vertice x and y in V. We prove that every
k-hypertournament on n (>k) vertices has a
Hamiltonian path (an extension of Redei's
theorem on tournaments) and every strong
k-hypertournament with n (>k+1) vertices has a
Hamiltonian cycle (an extension of Camion's
theorem on tournaments). Despite the last result, it is
shown that the Hamiltonian cycle problem remains
polynomial time solvable only for k &60= 3 and
becomes NP-complete for every fixed integer k >= 4.
| |||

| ||||

7. | Authors: |
J. Bang-Jensen, G. Gutin & A. Yeo
| ||

Title: | A Polynomial Algorithm for the Hamiltonian Cycle problem in Semicomplete Multipartite Digraphs. | |||

Download: | Not available | |||

Abstract: |
We describe a polynomial algorithm for the Hamiltonian
cycle problem for semicomplete multipartite
digraphs. The existence of such an algorithm was
conjectured in [1] (see also [2]). [1] G. Gutin, Paths and cycles in digraphs.
Ph.D thesis,
Tel Aviv Univ., 1993.
[2] G. Gutin, Cycles and paths in semicomplete multipartite
digraphs, theorems and algorithms: a survey. J. Graph
Theory 19 (1995) 481-505.
| |||

| ||||

8. | Authors: |
A. Yeo
| ||

Title: | A Note on Alternating Cycles in Edge-coloured Graphs. | |||

Download: | Not available | |||

Abstract: |
Grossman and Haggkvist gave a sufficient
condition under which a two-edge-coloured graph must
have an alternating cycle (i.e. a cycle in which no
two consecutive edges have the same colour). We
extend their result to edge-coloured graphs
with any number of colours. That is, we show that if
there is no alternating cycle in an edge-coloured
graph G, then G contains a vertex z such
that no connected component of G-z is joined
to z with edges of more than one colour. Our result
implies that there is a polynomial-time algorithm
for deciding whether an edge-coloured graph
contains an alternating cycle.
| |||

| ||||

9. | Authors: |
G. Gutin, B. Sudakov & A. Yeo
| ||

Title: | Note on alternating directed cycles. | |||

Download: | Not available | |||

Abstract: |
The problem of the existence of an
alternating simple dicycle in a 2-arc-coloured digraph is
considered. This is a generalization of the
alternating cycle problem in 2-edge-coloured graphs
(proved to be polynomial time solvable) and
the even dicycle problem (the complexity is not known
yet). We prove that the alternating dicycle
problem is NP-complete. Let f(n) (g(n),
resp.) be the minimum integer such that if every
monochromatic indegree and outdegree in a strongly
connected 2-arc-coloured digraph (any 2-arc-coloured
digraph, resp.) D is at least f(n)
(g(n), resp.), then D has an alternating
simple dicycle. We show that f(n)=Theta(log n) and
g(n)=Theta(log n).
| |||

| ||||

10. | Authors: |
J. Bang-Jensen, G. Gutin & A. Yeo
| ||

Title: | Properly coloured Hamiltonian paths in edge-coloured complete graphs. | |||

Download: | Not available | |||

Abstract: |
We consider edge-coloured complete graphs.
A path or cycle Q is called properly coloured (PC) if
any two adjacent edges of Q differ in colour. Our note
is inspired by the following conjecture by B.
Bollobas and P. Erdos (1976) : if G is an
edge-coloured complete graph on n vertices in
which the maximum monochromatic degree of every
vertex is less than n/2, then
G contains a PC Hamiltonian cycle. We prove
that if an edge-coloured complete graph contains a
PC 2-factor then it has a PC Hamiltonian path. R.
Haggkvist (1996) announced that every
edge-coloured complete graph satisfying Bollobas-Erdos
condition contains a PC 2-factor.
These two results imply that every edge-coloured
complete graph satisfying Bollobas-Erdos
condition has a PC Hamiltonian path.
| |||

| ||||

11. | Authors: |
D. Blokh, G. Gutin & A. Yeo
| ||

Title: | A problem of finding an acceptable variant in some generalized project networks. | |||

Download: | Not available | |||

Abstract: | A project network often has some activities or groups of activities which can be performed at different stages of the project. Then, the problem of finding an optimal time or/and optimal order of such an activity or a group of activities arises. Such problems emerge, in particular, in house-building management when the beginnings of some activities may vary in time or/and order. We consider a mathematical formulation of the problem, show its computational complexity and describe an algorithm for solving the problem. | |||

| ||||

12. | Authors: |
J. Bang-Jensen, J. Huang & A. Yeo
| ||

Title: | Round Graphs. | |||

Download: | Not available | |||

Abstract: |
We introduce a new class of graphs which we
call round graphs. These are those graphs whose
vertices can be circularly enumerated so that
either the neighbourhood or the closed neighbourhood of
each vertex forms an interval in the enumeration.
We show that round graphs have nice structural
properties. 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
[1], 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. We show that round graphs of type I (and
hence of type II) can be recognized in O(n+m)
time (here n denotes the number of vertices and
m the number of edges of the graph in question).
We show how to reduce the problem of
recognizing general round graphs to the problem
of determining whether a weakly triangulated graph
is round (a problem which is still open). We
describe optimal O(n+m) time algorithms for finding a
maximum clique, an 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.
[1] A. Tucker, Matrix characterizations of
circular-arc graphs, Pacific Journal of mathematics
39 (1971) 535-545.
| |||

| ||||

13. | Authors: |
A. Yeo
| ||

Title: | How close to regular must a multipartite tournament be to secure Hamiltonicity? | |||

Download: | Not available | |||

Abstract: |
Let D be a semicomplete multipartite digraph,
with partite sets (called color classes)
V_1,V_2,...,V_c, such that
|V_1| <= |V_2| <= ... <= |V_c|. Define
F(D)=|V(D)|-3|V_c|+1 and G(D)=
(|V(D)|-|V_{c-1}|-2|V_c|+2)/2. We define the
irregularity i(D) of D to be max |d^+(x)-d^-(y)|
over all vertices x and y of D
(possibly x=y). We define the local
irregularity il(D) of D to be max |d^+(x)-d^-(x)| over
all vertices x of D and we define the global
irregularity of D to be ig(D)=
max {d^+(x),d^-(x) : x is a vertex in V(D)}-
min {d^+(y),d^-(y) : y is a vertex in V(D)}
In this paper we show that if
ig(D) <= G(D) or if il(D) <= min{F(D),G(D)} then
D is Hamiltonian. We furthermore show
how this implies a theorem which generalizes two
results by Volkmann and solves a stated problem
and a conjecture from [1]. Our result also
gives support to the conjecture from [1]
that all diregular c-partite tournaments (c >= 4)
are pancyclic. Finally we show that our result
in some sense is best possible, by giving an infinite
class of non-Hamiltonian semicomplete
multipartite digraphs, D, with ig(D)=i(D)=
il(D)=G(D)+1/2 <= F(D)+1.
[1] L. Volkmann, Cycles in multipartite tournaments:
results and problems. Submitted.
| |||

| ||||

14. | Authors: |
J. Huang & A. Yeo
| ||

Title: | Maximal and Minimal Vertex-critical Graphs of Diameter Two. | |||

Download: | Not available | |||

Abstract: |
A graph is vertex-critical (edge-critical)
if deleting any vertex (edge) increases its diameter. A
conjecture of Simon and Murty stated that `every
edge-critical graph of diameter two on u
vertices contains at most (u^2)/4 edges'.
This conjecture has been established for
sufficiently large u. For vertex-critical graphs,
little is known about the number of edges.
Plesnik implicitly asked whether it is also true
that (u^2)/4 is an upper bound for the
number of edges in a vertex-critical graph of diameter
two on u vertices. In this paper, we
construct, for each u>=5 except u=6,
a vertex-critical graph of diameter two on u
vertices with at least
(u^2)/2 - \sqrt{2}u^{3/2} + u c_1
edges, where c_1 is
some constant. We show that each vertex-critical graph contains at most
(u^2)/2 - \sqrt{2} u^{3/2}/2 + u c_2
edges, where c_2 is some
constant. In addition, we also construct, for each
u>=5 except u=6, a vertex-critical graph
of diameter two on u vertices with at most
(5u-12)/2 edges. We show each
vertex-critical graph must contain at least
(5u-29)/2 edges. This second result is
comparable to a result of Murty on the minimum
number of edges possible in an edge-critical graph of
diameter two.
| |||

| ||||

15. | Authors: |
G. Gutin & A. Yeo
| ||

Title: | Note on the path covering number of a semicomplete multipartite tournament. | |||

Download: | Not available | |||

Abstract: |
A digraph D is called is semicomplete c-partite
if its vertex set V(D) can be partitioned into
c sets (partite sets) such that for any two vertices x
and y in different partite sets at least one
arc between x and y is in D and there are no arcs
between vertices in the same partite set.
The path covering number of D is the minimum number
of paths in D that are pairwise vertex
disjoint and cover the vertices of D. Volkmann (1996)
has proved two sufficient conditions on
hamiltonian paths in semicomplete multipartite
digraphs and conjectured two related sufficient
conditions. In this paper, we derive sufficient
conditions for a semicomplete multipartite digraph to
have path covering number at most k and show that
Volkmann's results and conjectures can be
readily obtained from our conditions.
| |||

| ||||

16. | Authors: |
G. Gutin & A. Yeo
| ||

Title: | Small diameter neighbourhood graphs for the traveling salesman problem. | |||

Download: | Not available | |||

Abstract: |
A neighbourhood N(T) of a tour T (in the TSP
with n cities) is polynomially searchable if the
best among tours in N(T) can be found in time
polynomial in n. Using Punnen's neighbourhoods
introduced in 1996, we construct polynomially
searchable neighbourhoods of exponential size
satisfying the following property: for any pair
of tours T_1 and T_5, there exist tours T_2,T_3
and T_4 such that T_i is in the neighbourhood of
T_{i-1} for all i=2,3,4,5. In contrast, for
pyramidal neighbourhoods considered by J. Carlier
and P. Villon (1990), one needs up to \Theta(\log
n) intermediate tours to 'move' from a tour to another one.
| |||

| ||||

17. | Authors: |
J. Bang-Jensen, Y. Guo & A. Yeo
| ||

Title: | A New Sufficient Condition for a Digraph to be Hamiltonian. | |||

Download: | Not available | |||

Abstract: |
In [1] the following extension
of Meyniels theorem was conjectured: If D is a digraph
on n vertices with the property that d(x)+d(y)>=2n-1
for every pair of non-adjacent vertices
x,y with a common out-neighbour or a common
in-neighbour, then D is Hamiltonian. We verify
the conjecture in the special case where we also require that
min{d^+(x)+d^-(y),d^-(x)+d^+(y)}>=n-1 for all
pairs of vertices x,y as above. This
generalizes one of the results in [1].
Furthermore we provide additional support for the
conjecture above by showing that such a digraph
always has a factor (a spanning collection of disjoint
cycles). Finally we show that if D satisfies that
d(x)+d(y)>=5(n-4)/2 for every pair of
non-adjacent vertices x,y with a common out-neighbour
or a common in-neighbour, then D is
Hamiltonian. [1] Bang-Jensen, Gutin and Li, Sufficient Conditions
for a Digraph to be Hamiltonian. J. Graph Theory 22 (1996)
181-187.
| |||

| ||||

18. | Authors: |
J. Bang-Jensen, Y. Guo & A. Yeo
| ||

Title: | Complementary cycles containing prescribed vertices in tournaments. | |||

Download: | Not available | |||

Abstract: |
We prove that if T is a tournament on n>=7 vertices
and x,y are distinct vertices of T with
the property that T remains 2-connected if we delete
the arc between x and y, then there exist
disjoint 3-cycles C_x,C_y such that x is a vertex in V(C_x)
and y is a vertex in V(C_y). This is best possible in
terms of the connectivity assumption. Using this result,
we prove that under the same connectivity
assumption and if n>=8, then T also contains
complementary cycles C'_x,C'_y (i.e.
V(C'_x)\cup V(C'_y)=V(T) and V(C'_x)\cap V(C'_y)=\emptyset)
such that x is a vertex in V(C'_x)
and y is a vertex in V(C'_y) for every choice of distinct
vertices x,y in V(T). Again this is best possible in
terms of the connectivity assumption. It is a trivial
consequence of our result that one can decide in
polynomial time whether a given tournament T
with special vertices x,y contains disjoint cycles
C_x,C_y such that x is a vertex in V(C_x) and
y is a vertex in V(C_y).
This problem is NP-complete for general
digraphs and furthermore there is no degree of
strong connectivity which suffices to guarantee such
cycles in a general digraph.
| |||

| ||||

19. | Authors: |
A. Yeo
| ||

Title: | Large exponential neighbourhoods for the traveling salesman problem. | |||

Download: | Not available | |||

Abstract: |
An exponential neighbourhood for the traveling
salesman problem (TSP) is a set of tours, which
grows exponentially in the input size. An exponential
neighbourhood is polynomial time searchable if
we can find the best among the exponential number of tours
in polynomial time. Deineko and
Woeginger asked if there exists polynomial time
searchable neighbourhoods of size at least (q n)!,
for some q > ½, where n is the number of vertices
in the TSP. In this paper we prove that such
neighbourhoods exist for all q < 1 . In fact we give
a neighbourhood of size at least (c n!)/ k^n , for
any k > 2+ln k > 1 (i.e. k > 3.14619...) and for some
constant c (depending on k), which can
be searched in O(n³) time. Using a slight variation
of the above algorithm we can search
neighbourhoods of size (q n) ! in time O(n^{1+2q}),
for any 0 < q < 1. Deineko and
Woeginger proved (indirectly) that if P\not=NP then no
algorithm for searching a neighbourhood of
size (q n) ! can run faster then O(n^{1+q}).
| |||

| ||||

20. | Authors: |
Y. Guo, M. Tewes, L. Volkmann & A. Yeo
| ||

Title: | Sufficient conditions for semicomplete multipartite digraphs to be Hamiltonian. | |||

Download: | Not available | |||

Abstract: | A semicomplete multipartite digraph is obtained by replacing each edge of a complete multipartite graph by an arc or by a pair of two mutually opposite arcs. Very recently, Yeo proved that every regular semicomplete multipartite digraph is Hamiltonian. With this, Yeo confirmed a conjecture of C.-Q. Zhang. In the first part of this paper, a generalization of regularity is considered. We extend Yeo's result to semicomplete multipartite digraphs that satisfy this condition apart from exactly two exceptions. In the second part, we introduce so called semi-partitioncomplete digraphs and show that this family is Hamiltonian or cycle complementary, when, clearly, the cardinality of each partite set is less than or equal to half the order. | |||

| ||||

21. | Authors: |
A. Yeo
| ||

Title: | Diregular c-partite tournaments are vertex-pancyclic when c>=5. | |||

Download: | Not available | |||

Abstract: |
Volkmann has conjectured that all diregular
c-partite tournaments, with c >= 4, are pancyclic.
In this paper we show that all diregular c-partite tournaments,
with c > 4, are in fact
vertex-pancyclic.
| |||

| ||||

22. | Authors: |
A. Yeo
| ||

Title: | Hamilton cycles, avoiding prescibed arcs, in close to regular tournaments. | |||

Download: | Not available | |||

Abstract: | The local irregularity of a digraph D is defined as il(D)=max{|d^+(x)-d^-(x)| : x \in V(D)}. Let T be a tournament, let P = {V1,V2,...,Vc } be a partition of V(T) such that |V1| >= |V2| >= ... >= |Vc|, and let D be the multipartite tournament obtained by deleting all the arcs with both end points in the same set in P. We prove that if |V(T)| >= max {2il(T)+2|V1|+2|V2|-2, il(T)+3|V1|-1} then D is Hamiltonian. Furthermore if T is regular (i.e. il(T)=0) then we give even better lower bounds for |V(T)|, such that we still can guarantee that D is Hamiltonian. Finally we show that our results are best possible. | |||

| ||||

23. | Authors: |
G. Gutin & A. Yeo
| ||

Title: | Quasi-hamiltonicity: a series of necessary conditions for a digraph to be hamiltonian. | |||

Download: | Not available | |||

Abstract: |
We introduce new necessary conditions, k-quasi-hamiltonicity
(0 <= k <= n-1), for a digraph of order n to be
hamiltonian. Every (k+1)-quasi-hamiltonian digraph is also
k-quasi-hamiltonian; we construct digraphs which are
k-quasi-hamiltonian, but not (k+1)-quasi-hamiltonian.
We design an algorithm that checks
k-quasi-hamiltonicity of a given digraph with $n$
vertices and m arcs in time O(nm^k). We prove that
(n-1)-quasi-hamiltonicity coincides with hamiltonicity
and 1-quasi-hamiltonicity is equivalent to
pseudo-hamiltonicity introduced (for undirected graphs)
by Babel and Woeginger (1997).
| |||

| ||||

24. | Authors: |
A. Yeo
| ||

Title: | A Polynomial Algorithm for finding a cycle covering a given set of vertices in a semicomplete multipartite digraph. | |||

Download: | Not available | |||

Abstract: | The existens of a polynomial algorithm for finding a cycle covering a given set of vertices in a semicomplete multipartite digraph (if it exists) was conjectured by Bang-Jensen, Gutin and Yeo in 1996. The analog problem for semicomplete bipartite digraphs was conjectured by Bang-Jensen and Manoussakis in 1994. We prove the conjecture from 1996 in the affirmative, which also implies the conjecture from 1994. We furthermore give a polynomial algorithm to find a cycle covering a given set of vertices in a semicomplete bipartite digraph, which is the longest of all such cycles, and we conjecture that such an algorithm also exists for semicomplete multipartite digraphs. | |||

| ||||

25. | Authors: |
G. Gutin & A. Yeo
| ||

Title: | TSP heuristics with large domination number. | |||

Download: | Not available | |||

Abstract: |
The domination number, dom(H), of a solution H of a
combinatorial minimization problem (CMP) with
objective function c is the number of solutions
T such that c(T) >= c(H) . The domination number of an
algorithm for CMP is the minimum domination number
of the solutions produced by the algorithm.
This paper is motivated by the following question
of Glover and Punnen: does there exist polynomial
time (in n) algorithm A for the traveling salesman
problem (TSP) on n cities such that dom(A) >=
n!/p(n) for some polynomial p(n). In this paper
we introduce polynomial algorithms with domination
number at least Omega(n!/k^n) for every constant
k>1.5. Even though this result does not
resolve the above question, we believe that the
suggested algorithms or their modifications are of
practical interest as construction heuristics
for the asymmetric TSP. We furthermore improve the
previously best known algorithm, which was obtained
in a paper by Yeo, who gave a polynomial
algorithms with domination number at least
Omega(n!/k^n) for every constant k>3.146.
| |||

| ||||

26. | Authors: |
G. Gutin & A. Yeo
| ||

Title: | Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number. | |||

Download: | Not available | |||

Abstract: |
Glover and Punnen (1997) asked whether there exists a
polynomial time algorithm that always
produces a tour which is not worse than at least
n!/p(n) tours for some polynomial p(n) for every
TSP instance on n cities. They conjectured that,
unless P=NP, the answer to this question is
negative. We prove that the answer to this question is,
in fact, positive. A generalization of the TSP,
the quadratic assignment problem, is also considered
with respect to the analogous question. Probabilistic, graph-theoretical, group-theoretical and number-theoretical methods and results are used. | |||

| ||||

27. | Authors: |
G. Gutin & A. Yeo
| ||

Title: | Kings in semicomplete multipartite digraphs. | |||

Download: | Not available | |||

Abstract: |
A digraph obtained by replacing each edge of a complete
p-partite graph by an arc or a pair of mutually opposite
arcs with the same end vertices is called a semicomplete
p-partite digraph, or just a semicomplete
multipartite digraph. A semicomplete
multipartite digraph with no cycle of length two is a
multipartite tournament.
In a digraph D,
an r-king is a vertex q such that every vertex
in D can be reached from q by a path of length at most r.
Strengthening a theorem by K.M. Koh and B.P. Tan (Discrete Math.
147 (1995) 171-183) on the number of
4-kings in multipartite tournaments,
we characterize semicomplete multipartite digraphs
which have exactly k 4-kings for every k=1,2,3,4,5.
| |||

| ||||

28. | Authors: |
M. Tewes, L. Volkmann & A. Yeo
| ||

Title: |
Almost all almost regular c-partite tournaments with
c >= 5 are vertex pancyclic.
| |||

Download: | Not available | |||

Abstract: |
A tournament is an orientation of a complete graph and a multipartite
or c-partite tournament is an orientation of a complete c-partite
graph. If D is a digraph, then let d+(x)
be the outdgree and d-(x)
the indegree of the vertex x in D.
The minimum (maximum) outdegree and
the minimum (maximum) indegree of D are denoted by delta+
(Delta+) and delta- (Delta-), respectively. In addition,
we define delta=min{delta+,delta-} and
Delta=max{Delta+,Delta-}. A digraph is regular when
delta=Delta and almost regular when Delta-delta<=1.
Very recently,
the third author proved that all regular c-partite tournaments are vertex
pancyclic when c>4, and that all, except possibly a
finite number, regular
4-partite tournaments are vertex pancyclic. Clearly, in a regular multipartite
tournament, each partite set has the same cardinality. As a supplement of
Yeo's result we prove first that an almost regular c-partite tournament
with c>5 is vertex pancyclic, if all partite sets have the same
cardinality. Second, we show that all almost regular c-partite tournaments
are vertex pancyclic when c>7, and third that all, except possibly a
finite number, almost regular c-partite tournaments are vertex pancyclic
when c>4.
| |||

| ||||

29. | Authors: |
G. Gutin & A. Yeo
| ||

Title: | Solution of a conjecture of Volkmann on the number of vertices in longest paths and cycles of strong semicomplete multipartite digraphs. | |||

Download: | Not available | |||

Abstract: |
A digraph obtained by replacing each edge of a complete
multipartite graph by an arc or a pair of mutually opposite
arcs with the same end vertices is called a semicomplete
multipartite digraph.
L. Volkmann conjectured that l<=2c-1, where l
(c, respectively) is
the number of vertices in a longest path (longest cycle) of a strong
semicomplete multipartite digraph. The bound
on l is sharp. We settle this conjecture in affirmative.
| |||

| ||||

30. | Authors: |
R.C. Brewster, P. Hell, S.H. Pantel & A. Yeo
| ||

Title: | Packing paths in digraphs. | |||

Download: | Not available | |||

Abstract: |
Let G be a fixed collection of digraphs.
Given a digraph H, a
G-packing of H is a collection of vertex
disjoint subgraphs of H, each
isomorphic to a member of G. A
G-packing, P, is maximum
if the number of vertices belonging to some member of P is maximum,
over all G-packings. The analogous problem for undirected graphs has
been extensively studied in the literature. We concentrate on the cases when
G is a family of paths. We show G-packing is NP-complete when
(essentially) G is not one of the families
{P_1}, or {P_1,P_2}, where P_1 is an arc and P_2 is a
path of length two.
When G={P_1}, the
G-packing problem is simply the matching
problem. The main focus of our paper is the
case when G={P_1,P_2}.
We present a collection of
augmenting
configurations such that a packing is maximum if and only if it contains no
augmenting configuration. We also present a
min-max condition which yields a concise
certificate for maximality of packings. We
apply these results to obtain a polynomial
time algorithm for finding maximum {P_1,P_2}-packings
in arbitrary
digraphs.
| |||

| ||||

31. | Authors: |
G. Gutin, M. Tewes & A. Yeo
| ||

Title: | Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs. | |||

Download: | Not available | |||

Abstract: |
A digraph obtained by replacing each edge of a complete
multipartite graph by an arc or a pair of mutually opposite
arcs with the same end vertices is called a semicomplete
multipartite digraph.
L. Volkmann (1998) raised the following question:
Let D be a strong semicomplete multipartite digraph with a
longest path of length l. Does there exist a strong spanning oriented
subgraph of D with a longest path of length l?
We provide examples
which show that the answer to this question is negative. We also demonstrate
that every strong semicomplete multipartite digraph D,
which is not bipartite
with a partite set of cardinality one, has a strong spanning oriented
subgraph of D with a longest path of length at least l-2.
This bound is sharp.
| |||

| ||||

32. | Authors: |
F. Glover, G. Gutin, A. Yeo & A. Zverovich
| ||

Title: | Construction heuristics for the asymmetric TSP | |||

Download: | Not available | |||

Abstract: |
Non-Euclidean TSP construction heuristics, and especially
asymmetric TSP construction heuristics, have been neglected in the
literature by comparison with the extensive efforts devoted to
studying Euclidean TSP construction heuristics. This state of
affairs is at odds with the fact that asymmetric models are
relevant to a wider range of applications, and indeed are
uniformly more general that symmetric models. Moreover, common
construction approaches for the Euclidean TSP have been shown to
produce poor quality solutions for non-Euclidean instances.
Motivation for remedying this gap in the study of construction
approaches is increased by the fact that such methods are a great
deal faster than other TSP heuristics, which can be important for
real time problems requiring continuously updated response.
The purpose of this paper is to describe two new construction
heuristics for the asymmetric TSP and a third heuristic based on
combining the other two. Extensive computational experiments are
performed for several different families of TSP instances,
disclosing that our combined heuristic clearly outperforms
well-known TSP construction methods and proves significantly more
robust in obtaining high quality solutions over a wide range of
problems.
| |||

| ||||

33. | Authors: |
J. Bang-Jensen & A. Yeo
| ||

Title: | Strongly connected spanning subgraphs with the minimum number of arcs in semicomplete multipartite digraphs | |||

Download: | Not available | |||

Abstract: |
We consider the problem (MSSS) of
finding the minimum number of arcs
in a spanning strongly connected subgraph of a strongly connected
digraph. This problem is NP-hard for general digraphs
since it generalizes the hamiltonian cycle problem.
We characterize the number
of arcs in a minimum spanning strong subgraph
for digraphs which are either extended
semicomplete or semicomplete bipartite. Our proofs
lead to polynomial algorithms
for finding an optimal subgraph for every digraph from
each of these classes. Our proofs are based on a
number of results (some of which are new and interesting in their own right)
on the structure of cycles and paths in these graphs. We conjecture that the
problem is also polynomial for semicomplete
multipartite digraphs, a superclass
of the two classes considered. Quite recently,
it was shown that the hamiltonian cycle
problem is polynomially solvable for this class [1].
[1] J. Bang-Jensen, G. Gutin, and A. Yeo, A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs. J. Graph Theory 29 (1998) 111-132.
| |||

| ||||

34. | Authors: |
J. Bang-Jensen, J. Huang & A. Yeo
| ||

Title: | Strongly Connected Spanning Subgraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs | |||

Download: | Not available | |||

Abstract: |
We consider the problem (MSSS)
of finding a strongly connected spanning subgraph
with the minimum number of arcs in a strongly
connected digraph. This problem
is NP-hard for general digraphs since it
generalizes the hamiltonian cycle
problem. We show that the problem is polynomially
solvable for quasi-transitive
digraphs. We characterize the minimum number of arcs in such a spanning
subgraph of a quasi-transitive digraph
in terms of the path covering number. Our proofs are based on a
number of results (some of which are new and
interesting in their own right)
on the structure of cycles and paths in quasi-transitive
digraphs and the class of
extended semicomplete digraphs. In particular,
we give a new characterization
of the longest cycle in an extended semicomplete digraph.
Finally, we point out that our proofs imply
the that MSSS problem is solvable
in polynomial time for all digraphs that can be obtained from strong
semicomplete digraphs on at least two vertices
by replacing each vertex with a
digraph whose path covering number can be decided in polynomial time.
| |||

| ||||

35. | Authors: |
G. Gutin & A. Yeo
| ||

Title: | TSP tour domination and Hamilton cycle decomposition of regular digraphs. | |||

Download: | Not available | |||

Abstract: |
F. Glover and A.P. Punnen (1997) asked whether there exists a
polynomial time algorithm that, for every TSP instance on n
cities, produces a tour which is not worse than at least
(n-1)!/p tours for some p being a constant or even polynomial
in n. We show that, if there exists
a constant r > 1 such that
for every sufficiently large k a k-regular digraph of order at
most [rk] can be decomposed into Hamilton cycles and
such a decomposition can be found in time polynomial in n, then
there exists a required TSP algorithm where p is a constant.
This result is of interest as R. Haggkvist demonstrated (not
published yet) that the above Hamilton decomposition exists for
every 1 < r < = 2 and can be found in polynomial time. His very
deep result and our main theorem imply that, in polynomial time,
one can always find a tour, which is not worse than 50% of all
tours.
| |||

| ||||

36. | Authors: |
J. Bang-Jensen, J. Huang,
G. MacGillivray & A. Yeo
| ||

Title: | Domination in convex bipartite and convex-round graphs. | |||

Download: | Not available | |||

Abstract: |
A bipartite graph G=(X,Y;E) is convex
if there exists a linear enumeration
L of the vertices of X such
that the neighbours of each vertex of
Y are consecutive in L. We show that the problem of finding
a minimum dominating set,
or a minimum independent dominating set,
in an n-vertex convex bipartite graph is solvable in time
O(n²). This
improves previous O(n³) algorithms
for these problems. Recently, a new class
of graphs called convex-round
graphs have been introduced by Bang-Jensen,
Huang and Yeo. These are the graphs in which vertices can be circularly
enumerated so that the neighbours of every vertex are consecutive in
the enumeration. As a byproduct, we show that a minimum dominating set, or
a minimum independent dominating set, in a convex-round graph can be
computed in time O(n³). Using a
reduction to circular arc graphs, we show
that a minimum total dominating set in a convex-round graph (with a given
convex-round enumeration) can be computed in time O(n).
| |||

| ||||

37. | Authors: |
G. Gutin & A. Yeo
| ||

Title: | Remarks on hamiltonian digraphs | |||

Download: | Not available | |||

Abstract: |
An oriented graph is an out-tournament if the out-neighbourhood of
every vertex is a tournament. This note is motivated by A. Kemnitz
and B. Greger, Congr. Numer. 130 (1998) 127-131. We show that the
main result of the paper by Kemnitz and Greger is an easy
consequence of the characterization of hamiltonian out-tournaments
by Bang-Jensen, Huang and Prisner, J. Combin. Theory Ser. B 59
(1993) 267-287. We also disprove a conjecture from the paper of
Kemnitz and Greger.
| |||

| ||||

38. | Authors: |
J. Bang-Jensen, J. Huang & A. Yeo
| ||

Title: | Finding small k-arc-strong Spanning Subgraphs in k-arc-strong Tournaments | |||

Download: | Not available | |||

Abstract: |
Given a k-arc-strong tournament T,
we estimate the minimum number
of arcs possible in a k-arc-strong spanning subdigraph of T.
We give a construction which shows that for each k>=2
there are tournaments T
on n vertices such that every k-arc-strong
spanning subdigraph of T
contains at least nk + k(k-1)/2 arcs. In fact, the tournaments
in our construction
have the property that
every spanning subdigraph
with minimum in- and out-degree at least k has
nk + k(k-1)/2 arcs. This is best possible since it can be shown
that every k-arc-strong tournament contains a spanning subdigraph
with minimum in- and out-degree at least k and no more than nk +
k(k-1)/2 arcs. As our main result we prove
that every k-arc-strong tournament
contains a spanning k-arc-strong
subdigraph with no more than nk+280k^2 arcs. We
conjecture that for every k-arc-strong tournament T,
the minimum number of arcs in a k-arc-strong spanning subdigraph of
T is equal to the minimum number of arcs in a spanning subdigraph of
T with the property that every vertex has in- and out-degree at least
k. We also discuss the implications of our results
on related problems and conjectures.
| |||

| ||||

39. | Authors: |
G. Gutin & A. Yeo
| ||

Title: | Orientations of digraphs almost preserving diameter and the one-way and gossip problems | |||

Download: | Not available | |||

Abstract: |
An orientation of a digraph
D is a spanning subdigraph of D
obtained from D by deleting exactly one arc between x and y
for every pair x,y (x not equal to y)
of vertices such that both xy and yx
are in D. In this paper, we consider certain well-known classes
of strong digraphs, each member D of which has an orientation
with diameter not exceeding the diameter of D by more than a
small constant.
| |||

| ||||

40. | Authors: |
G. Gutin, K.M. Koh, E.G. Tay & A. Yeo
| ||

Title: | Almost minimum diameter orientations of semicomplete multipartitite and extended digraphs. | |||

Download: | Not available | |||

Abstract: |
An orientation of a digraph
D is a spanning subdigraph of D
obtained from D by deleting exactly one arc between x and y
for every pair x,y (x not equal to y)
of vertices such that both xy and yx
are in D. Almost minimum diameter orientations of certain semicomplete
multipartite and extended digraphs are considered, several generalizations
of results on orientations of undirected graphs are obtained, some conjectures
are posed.
| |||

| ||||

41. | Authors: |
J. Huang, G. MacGillivray & A. Yeo
| ||

Title: | Pushing Vertices in Digraphs Without Long Induced Cycles. | |||

Download: | Not available | |||

Abstract: |
Given a digraph D and
a subset X of vertices of D, pushing
X in D means reversing the orientation of all arcs with exactly
one end in X.
It is known that the problem of deciding whether
a given digraph can be made acyclic using the push operation is NP-complete
for general digraphs, and polynomial time solvable for multipartite tournaments.
Here, we continue the study of
deciding whether a digraph is acyclically pushable,
focussing on special classes
of well-structured digraphs.
It is proved that the problem remains NP-complete
even when restricted to the class of bipartite digraphs
(i.e., oriented bipartite graphs) and
we characterize, in terms of two forbidden subdigraphs,
the chordal digraphs which can be made
acyclic using the push operation.
An infinite family of chordal
bipartite digraphs which are not acyclically pushable
is described.
A polynomial algorithm, based on 2-SAT,
for solving the problem for a subclass of the chordal bipartite digraphs
is given.
Finally, a characterization in terms of a finite number of
forbidden subdigraphs, of the acyclically pushable
bipartite permutation digraphs is given.
| |||

| ||||

42. | Authors: |
G. Gutin, K. M. Koh, E. G. Tay & A. Yeo
| ||

Title: | On the number of quasi-kernels in digraphs. | |||

Download: | Not available | |||

Abstract: |
A vertex set X of a
digraph D=(V,A) is a kernel if X
is independent (i.e., all pairs of distinct vertices of X are
non-adjacent) and for every v\in V-X there exists x\in X such
that vx\in A. A vertex set X
of a digraph D=(V,A) is a {\em
quasi-kernel} if X is independent and for every v\in V-X
there exist w\in V-X, x\in X such that either vx\in A or
vw,wx\in A. In 1994, Chvatal and Lovasz proved that every
digraph has a quasi-kernel. In 1996, Jacob and Meyniel proved
that, if a digraph D has no kernel, then D contains at least
three quasi-kernels. We characterize digraphs with exactly one
and two quasi-kernels, and, thus, provide necessary and
sufficient conditions for a digraph to have at least three
quasi-kernels. In particular, we prove that every strong digraph
of order at least three, which is not a 4-cycle, has at least
three quasi-kernels. We conjecture that every digraph with no sink
has a pair of disjoint quasi-kernels and provide some support to
this conjecture.
| |||

| ||||

43. | Authors: |
K. M. Hangos, Z. Tuza & A. Yeo
| ||

Title: | Matchings and P_3-partitions motivated by process control. | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

44. | Authors: |
G. Gutin, A. Yeo & A. Zverovich
| ||

Title: | Traveling salesman should not be greedy: domination analysis of ATSP greedy-type heuristics. | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

45. | Authors: |
J. Bang-Jensen & A. Yeo
| ||

Title: |
Decomposing k-arc-strong tournaments into
strong spanning subdigraphs
| |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

46. | Authors: | G. Gutin & A. Yeo
| ||

Title: | Upper Bounds on ATSP Neighborhood Size | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

47. | Authors: | G. Gutin & A. Yeo
| ||

Title: | Anti-matroids | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

48. | Authors: | G. Gutin & A. Yeo
| ||

Title: | Assignment Problem based algorithms are impractical for the Generalized TSP | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

49. | Authors: | J. Bang-Jensen & A. Yeo
| ||

Title: | How to obtain $k$-arc-strong tournament, by reversing arcs | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

50. | Authors: | J. Bang-Jensen, S. Thomasse & A. Yeo
| ||

Title: | Small degree out-branching | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

51. | Authors: | J. Bang-Jensen, G. Gutin & A. Yeo
| ||

Title: | Finding cheapest cycles in vertex-weighted quasi-transitive digraphs and extended semicomplete digraphs. | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

52. | Authors: | D. Ben-Arieh, G. Gutin, M. Penn, A. Yeo
& A. Zverovitch
| ||

Title: | Process Planning for Rotational Parts and the Generalized Travelling Salesman Problem. | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

53. | Authors: | J. Bang-Jensen, G. Gutin & A. Yeo
| ||

Title: | Steiner type problems for digraphs that are locally semicomplete or extended semicomplete. | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

54. | Authors: | L. Volkmann & A. Yeo
| ||

Title: | Hamiltonian paths containing a given path or collection of arcs, in close to regular multipartite tournaments | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

55. | Authors: | D. Ben-Arieh, G. Gutin, M. Penn, A. Yeo & A. Zverovitch
| ||

Title: | Transformations of Generalized ATSP into ATSP: experimental and theoretical study | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

56. | Authors: | G. Gutin, A. Vainshtein & A. Yeo
| ||

Title: | When greedy-type algorithms fail | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

57. | Authors: | S. Thomasse & A. Yeo
| ||

Title: | Total domination of graphs and small transversals of hypergraphs | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

58. | Authors: | G. Gutin, A. Vainshtein & A. Yeo
| ||

Title: | Domination Analysis of Combinatorial Optimization Problems | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

59. | Authors: | J. Bang-Jensen, G. Gutin & A. Yeo
| ||

Title: | When the greedy algorithm fails | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

60. | Authors: | G. Gutin, T. Jensen & A. Yeo
| ||

Title: | Asymptotic domination scheme for minimum multiprocessor scheduling | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

61. | Authors: | A. Yeo
| ||

Title: | The number of pancyclic arcs in a k-strong tournament. | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

62. | Authors: | G. Gutin, T. Kloks, C.M. Lee & A. Yeo
| ||

Title: | Kernels in planar digraphs | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

63. | Authors: | G. Gutin & A. Yeo
| ||

Title: | Introduction to Domination Analysis | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

64. | Authors: | G. Gutin, T. Jensen & A. Yeo
| ||

Title: | Batched Bin Packing | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

65. | Authors: | G. Gutin, A. Rafiey & A. Yeo
| ||

Title: | On n-partite tournaments with unique n-cycle | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

66. | Authors: | G. Gutin, A. Rafiey, M. Tso & A. Yeo
| ||

Title: | Level of Repair Analysis and Minimal Cost Homomorphisms of Graphs | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

67. | Authors: | G. Gutin, T. Jensen & A. Yeo
| ||

Title: | Optimal on-line bin packing with two item sizes | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

68. | Authors: | G. Gutin, A. Rafiey, S. Severini & A. Yeo
| ||

Title: | Conjecture on Hamilton Cycles in Digraphs of Unitary Matrices | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

69. | Authors: | G. Gutin, N. Jones, A. Rafiey, S. Severini & A. Yeo
| ||

Title: | Mediated Digraphs and Quantum Nonlocality | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

70. | Authors: | P. Charbit, S. Thomasse & A. Yeo
| ||

Title: | The minimum feedback arc set problem is NP-hard for tournaments | |||

Download: | ps-file | |||

Abstract: |
| |||

| ||||

71. | Authors: | A. Yeo
| ||

Title: | Relationships between total domination, order, size and maximum degree of graphs | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

72. | Authors: | G. Gutin, A. Rafiey & A. Yeo
| ||

Title: | Minimum Cost and List Homomorphisms to Semicomplete Digraphs | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

73. | Authors: | M. Henning, L. Kang, E. Shan & A. Yeo
| ||

Title: | On matching and total domination in graphs | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

74. | Authors: | M. Henning & A. Yeo
| ||

Title: | Hypergraphs with large transversal number \\ and with edge sizes at least three | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

75. | Authors: | A. Yeo
| ||

Title: | Paths and cycles containing given arcs, in close to regular multipartite tournaments. | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

76. | Authors: | G. Gutin, A. Rafiey & A. Yeo
| ||

Title: | Minimum Cost Homomorphisms to Semicomplete Multipartite Digraphs | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

77. | Authors: | J. Bang-Jensen, M. H. Nielsen & A. Yeo
| ||

Title: | Longest path-partitions in generalizations of tournaments | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

78. | Authors: | M. Henning & A. Yeo
| ||

Title: | Tight lower bounds on the size of a matching in a regular graph | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

79. | Authors: | G. Gutin, A. Rafiey, S. Szeider & A. Yeo
| ||

Title: | The Linear Arrangement Problem Parameterized Above Guaranteed Value | |||

Download: | Not available | |||

Abstract: |
| |||

| ||||

Anders Yeo <anders@cs.rhul.ac.uk>