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.     

An explosion point space without the fixed point property

In 1988 A. Gutek proved that there exist one-point connectifications of hereditarily disconnected spaces that do not have the fixed point property. We improve on this result by constructing a one-point connectification of a totally disconnected space without the fixed point property.     

A Positive Doubly Power Bounded Operator with a Nonpositive Inverse Exists on any Infinite-dimensional AL-Space

In this paper we construct a positive doubly power bounded operator with a nonpositive inverse on an AL-space.     

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     

�ɲ����˶�����ά��������������һ�������ڵ����Զ������������������

??We study the linear quadratic optimal stochastic control problem which is jointly driven by Brownian motion and L\'{e}vy processes. We prove that the new affine stochastic differential adjoint equation exists an inverse process by applying the profound section theorem. Applying for the Bellman's principle of quasilinearization and a monotone iterative convergence method, we prove the existence and uniqueness of the solution of the backward Riccati differential equation. Finally, we prove that the optimal feedback control exists, and the value function is composed of the initial value of the solution of the related backward Riccati differential equation and the related adjoint equation.     

Group symmetry in tensor categories and duality for orbifolds

A duality for orbifolds is presented as an application of group extensions in tensor categories.     

Effect of Ru crystal orientation on the adhesion characteristics of Cu for ultra-large scale integration interconnects

The adhesion of Cu on Ru substrates with different crystal orientations was evaluated. The crystal orientation of sputter deposited Ru could be changed from (1 0 0) to (0 0 1) by annealing at 650 °C for 20 min. The adhesion of Cu was evaluated by the degree of Cu agglomeration on Ru. Cu films on annealed Ru films with the (0 0 1) crystal orientation showed 28% lower RMS values and 50% lower Ru surface coverage than Cu as-deposited on Ru having the (1 0 0) crystal orientation after annealing at 550 °C for 30 min, which suggest that Cu wettability on the Ru(0 0 1) was better than that on the Ru(1 0 0) plane. The low lattice misfit of 4% between Cu(1 1 1) and Ru(0 0 1) may be the reason for this good adhesion property.     

Some new nonlinear inequalities and applications to boundary value problems

In this paper, we establish some new nonlinear integral inequalities of the Gronwall–Bellman–Ou-Iang-type in two variables. These on the one hand generalizes and on the other hand furnish a handy tool for the study of qualitative as well as quantitative properties of solutions of differential equations. We illustrate this by applying our new results to certain boundary value problem.     

Existence of solutions on weak vector equilibrium problems

Weak vector equilibrium problems with bi-variable mappings from product space of two bounded complete locally convex Hausdorff topological vector spaces to another topological vector space are studied. The existence theorems of solutions are proved by the FKKM fixed point theorem. Viscosity principle of vector equilibrium problems is dealt with. The relations between solutions of the vector equilibrium problem and those of its perturbation problem are presented.