基于微分算子的边缘检测法在基因芯片图像识别中的应用

一种基于梯度算子和拉普拉斯算子检测医学基因芯片荧光数字图像边缘的方法．数字图像经过图像增强等预处理以后，突出了我们感兴趣的数字图像特征，根据数字图像灰度变化的趋势，用灰度变化的一阶导数(梯度算子)检测图象中的边缘区域；用灰度变化的二阶导数确定图像边缘的中心位置．最后根据某些预定的准则把满足这些准则的象素组成一条边缘．     

A conjecture of Borodin and a coloring of Grünbaum

In 1976, Borodin conjectured that every planar graph has a 5‐coloring such that the union of every k color classes with 1 ≤ k ≤ 4 induces a (k—1)‐degenerate graph. We prove the existence of such a coloring using 18 colors. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:139–147, 2008     

On the asymmetric representatives formulation for the vertex coloring problem

We consider the vertex coloring problem, which can be stated as the problem of minimizing the number of labels that can be assigned to the vertices of a graph G such that each vertex receives at least one label and the endpoints of every edge are assigned different labels. In this work, the 0-1 integer programming formulation based on representative vertices is revisited to remove symmetry. The previous polyhedral study related to the original formulation is adapted and generalized. New versions of facets derived from substructures of G are presented, including cliques, odd holes and anti-holes and wheels. In addition, a new class of facets is derived from independent sets of G. Finally, a comparison with the independent sets formulation is provided.     

Solving some NP-complete problems using split decomposition

We show how to use the split decomposition to solve some NP-hard optimization problems on graphs. We give algorithms for clique problem and domination-type problems. Our main result is an algorithm to compute a coloration of a graph using its split decomposition. Finally we show that the clique-width of a graph is bounded if and only if the clique-width of each representative graph in its split decomposition is bounded.     

NUMERICAL LOCALIZATION OF ELECTROMAGNETIC IMPERFECTIONS FROM A PERTURBATION FORMULA IN THREE DIMENSIONS

This work deals with the numerical localization of small electromagnetic inhomogeneities. The underlying inverse problem considers, in a three-dimensional bounded domain, the time-harmonic Maxwell equations formulated in electric field. Typically, the domain contains a finite number of unknown inhomogeneities of small volume and the inverse problem attempts to localize these inhomogeneities from a finite number of boundary measurements. Our localization approach is based on a recent framework that uses an asymptotic expansion for the perturbations in the tangential boundary trace of the curl of the electric field. We present three numerical localization procedures resulting from the combination of this asymptotic expansion with each of the following inversion algorithms： the Current Projection method, the MUltiple Signal Classification （MUSIC） algorithm, and an Inverse Fourier method. We perform a numerical study of the asymptotic expansion and compare the numerical results obtained from the three localization procedures in different settings.     

Batch processing with interval graph compatibilities between tasks

We analyze batch-scheduling problems that arise in connection with certain industrial applications. The models concern processing on a single max-batch machine with the additional feature that the tasks of the same batch have to be compatible. Compatibility is a symmetric binary relation—the compatible pairs are described with an undirected “compatibility graph”, which is often an interval graph according to some natural practical conditions that we present. We consider several models with varying batch capacities, processing times or compatibility graphs. We summarize known results, and present a min-max formula and polynomial time algorithms.     

Distinguishing colorings of Cartesian products of complete graphs

We determine the values of s and t for which there is a coloring of the edges of the complete bipartite graph K_s,t which admits only the identity automorphism. In particular, this allows us to determine the distinguishing number of the Cartesian product of complete graphs.     

Game coloring the Cartesian product of graphs

This article proves the following result: Let G and G′ be graphs of orders n and n′, respectively. Let G^* be obtained from G by adding to each vertex a set of n′ degree 1 neighbors. If G^* has game coloring number m and G′ has acyclic chromatic number k, then the Cartesian product G□G′ has game chromatic number at most k(k + m ? 1). As a consequence, the Cartesian product of two forests has game chromatic number at most 10, and the Cartesian product of two planar graphs has game chromatic number at most 105. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 261–278, 2008     

Reverse Mathematics and Grundy colorings of graphs

The relationship of Grundy and chromatic numbers of graphs in the context of Reverse Mathematics is investi‐gated (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Smaller planar triangle-free graphs that are not 3-list-colorable

In 1995, Voigt constructed a planar triangle-free graph that is not 3-list-colorable. It has 166 vertices. Gutner then constructed such a graph with 164 vertices. We present two more graphs with these properties. The first graph has 97 vertices and a failing list assignment using triples from a set of six colors, while the second has 109 vertices and a failing list assignment using triples from a set of five colors.