Eliminating graphs by means of parallel knock-out schemes

In 1997 Lampert and Slater introduced parallel knock-out schemes, an iterative process on graphs that goes through several rounds. In each round of this process, every vertex eliminates exactly one of its neighbors. The parallel knock-out number of a graph is the minimum number of rounds after which all vertices have been eliminated (if possible). The parallel knock-out number is related to well-known concepts like perfect matchings, hamiltonian cycles, and 2-factors.We derive a number of combinatorial and algorithmic results on parallel knock-out numbers: for families of sparse graphs (like planar graphs or graphs of bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices; this bound is basically tight for trees. Furthermore, there is a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and we show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach (whereas in general graphs this problem is known to be NP-hard). Finally, we prove that the parallel knock-out number of a claw-free graph is either infinite or less than or equal to 2.     

Some explicit examples of Hamiltonian minimal Lagrangian submanifolds in complex space forms

In this paper, we find some new explicit examples of Hamiltonian minimal Lagrangian submanifolds among the Lagrangian isometric immersions of a real space form in a complex space form.     

The communication complexity of private value single-item auctions

This paper is concerned with information revelation in single-item auctions. We compute how much data needs to be transmitted in three strategically equivalent auctions—the Vickrey auction, the English auction and the recently proposed bisection auction—and show that in the truth-telling equilibrium the bisection auction is the best performer.     

A MINI MULTI-GAS DETECTION SYSTEM BASED ON INFRARED PRINCIPLE

To counter the problems of gas accidents in coal mines, family safety resulted from using gas, a new infrared detection system with integration and miniaturization has been developed. The infrared detection optics principle used in developing this system is mainly analyzed. The idea that multi gas detection is introduced and guided through analyzing single gas detection is got across. Through researching the design of cell structure, the cell with integration and miniaturization has been devised. The way of data transmission on Controller Area Network (CAN) bus is explained. By taking Single-Chip Microcomputer (SCM) as intelligence handling, the functional block diagram of gas detection system is designed with its hardware and software system analyzed and devised. This system designed has reached the technology requirement of lower power consumption, mini-volume, big measure range, and able to realize multi-gas detection.     

Barycentric systems and stretchability

Using a general resolution of barycentric systems we give a generalization of Tutte's theorem on convex drawing of planar graphs. We deduce a characterization of the edge coverings into pairwise non-crossing paths which are stretchable: such a system is stretchable if and only if each subsystem of at least two paths has at least three free vertices (vertices of the outer face of the induced subgraph which are internal to none of the paths of the subsystem). We also deduce that a contact system of pseudo-segments is stretchable if and only if it is extendible.     

Preemptive scheduling of interval orders is polynomial

In 1979, Papadimitriou and Yannakakis gave a polynomial time algorithm for the scheduling of jobs requiring unit completion times when the precedence constraints form an interval order. The authors solve here the corresponding problem, for preemptive scheduling (a job can be interrupted to work on more important tasks, and completed at a later time, subject to the usual scheduling constraints.) The m-machine preemptive scheduling problem is shown to have a polynomial algorithm, for both unit time and variable execution times as well, when the precedence constraints are given by an interval order.     

Complete systems, elementary submodels and the tightness of upper hyperspaces

We introduce and study some completeness properties for systems of open coverings of a given topological space. A Hausdorff space admitting a system of cardinality κ satisfying one of these properties is of type Gκ. Hence, we define several new variants of the ?ech number and use elementary submodels to determine further results. We introduce M-hulls and M-networks, for M elementary submodel. As an application, we give estimates for both the tightness and the Lindelöf number of a generic upper hyperspace. Two recent results of Costantini, Holá and Vitolo on the tightness of co-compact hyperspaces follow from ours as corollaries.     

Approximating the single source unsplittable min-cost flow problem

In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed along a single path so that the total flow through any edge is at most its capacity. Moreover, the total cost must not exceed a given budget. This problem has been introduced by Kleinberg [7] and generalizes several NP-complete problems from various areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing, and virtual-circuit routing. Kolliopoulos and Stein [9] and Dinitz, Garg, and Goemans [4] developed algorithms improving the first approximation results of Kleinberg for the problem of minimizing the violation of edge capacities and for other variants. However, known techniques do not seem to be capable of providing solutions without also violating the cost constraint. We give the first approximation results with hard cost constraints. Moreover, all our results dominate the best known bicriteria approximations. Finally, we provide results on the hardness of approximation for several variants of the problem. Received: August 23, 2000 / Accepted: April 20, 2001?Published online October 2, 2001     

Markov processes associated with L p -resolvents and applications to stochastic differential equations on Hilbert space

We give general conditions on a generator of a C₀-semigroup (resp. of a C₀-resolvent) on L^p(E,μ), p ≥ 1, where E is an arbitrary (Lusin) topological space and μ a σ-finite measure on its Borel σ-algebra, so that it generates a sufficiently regular Markov process on E. We present a general method how these conditions can be checked in many situations. Applications to solve stochastic differential equations on Hilbert space in the sense of a martingale problem are given. Dedicated to Giuseppe Da Prato on the occasion of his 70th birthday     

显微镜工作台闭环控制系统的设计与实现

高精度工作台控制系统是现代自动显微系统的重要组成部分,其精度直接影响显微镜对样品的检测质量。介绍了一种基于AT89C52单片机的显微镜工作台闭环控制系统的设计方案。工作台移动时作为检测元件的光栅输出脉冲信号。单片机控制电路实现脉冲的计数并计算误差值,控制步进电机进行反馈补偿。步进电机通过细分驱动模块可以以四种不同的步距驱动工作台移动,以实现显微镜对工作台移动速度的不同需要。8位数码管实时显示工作台移动的实际位置。实验结果表明,该系统的重复定位精度可达到0.020mm,可满足显微镜对控制工作台的要求。