Online scheduling of equal-length jobs with incompatible families on multiple batch machines to maximize the weighted number of early jobs

This paper studies the online scheduling of equal-length jobs with incompatible families on multiple batch machines which can process the jobs from a common family in batches, where each batch has a capacity b with $b=\infty$ in the unbounded batching and $b<\infty$ in the bounded batching. Each job J has an equal-length integral processing time $p>0$, an integral release time $r(J)?0$, an integral deadline $d(J)?0$ and a real weight $w(J)?0$. The goal is to determine a preemptive schedule with restart which maximizes the weighted number of early jobs. When $p=1$, we show that a simple greedy online algorithm has a competitive ratio 2, and establish the lower bound $2?1/b$. This means that the greedy algorithm is of the best possible for $b=\infty$. When p is any positive integer, we provide an online algorithm of competitive ratio $3+2\sqrt{2}$ for both $b=\infty$ and $b<\infty$. This is the first online algorithm for the problem with a constant competitive ratio.     

A shortest cycle for each vertex of a graph

We present an algorithm that finds, for each vertex of an undirected graph, a shortest cycle containing it. While for directed graphs this problem reduces to the All-Pairs Shortest Paths problem, this is not known to be the case for undirected graphs.We present a truly sub-cubic randomized algorithm for the undirected case. Given an undirected graph with n vertices and integer weights in $1,\dots ,M$, it runs in $\stackrel{?}{O}(\sqrt{M}{n}^{(\omega +3)/2})$ time where $\omega <2.376$ is the exponent of matrix multiplication. As a by-product, our algorithm can be used to determine which vertices lie on cycles of length at most t in $\stackrel{?}{O}(M{n}^{\omega }t)$ time. For the case of bounded real edge weights, a variant of our algorithm solves the problem up to an additive error of ? in $\stackrel{?}{O}(n^{(\omega +6)/3})$ time.     

Faster gossiping on butterfly networks

Gossiping has been considered intensively for butterflies and “simple” butterflies (which have no wrap-around connections). In the “telephone” communication model, for a butterfly of order k, the best previous gossiping algorithms require $2\frac{1}{2}k$ and $3k$ communication rounds, respectively. By new asymptotic methods we break through these bounds. We show that gossiping on a class of “column-based” networks, which also contains the cube-connected cycles, can be reduced to the simpler problem of “row-gossiping”. Row-gossiping in turn is reduced to “coherent row-broadcasting”. This latter problem is sufficiently simple to be solved by a sophisticated computer program for butterflies with up to $15\times 2^{15}$ nodes. Out of the produced solutions a pattern is distilled, which can be used to perform gossiping on butterflies and simple butterflies of order k in $2\frac{1}{4}k+\mathrm{o}(k)$ and $2\frac{1}{2}k+\mathrm{o}(k)$ rounds, respectively, for any k, considerably reducing the gap with the lower bounds. The new upper bounds also hold for gossiping in the weaker “telegraph” model.     

A proof of the extended Duval's conjecture

We give a short and elementary proof of the following stronger version of Duval's conjecture: let u be an unbordered word, and $v$ a word of length $\left|u\right|-1$, such that $v$ is not a prefix of u. Then u$v$ contains an unbordered word of length at least $\left|u\right|+1$.     

Pancyclic out-arcs of a vertex in oriented graphs

Let D be an oriented graph with $n?9$ vertices and minimum degree at least $n?2$, such that, for any two vertices x and y, either x dominates y or $d_D^{+}(x)+d_D^{?}(y)?n?3$. Song (1994) [5] proved that D is pancyclic. Bang-Jensen and Guo (1999) [2] proved, based on Song?s result, that D is vertex pancyclic. In this article, we give a sufficient condition for D to contain a vertex whose out-arcs are pancyclic in D, when $n?14$.     

Jacobi elliptic wave solutions for two variable coefficients cylindrical Korteweg–de Vries models arising in dusty plasmas by using direct reduction method

In this paper, generalized models for both ($2+1$)-dimensional cylindrical modified Korteweg–de Vries (cmKdV) equation with variable coefficients and ($3+1$)-dimensional variable coefficients cylindrical Korteweg–de Vries (cKdV) equation are studied by direct reduction method. A direct reduction to nonlinear ordinary differential equations in the form of Riccati equations obtained for the considered equations under some integrability conditions. The search for solutions for the reduced Riccati equations has yielded many Jacobi elliptic wave solutions, solitary and periodic wave solutions for both ($2+1$)-dimensional cmKdV and ($3+1$)-dimensional cKdV equations. Physical application for the obtained solutions as dust ion acoustic waves in plasma physics is given     

Edge-fault-tolerant pancyclicity and bipancyclicity of Cartesian product graphs with faulty edges

Let r≥ 4 be an even integer. Graph G is r-bipancyclic if it contains a cycle of every even length from r to $2\lfloor \frac{n(G)}{2}\rfloor$, where $n(G)$ is the number of vertices in G. A graph G is r-pancyclic if it contains a cycle of every length from r to $n(G)$, where $r\ge 3$. A graph is k-edge-fault Hamiltonian if, after deleting arbitrary k edges from the graph, the resulting graph remains Hamiltonian. The terms k-edge-fault r-bipancyclic and k-edge-fault r-pancyclic can be defined similarly. Given two graphs G and H, where $n(G)$, $n(H)\ge$ 9, let $k_1$, $k_2\ge 5$ be the minimum degrees of G and H, respectively. This study determined the edge-fault r-bipancyclic and edge-fault r-pancyclic of Cartesian product graph $G\times H$ with some conditions. These results were then used to evaluate the edge-fault pancyclicity (bipancyclicity) of ${\mathit{NQ}}_{m_r,\dots ,m_1}$ and ${\mathit{GQ}}_{m_r,\dots ,m_1}$.     

Lattice Boltzmann method based on Dual-MRT model for three-dimensional natural convection and entropy generation in CuO–water nanofluid filled cuboid enclosure included with discrete active walls

In the present study, the three-dimensional natural convection and entropy generation in a cuboid enclosure included with various discrete active walls is analyzed using lattice Boltzmann method. The enclosure is filled with CuO–water nanofluid. To predict thermo-physical properties, dynamic viscosity and thermal conductivity, of CuO–water nanofluid, the KKL model is applied to consider the effect of Brownian motion on nanofluid properties. In lattice Boltzmann simulation, two different MRT models are used to solve the problem. The D3Q7-MRT model is used to solve the temperature filed, and the D3Q19 is employed to solve the fluid flow of natural convection within the enclosure. The influences of different Rayleigh numbers $\left(10^3<Ra<10^6\right)$ and solid volume fractions $\left(0<\phi <0.04\right)$ and four different arrangements of discrete active walls on the fluid flow, heat transfer, total entropy generation, local heat transfer irreversibility and local fluid friction irreversibility are presented comprehensively.