Details of A. Yeo's publications


Note that these papers may be copyright protected!
Click here for an overview, including where they are published.


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 k-strong and k-cyclic Digraphs, Discrete Mathematics 162 (1996) 1-11
    [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>