An immune algorithm with stochastic aging and kullback entropy for the chromatic number problem

We present a new Immune Algorithm, IMMALG, that incorporates a Stochastic Aging operator and a simple local search procedure to improve the overall performances in tackling the chromatic number problem (CNP) instances. We characterize the algorithm and set its parameters in terms of Kullback Entropy. Experiments will show that the IA we propose is very competitive with the state-of-art evolutionary algorithms.     

An upper bound on the total restrained domination number of a tree

Let G=(V,E) be a graph. A set of vertices S?V is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of $V-\nobreak S$ is adjacent to a vertex in V?S. The total restrained domination number of G, denoted by γ _tr (G), is the smallest cardinality of a total restrained dominating set of G. A support vertex of a graph is a vertex of degree at least two which is adjacent to a leaf. We show that $\gamma_{\mathit{tr}}(T)\leq\lfloor\frac{n+2s+\ell-1}{2}\rfloor$ where T is a tree of order n≥3, and s and ? are, respectively, the number of support vertices and leaves of T. We also constructively characterize the trees attaining the aforementioned bound.     

An approximation algorithm for maximum internal spanning tree

Given a graph G, the maximum internal spanning tree problem (MIST for short) asks for computing a spanning tree T of G such that the number of internal vertices in T is maximized. MIST has possible applications in the design of cost-efficient communication networks and water supply networks and hence has been extensively studied in the literature. MIST is NP-hard and hence a number of polynomial-time approximation algorithms have been designed for MIST in the literature. The previously best polynomial-time approximation algorithm for MIST achieves a ratio of \(\frac{3}{4}\). In this paper, we first design a simpler algorithm that achieves the same ratio and the same time complexity as the previous best. We then refine the algorithm into a new approximation algorithm that achieves a better ratio (namely, \(\frac{13}{17}\)) with the same time complexity. Our new algorithm explores much deeper structure of the problem than the previous best. The discovered structure may be used to design even better approximation or parameterized algorithms for the problem in the future.     

A combinatorial proof for the circular chromatic number of Kneser graphs

Chen (J Combin Theory A 118(3):1062–1071, 2011) confirmed the Johnson–Holroyd–Stahl conjecture that the circular chromatic number of a Kneser graph is equal to its chromatic number. A shorter proof of this result was given by Chang et al. (J Combin Theory A 120:159–163, 2013). Both proofs were based on Fan’s lemma (Ann Math 56:431–437, 1952) in algebraic topology. In this article we give a further simplified proof of this result. Moreover, by specializing a constructive proof of Fan’s lemma by Prescott and Su (J Combin Theory A 111:257–265, 2005), our proof is self-contained and combinatorial.     

A note on the annihilation number and 2-domination number of a tree

In 2014, Desormeaux et al. (Discrete Math 319:15–23, 2014) proved a relationship between the annihilation number and 2-domination number of a tree. In this note, we provide a family of bounds for the 2-domination number of a tree based on the amount of vertices of small degree. This family of bounds extends current bounds on the 2-domination number of a tree, and provides an alternative proof for the relationship between the annihilation number and the 2-domination number of a tree that was shown by Desormeaux et al.     

Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree

Gyárfás conjectured that for a given forest F, there exists an integer function f(F, x) such that \(\chi (G)\le f(F,\omega (G))\) for each F-free graph G, where \(\omega (G)\) is the clique number of G. The broom B(m, n) is the tree of order \(m+n\) obtained from identifying a vertex of degree 1 of the path \(P_m\) with the center of the star \(K_{1,n}\). In this note, we prove that every connected, triangle-free and B(m, n)-free graph is \((m+n-2)\)-colorable as an extension of a result of Randerath and Schiermeyer and a result of Gyárfás, Szemeredi and Tuza. In addition, it is also shown that every connected, triangle-free, \(C_4\)-free and T-free graph is \((p-2)\)-colorable, where T is a tree of order \(p\ge 4\) and \(T\not \cong K_{1,3}\).     

Star list chromatic number of planar subcubic graphs

A proper coloring of the vertices of a graph G is called a star-coloring if the union of every two color classes induces a star forest. The graph G is L-star-colorable if for a given list assignment L there is a star-coloring π such that π(v)∈L(v). If G is L-star-colorable for any list assignment L with |L(v)|≥k for all v∈V(G), then G is called k-star-choosable. The star list chromatic number of G, denoted by $\chi_{s}^{l}(G)$ , is the smallest integer k such that G is k-star-choosable. In this paper, we prove that every planar subcubic graph is 6-star-choosable.     

Note on incidence chromatic number of subquartic graphs

An incidence in a graph G is a pair (v, e) where v is a vertex of G and e is an edge of G incident to v. Two incidences (v, e) and (u, f) are adjacent if at least one of the following holds: \((a) v = u, (b) e = f\), or \((c) vu \in \{e,f\}\). An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. In this note we prove that every subquartic graph admits an incidence coloring with at most seven colors.     

An improved algorithm for tree edit distance with applications for RNA secondary structure comparison

An ordered labeled tree is a tree in which the nodes are labeled and the left-to-right order among siblings is relevant. The edit distance between two ordered labeled trees is the minimum cost of transforming one tree into the other through a sequence of edit operations. We present techniques for speeding up the tree edit distance computation which are applicable to a family of algorithms based on closely related recursion strategies. These techniques aim to reduce repetitious steps in the original algorithms by exploring certain structural features in the tree. When these features exist in a large portion of the tree, the speedup due to our techniques would be significant. Viable examples for application include RNA secondary structure comparison and structured text comparison.     

On the odd girth and the circular chromatic number of generalized Petersen graphs

A class \(\mathcal{G}\) of simple graphs is said to be girth-closed (odd-girth-closed) if for any positive integer g there exists a graph \(\mathrm {G} \in \mathcal{G}\) such that the girth (odd-girth) of \(\mathrm {G}\) is \(\ge g\). A girth-closed (odd-girth-closed) class \(\mathcal{G}\) of graphs is said to be pentagonal (odd-pentagonal) if there exists a positive integer \(g^*\) depending on \(\mathcal{G}\) such that any graph \(\mathrm {G} \in \mathcal{G}\) whose girth (odd-girth) is greater than \(g^*\) admits a homomorphism to the five cycle (i.e. is \(\mathrm {C}_{_{5}}\)-colourable). Although, the question “Is the class of simple 3-regular graphs pentagonal?” proposed by Ne?et?il (Taiwan J Math 3:381–423, 1999) is still a central open problem, Gebleh (Theorems and computations in circular colourings of graphs, 2007) has shown that there exists an odd-girth-closed subclass of simple 3-regular graphs which is not odd-pentagonal. In this article, motivated by the conjecture that the class of generalized Petersen graphs is odd-pentagonal, we show that finding the odd girth of generalized Petersen graphs can be transformed to an integer programming problem, and using the combinatorial and number theoretic properties of this problem, we explicitly compute the odd girth of such graphs, showing that the class is odd-girth-closed. Also, we obtain upper and lower bounds for the circular chromatic number of these graphs, and as a consequence, we show that the subclass containing generalized Petersen graphs \(\mathrm {Pet}(n,k)\) for which either k is even, n is odd and \(n\mathop {\equiv }\limits ^{k-1}\pm 2\) or both n and k are odd and \(n\ge 5k\) is odd-pentagonal. This in particular shows the existence of nontrivial odd-pentagonal subclasses of 3-regular simple graphs.     

An algorithm for finding a representation of a subtree distance

Generalizing the concept of tree metric, Hirai (Ann Combinatorics 10:111–128, 2006) introduced the concept of subtree distance. A nonnegative-valued mapping \(d:X\times X \rightarrow \mathbb {R}_+\) is called a subtree distance if there exist a weighted tree T and a family \(\{T_x\mid x \in X\}\) of subtrees of T indexed by the elements in X such that \(d(x,y)=d_T(T_x,T_y)\), where \(d_T(T_x,T_y)\ge 0\) is the distance between \(T_x\) and \(T_y\) in T. Hirai (2006) provided a characterization of subtree distances that corresponds to Buneman’s (J Comb Theory, Series B 17:48–50, 1974) four-point condition for tree metrics. Using this characterization, we can decide whether or not a given mapping is a subtree distance in O\((n^4)\) time. In this paper, we show an O\((n^3)\) time algorithm that finds a representation of a given subtree distance. This results in an O\((n^3)\) time algorithm for deciding whether a given mapping is a subtree distance.     

An algorithm for scheduling a chemical processing tank line

This paper presents a model and an algorithm for scheduling a system in which parts are processed through a chemical processing tank line. The tank line is equipped with one piece of material-handling equipment. The tank line is modelled with a mixed integer linear programming formulation. The formulation is then used to develop a heuristic algorithm. The algorithm generates the optimum or near optimum schedule and is easy to apply in practice where no defectives are permitted.     

An algorithm to dynamically adjust the number of Kanbans in stochastic processing times and variable demand environment

In a real-life environment, the just-in-time JIT system is subjected to various types of uncertainties such as stochastic processing times and variable demand. Since, JIT was only meant to operate in a deterministic environment, its performance is seriously affected by variations in processing times and demand. In this paper, a newly developed Kanban system is presented which uses an algorithm to dynamically and systematically manipulate the number of Kanbans in order to offset the blocking and starvation caused by the said uncertainties during a production cycle. The new system is termed a flexible Kanban system FKS . The steps of the algorithm are detailed and the effectiveness of FKS is demonstrated using an example model. For the example model, the solution procedure, results and a discussion are presented.     

An approximation algorithm for k-center problem on a convex polygon

This paper studies the constrained version of the k-center location problem. Given a convex polygonal region, every point in the region originates a service demand. Our objective is to place k facilities lying on the region’s boundary, such that every point in that region receives service from its closest facility and the maximum service distance is minimized. This problem is equivalent to covering the polygon by k circles with centers on its boundary which have the smallest possible radius. We present an 1.8841-approximation polynomial time algorithm for this problem.     

An approximation algorithm for a general class of parametric optimization problems

Journal of Combinatorial Optimization - In a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is...