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].     

Finding large 3-free sets I: The small n case

There has been much work on the following question: given n, how large can a subset of $\{1,\dots ,n\}$ be that has no arithmetic progressions of length 3. We call such sets 3-free. Most of the work has been asymptotic. In this paper we sketch applications of large 3-free sets, present techniques to find large 3-free sets of $\{1,\dots ,n\}$ for $n?250$, and give empirical results obtained by coding up those techniques. In the sequel we survey the known techniques for finding large 3-free sets of $\{1,\dots ,n\}$ for large n, discuss variants of them, and give empirical results obtained by coding up those techniques and variants.     

On the bounds of feedback numbers of (n,k)-star graphs

The feedback number of a graph G is the minimum number of vertices whose removal from G results in an acyclic subgraph. We use $f(n,k)$ to denote the feedback number of the $(n,k)$-star graph $S_{n,k}$ and $p(n,k)$ the number of k-permutations of an n-element set. This paper proves that$p(n,k)?2(k?1)!\left(\begin{array}{c}\hfill n\hfill \\ \hfill k?1\hfill \end{array}\right)?f(n,k)?p(n,k)?2(k?1)!\sum _{i=1}^{\theta }\left(\begin{array}{c}\hfill n?2i+1\hfill \\ \hfill k?i\hfill \end{array}\right),$ where $\theta =\min \{k?1,n?k+1\}$.     

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.     

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.     

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.