Mod (2p+1)-orientations in line graphs

Jaeger in 1984 conjectured that every $(4p)$-edge-connected graph has a mod $(2p+1)$-orientation. It has also been conjectured that every $(4p+1)$-edge-connected graph is mod $(2p+1)$-contractible. In [Z.-H. Chen, H.-J. Lai, H. Lai, Nowhere zero flows in line graphs, Discrete Math. 230 (2001) 133–141], it has been proved that if G has a nowhere-zero 3-flow and the minimum degree of G is at least 4, then $L(G)$ also has a nowhere-zero 3-flow. In this paper, we prove that the above conjectures on line graphs would imply the truth of the conjectures in general, and we also prove that if G has a mod $(2p+1)$-orientation and $\delta (G)?4p$, then $L(G)$ also has a mod $(2p+1)$-orientation, which extends a result in Chen et al. (2001) [2].     

A simplified gravitational model to analyze texture roughness

Textures are among the most important visual attributes in image analysis. This paper presents a novel method to analyze texture, based on representing states of a simplified gravitational collapse from an image and extracting information from each state using fractal dimension. In this approach, an image evolves in times $t=\{1,2,\dots ,20\}$, each time representing a state, which is explored by the Bouligand–Minkowski method using radius $r=\{3,4,\dots ,8\}$. These parameters allow to create a set of feature vectors, which were extracted from Brodatz's textures and leaf textures. The best classification results were 98.75% and 86.67% of success rate (percentage of samples correctly classified) for these two databases, respectively. These results prove that the proposed approach opens a promising source of research in texture analysis to be explored.     

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.