Search

Abstract: The concept of table algebra in the title is a real nonsingular generalized table algebra in the sense of [Z. Arad, E. Fisman, M. Muzychuk, Generalized table algebras, Israel J. Math. 114 (1999) 29–60]. In this paper we first give some definitions and facts about table algebras. It is well known that every association scheme gives a Hecke-algebra which is a table algebra too. This leads to the natural question which properties of association schemes stay valid for table algebras. For instance, we prove the Second Isomorphism Theorem and the Jordan–Holder''s theorem for standard table algebras. [Copyright &y& Elsevier]

Abstract: The 2-factor index of a graph G, denoted by is the smallest integer m such that the m-iterated line graph of G contains a 2-factor. In this paper, we provide a formula for , and point out that there is a polynomial time algorithm to determine . [Copyright &y& Elsevier]

Abstract: We consider a variant of the classical two median facility location problem on a tree in which vertices are allowed to have positive or negative weights. This problem was proposed by Burkard et al. in 2000 (R.E. Burkard, E. Çela, H. Dollani, 2-medians in trees with pos/neg-weights, Discrete Appl. Math. 105 (2000) 51–71). who looked at two objectives, finding the total minimum weighted distance (MWD) and the total weighted minimum distance (WMD). Their approach finds an optimal solution in time and time, respectively, with better performance for special trees such as paths and stars. We propose here an algorithm for the MWD problem on trees of arbitrary shape. We also briefly discuss the WMD case and argue that it can be solved in time. However, a systematic exposition of the later case cannot be contained in this paper. [Copyright &y& Elsevier]

Abstract: Kumar and Madhavan [Minimal vertex separators of chordal graphs, Discrete Appl. Math. 89 (1998) 155–168] gave a linear time algorithm to list all the minimal separators of a chordal graph. In this paper we give another linear time algorithm for the same purpose. While the algorithm of Kumar and Madhavan requires that a specific type of PEO, namely the MCS PEO is computed first, our algorithm works with any PEO. This is interesting when we consider the fact that there are other popular methods such as Lex BFS to compute a PEO for a given chordal graph. [Copyright &y& Elsevier]

Abstract: Let be the collection of sets T such that the greedy algorithm obtains the optimal T-span of for all , the collection of sets T such that is true for all graphs G. Many families in or have been discovered. We know that r-initial set and k multiple of s set are all in . Liu (T-colorings of graphs, Discrete Math. 10 (1992), 203–212) extended k multiple of s set by union with another set . In this paper, we continue to study the T-set in and , extending some T-sets by the similar way. [Copyright &y& Elsevier]

Covering arrays are combinatorial structures which extend the notion of orthogonal arrays and have applications in the realm of software testing. In this paper we raise several new problems motivated by these applications and discuss algorithms for their solution. [Copyright &y& Elsevier]

We give a general result on the average-case performance of certain greedy algorithms. These are derived from algorithms in which the possible operations performed at each step are prioritised. This type of prioritisation has occurred in previously studied heuristics for finding large subgraphs with special properties in random regular graphs, such as maximum independent sets and minimum dominating sets. The approach in this paper eliminates some of the complications caused by prioritisation. The main results apply in general to random graphs with a given degree sequence. [Copyright &y& Elsevier]